Les parties sans deux entiers consécutifs

Exercice de TD · niveau 3 (difficile) · mathématiques MPSI, chapitre 18 — Dénombrement · C. Combinaisons et identités

Énoncé

Pour $n \in N$ , on note $a_{n}$ le nombre de parties $A$ de ${1, \dots, n}$ ne contenant aucun couple d'entiers consécutifs : pour tout $i$ , les entiers $i$ et $i + 1$ ne sont pas tous deux dans $A$ . On convient que $a_{0} = 1$ . On note $(F_{n})$ la suite de Fibonacci : $F_{0} = 0$ , $F_{1} = 1$ , $F_{n + 2} = F_{n + 1} + F_{n}$ .

a) Calculer $a_{1}$ , $a_{2}$ , $a_{3}$ en listant les parties.

b) En classant les parties selon qu'elles contiennent $n$ ou non, montrer que $a_{n} = a_{n - 1} + a_{n - 2}$ pour $n \geq 2$ . En déduire $a_{n} = F_{n + 2}$ .

c) Soit $k \in N$ . Montrer que le nombre de telles parties à $k$ éléments est $(k n - k + 1)$ (pour $A = {x_{1} < x_{2} < \dots < x_{k}}$ , on pourra considérer les entiers $y_{i} = x_{i} - (i - 1)$ ).

d) En déduire $k \geq 0 \sum (k n + 1 - k) = F_{n + 2}$ : les sommes « diagonales » du triangle de Pascal sont les nombres de Fibonacci.

e) Combien de mots binaires de longueur $n$ ne contiennent pas deux $1$ consécutifs ?

Corrigé

La stratégie. La récurrence combinatoire par le dernier élément — « contient $n$ ou non » — qui est exactement le mécanisme de la démonstration combinatoire de la formule de Pascal ; puis un encodage qui resserre les éléments pour supprimer la contrainte.

a) Les premières valeurs. Parties de ${1}$ : $\emptyset$ , ${1}$ , donc $a_{1} = 2$ . Parties de ${1, 2}$ sans deux consécutifs : $\emptyset$ , ${1}$ , ${2}$ — la partie ${1, 2}$ est exclue — donc $a_{2} = 3$ . Parties de ${1, 2, 3}$ : $\emptyset$ , ${1}$ , ${2}$ , ${3}$ , ${1, 3}$ , donc $a_{3} = 5$ . On reconnaît $F_{3} = 2$ , $F_{4} = 3$ , $F_{5} = 5$ .

b) La récurrence. Soit $n \geq 2$ . Classons les parties admissibles de ${1, \dots, n}$ en deux classes disjointes qui recouvrent tout : celles qui ne contiennent pas $n$ et celles qui le contiennent.

Celles qui ne contiennent pas $n$ sont exactement les parties admissibles de ${1, \dots, n - 1}$ : il y en a $a_{n - 1}$ .

Celles qui contiennent $n$ ne contiennent pas $n - 1$ , par la contrainte ; en retirant $n$ , on obtient une partie admissible de ${1, \dots, n - 2}$ . Réciproquement, toute partie admissible de ${1, \dots, n - 2}$ , augmentée de $n$ , est admissible dans ${1, \dots, n}$ : elle ne contient pas $n - 1$ , et $n$ ne crée aucun couple consécutif. Cette correspondance est une bijection : il y en a $a_{n - 2}$ .

Par le principe d'addition, $a_{n} = a_{n - 1} + a_{n - 2}$ . (Pour $n = 2$ , la seconde classe est ${{2}}$ , et $a_{0} = 1$ compte bien la partie vide de $\emptyset$ .)

L'identification. Les suites $(a_{n})$ et $(F_{n + 2})$ vérifient la même récurrence d'ordre $2$ , et coïncident aux deux premiers rangs : $a_{0} = 1 = F_{2}$ , $a_{1} = 2 = F_{3}$ . Par récurrence double, $a_{n} = F_{n + 2}$ pour tout $n$ : si $a_{n - 1} = F_{n + 1}$ et $a_{n - 2} = F_{n}$ , alors $a_{n} = F_{n + 1} + F_{n} = F_{n + 2}$ .

