Exercice 41

1. Par récurrence sur $n \geqslant 1$. Pour $n = 1$, la liste $\varnothing$, $\{1\}$ convient. Supposons construite une liste convenable $C_{0}$, …, $C_{N-1}$ des parties de $[\![1\,;n]\!]$, avec $N = 2^{n}$. On forme la liste des parties de $[\![1\,;n+1]\!]$ en parcourant cette liste, puis en la parcourant à l'envers après avoir ajouté $n + 1$ à chaque partie : $$C_{0},\ C_{1},\ \dots,\ C_{N-1},\ C_{N-1} \cup \{n+1\},\ C_{N-2} \cup \{n+1\},\ \dots,\ C_{0} \cup \{n+1\}.$$ Les parties de $[\![1\,;n+1]\!]$ ne contenant pas $n + 1$ sont les $C_{k}$, et celles qui le contiennent sont les $C_{k} \cup \{n+1\}$ : chacune apparaît exactement une fois, ce qui fait bien $2N = 2^{n+1}$ parties. Deux termes consécutifs dans une même moitié sont adjacents, comme $C_{k-1}$ et $C_{k}$. À la jonction, $C_{N-1}$ et $C_{N-1} \cup \{n+1\}$ sont adjacents, ainsi que le dernier terme $C_{0} \cup \{n+1\}$ et le premier $C_{0}$. Pour $n = 3$, on obtient $$\boxed{\varnothing,\ \{1\},\ \{1,2\},\ \{2\},\ \{2,3\},\ \{1,2,3\},\ \{1,3\},\ \{3\}}$$

2. On adapte la construction précédente pour contrôler les premiers termes. Montrons par récurrence sur $n \geqslant 1$ qu'il existe une liste cyclique adjacente $C_{0}$, …, $C_{N-1}$ des parties de $[\![1\,;n]\!]$, avec $N = 2^{n}$, telle que $C_{k} = [\![1\,;k]\!]$ pour $0 \leqslant k \leqslant n$ (avec $[\![1\,;0]\!] = \varnothing$). Pour $n = 1$, la liste $\varnothing$, $\{1\}$ convient.

Supposons une telle liste construite pour $n$, et notons $m = n + 1$. Comme $N = 2^{n} \geqslant n + 1$, les termes $C_{0}$, …, $C_{n}$ existent. On forme la liste $$\underbrace{C_{0},\ \dots,\ C_{n}}_{\text{(1)}},\quad \underbrace{C_{n} \cup \{m\},\ \dots,\ C_{0} \cup \{m\}}_{\text{(2)}},\quad \underbrace{C_{N-1} \cup \{m\},\ \dots,\ C_{n+1} \cup \{m\}}_{\text{(3)}},\quad \underbrace{C_{n+1},\ \dots,\ C_{N-1}}_{\text{(4)}}.$$

• Chaque partie de $[\![1\,;m]\!]$ figure exactement une fois : les $C_{k}$ dans les blocs (1) et (4), les $C_{k} \cup \{m\}$ dans (2) et (3).

• Les termes consécutifs à l'intérieur de chaque bloc sont adjacents, car $C_{k-1}$ et $C_{k}$ le sont. Aux jonctions : $C_{n}$ et $C_{n} \cup \{m\}$ ; puis $C_{0} \cup \{m\}$ et $C_{N-1} \cup \{m\}$, adjacents car $C_{0}$ et $C_{N-1}$ le sont, par cyclicité ; puis $C_{n+1} \cup \{m\}$ et $C_{n+1}$ ; enfin le dernier terme $C_{N-1}$ et le premier $C_{0}$. Si les blocs (3) et (4) sont vides, ce qui n'arrive que pour $N = n + 1$, c'est-à-dire $n = 1$, la liste se referme directement de $C_{0} \cup \{m\}$ sur $C_{0}$.

• Les premiers termes sont $C_{k} = [\![1\,;k]\!]$ pour $k \leqslant n$, puis $C_{n} \cup \{m\} = [\![1\,;n+1]\!]$ au rang $n + 1 = m$.

$$\boxed{\text{On peut imposer } A_{0} = \varnothing \text{ et } A_{k} = [\![1\,;k]\!] \text{ pour } 1 \leqslant k \leqslant n.}$$ Pour $n = 3$, la construction fournit $\varnothing$, $\{1\}$, $\{1,2\}$, $\{1,2,3\}$, $\{1,3\}$, $\{3\}$, $\{2,3\}$, $\{2\}$, liste que l'on vérifie directement. La construction a été contrôlée par ordinateur jusqu'à $n = 8$.

À retenir : on démontre souvent un énoncé plus précis que celui demandé, ici la position des $n + 1$ premiers termes, pour disposer d'une hypothèse de récurrence assez riche. On retrouve, sous une forme combinatoire, la leçon des exercices 19 et 24.