Exercice 5

On note $N_{k}$ le nombre de parties de $\llbracket 1\,,n \rrbracket$ de diamètre $k$. Le diamètre d'une partie non vide est compris entre $0$ et $n - 1$, donc $N_{k} = 0$ pour $k \geqslant n$. Une partie de diamètre $0$ a son minimum égal à son maximum : c'est un singleton, et $N_{0} = n$.

Soit $k \in \llbracket 1\,,n - 1 \rrbracket$. Une partie $A$ de diamètre $k$ est déterminée par son minimum $a$ et par l'ensemble $A \cap \llbracket a + 1\,,a + k - 1 \rrbracket$ de ses éléments compris strictement entre $a$ et $a + k$. Réciproquement, pour $a \in \llbracket 1\,,n - k \rrbracket$ et $B$ une partie quelconque de l'intervalle $\llbracket a + 1\,,a + k - 1 \rrbracket$, qui a $k - 1$ éléments, la partie $\{a\} \cup B \cup \{a + k\}$ est contenue dans $\llbracket 1\,,n \rrbracket$ et a pour diamètre $k$. On a ainsi une bijection entre les parties de diamètre $k$ et les couples $(a, B)$ ; il y a $n - k$ choix de $a$ et, pour chacun, $2^{k-1}$ choix de $B$ (proposition 3). $$\boxed{N_{0} = n, \qquad N_{k} = (n - k)\,2^{k-1} \text{ pour } 1 \leqslant k \leqslant n - 1, \qquad N_{k} = 0 \text{ pour } k \geqslant n}$$ Pour la vérification, on écrit $n - k = \sum_{j=k}^{n-1} 1$ et l'on intervertit les sommes (chapitre 3, proposition 8) : $$\sum_{k=1}^{n-1} (n - k)2^{k-1} = \sum_{j=1}^{n-1}\,\sum_{k=1}^{j} 2^{k-1} = \sum_{j=1}^{n-1} \big(2^{j} - 1\big) = \big(2^{n} - 2\big) - (n - 1) = 2^{n} - n - 1.$$

$$\boxed{\sum_{k \geqslant 0} N_{k} = n + 2^{n} - n - 1 = 2^{n} - 1}$$ C'est bien le nombre de parties non vides de $\llbracket 1\,,n \rrbracket$ (proposition 3) ✓ : les parties non vides se répartissent selon leur diamètre en morceaux disjoints. Lu dans l'autre sens, ce dénombrement est une démonstration combinatoire de l'identité $\sum_{k=1}^{n-1} (n - k)2^{k-1} = 2^{n} - n - 1$.