CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #21 : Combien y a-t-il de parties de $\{1, 2, \ldots, n\}$ ne contenant pas deux entiers consécutifs ?

---

La réponse est le $(n+2)$-ième nombre de Fibonacci1.

La manière la plus simple de démontrer ce résultat est probablement d'établir que le nombre $p_n$ de parties de $\{1, 2, \ldots, n\}$ ne contenant pas deux entiers consécutifs vérifie la relation de récurrence $p_{n+2} = p_n + p_{n+1}$. Il suffit ensuite de vérifier que $p_1 = F_3 = 2$ (les deux parties $\varnothing$ et $\{1\}$ vérifient tautologiquement la condition) et $p_2 = F_4 = 3$ (les trois parties $\varnothing$, $\{1\}$ et $\{2\}$ vérifient la condition, contrairement à $\{1,2\}$).

Pour cela, remarquons que les parties de $\{1, 2, \ldots, n+2\}$ ne contenant pas deux entiers consécutifs se partagent en deux types :

• Les parties contenant $n+2$ ne peuvent pas contenir $n+1$. Elles s'écrivent donc $F \sqcup \{n+2\}$, où $F$ est une partie de $\{1, 2, \ldots, n\}$ ne contenant pas deux entiers consécutifs. Réciproquement, pour une telle partie $F$, $F \sqcup \{n+2\}$ ne contient pas deux entiers consécutifs. Le nombre de ces parties est donc $p_{n}$.
• Les parties ne contenant pas $n+2$ sont simplement les parties de $\{1, \ldots, n+1\}$ ne contenant pas deux entiers consécutifs. Il y en a donc $p_{n+1}$.

Ce petit dénombrement démontre donc la relation de récurrence, et conclut la preuve.
 

Une autre preuve de ce résultat consiste à se ramener à une définition combinatoire classique des nombres de Fibonacci : $F_{m+1}$ est le nombre de façons de décomposer $m$ en une somme $i_1 + \cdots + i_d = m$, où les $i_k$ valent $1$ ou $2$. Cette caractérisation est d'ailleurs à l'origine de la première apparition des nombres de Fibonacci dans l'histoire, à propos de règles de prosodie en sanskrit.2.

Étant donné une telle somme, que l'on peut voir comme un pavage du rectangle $1 \times m$ par des rectangles $1 \times 1$ et $1\times 2$, les premières cases des rectangles $1 \times 2$ forment une partie de $\{1,2, \ldots, m-1\}$ sans deux entiers consécutifs.

Il n'est pas difficile de voir que cette construction réalise une bijection entre ces pavages du rectangle $1\times m$ et les parties de $\{1, 2, \ldots, m-1\}$ sans entiers consécutifs. Le nombre de parties de $\{1, 2, \ldots, n\}$ est donc bien $F_{n+2}$.
 

• 1. On choisit de numéroter les nombres de Fibonacci en commençant par $F_0 = 0$ et $F_1 = 1$.
• 2. Si chaque syllabe d'un mot peut être courte (auquel cas elle compte pour un temps) ou longue (deux temps), il s'agit de compter le nombre de profils prosodiques pouvant exister pour un vers de $m$ temps.