c) Les parties à $k$ éléments. Soit $A = {x_{1} < x_{2} < \dots < x_{k}}$ une partie admissible à $k$ éléments : la contrainte s'écrit $x_{i + 1} \geq x_{i} + 2$ pour $1 \leq i < k$ . Posons $y_{i} = x_{i} - (i - 1)$ . Alors $y_{i + 1} - y_{i} = x_{i + 1} - x_{i} - 1 \geq 1$ : la suite $(y_{i})$ est strictement croissante. De plus $y_{1} = x_{1} \geq 1$ et $y_{k} = x_{k} - (k - 1) \leq n - k + 1$ . Donc ${y_{1}, \dots, y_{k}}$ est une partie à $k$ éléments de ${1, \dots, n - k + 1}$ .

Réciproquement, soit ${y_{1} < \dots < y_{k}}$ une partie à $k$ éléments de ${1, \dots, n - k + 1}$ ; posons $x_{i} = y_{i} + (i - 1)$ . Alors $x_{i + 1} - x_{i} = y_{i + 1} - y_{i} + 1 \geq 2$ , $x_{1} = y_{1} \geq 1$ et $x_{k} = y_{k} + k - 1 \leq n$ : les $x_{i}$ forment une partie admissible de ${1, \dots, n}$ . Les deux applications sont inverses l'une de l'autre : le nombre cherché est $(k n - k + 1)$ , nul dès que $k > n - k + 1$ , c'est-à-dire dès que $2 k > n + 1$ — on ne peut pas placer plus de la moitié des entiers sans en prendre deux consécutifs.

Lecture par les étoiles et les barres. Les $k$ éléments choisis, et les $n - k$ non choisis, forment un mot de longueur $n$ à deux lettres où deux « choisi » ne sont jamais adjacents : on aligne les $n - k$ non choisis, et l'on place les $k$ choisis dans $k$ des $n - k + 1$ intervalles qu'ils délimitent, au plus un par intervalle — $(k n - k + 1)$ façons. C'est le même nombre, par l'autre codage.

d) Les diagonales du triangle de Pascal. Les parties admissibles de ${1, \dots, n}$ se classent selon leur cardinal $k$ , de $0$ à $⌊ \frac{n + 1}{2} ⌋$ ; par le principe d'addition et le c), $F_{n + 2} = a_{n} = k \geq 0 \sum (k n + 1 - k),$ la somme étant finie puisque ses termes sont nuls au-delà. Dans le triangle de Pascal, les termes $(0 n + 1), (1 n), (2 n - 1), \dots$ sont lus sur une diagonale montante : les sommes diagonales sont les nombres de Fibonacci. Contrôle pour $n = 4$ : $(0 5) + (1 4) + (2 3) = 1 + 4 + 3 = 8 = F_{6}$ .

e) Les mots binaires. Un mot binaire de longueur $n$ est déterminé par l'ensemble des positions de ses $1$ , qui est une partie de ${1, \dots, n}$ ; le mot n'a pas deux $1$ consécutifs si et seulement si cette partie est admissible. Il y a donc $F_{n + 2}$ tels mots : $5$ pour $n = 3$ ( $000, 001, 010, 100, 101$ ), $8$ pour $n = 4$ , $144$ pour $n = 10$ .

Ce que l'exercice installe. La récurrence combinatoire par le dernier élément : trier les objets selon qu'ils contiennent $n$ ou non, et reconnaître dans chaque classe les objets du rang précédent. C'est mot pour mot la démonstration combinatoire de la formule de Pascal, et la même idée compte les mots évitant un motif, les pavages, les chemins sous contrainte. Et un codage qui « resserre » — $y_{i} = x_{i} - (i - 1)$ — transforme une contrainte d'écart en une contrainte de simple croissance.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.