Théorie > Combinatoire > Dénombrement (suite)

Il faut tout d'abord trouver une relation de récurrence que le problème vérifie. On peut pour cela noter $N(n,k)$ la réponse attendue, c'est-à-dire le nombre de sous-ensembles à $k$ éléments de $\{1,2, \ldots, n\}$ sans entiers consécutifs, et chercher s'il est possible de trouver une formule pour $N(n, k)$ à partir de valeurs inférieures, comme par exemple $N(n-1,k)$ ou $N(n, k-1)$.

Cherchons une telle relation. On considère pour cela un sous-ensemble $E$ à $k$ éléments de $\{1, 2, \ldots, n\}$ sans entiers consécutifs et on cherche à se ramener à une situation similaire avec des variables plus petites. Si $E$ ne contient pas $n$, alors il s'agit également d'un sous-ensemble de $\{1, 2, \ldots, n-1\}$ et est donc pris en compte lorsqu'on calcule $N(n-1, k)$. En fait, on a clairement une bijection entre les sous-ensembles pris en compte dans $N(n, k)$ ne contenant pas $n$ et les sous-ensembles pris en compte dans $N(n-1, k)$.

Il reste à considérer le cas où $E$ contient $n$. Dans ce cas, $E \setminus \{n\}$ est un sous-ensemble à $(k-1)$ éléments de $\{1, 2, \ldots, n-1\}$. En fait, puisque $E$ contient $n$ et ne contient pas deux éléments consécutifs, il ne peut pas contenir $(n-1)$. L'ensemble $E \setminus \{n\}$ est donc même contenu dans $\{1, 2, \ldots, n-2\}$, et il est donc pris en compte dans $N(n-2,k-1)$. Réciproquement, en présence d'un sous-ensemble à $(k-1)$ éléments de $\{1, 2, \ldots, n-2\}$ sans entiers consécutifs, on peut bien sûr lui rajouter l'élément $n$ et obtenir un ensemble pris en compte dans $N(n,k)$. On a donc une bijection entre les sous-ensembles pris en compte dans $N(n, k)$ contenant $n$ et les sous-ensembles pris en compte dans $N(n-2, k-1)$.

De ces constatations, on déduit l'égalité
$$N(n, k) = N(n-1, k) + N(n-2,k-1).$$
L'étape suivante dans la résolution du problème est alors de "deviner" sa réponse. Cela se fait généralement en la calculant pour les petites valeurs des variables. Dans notre situation, on peut par exemple remarquer que :

• $N(n, 0) = 1$ pour tout $n$, car il n'y a qu'une seule manière de ne choisir aucun nombre.


• $N(n, 1) = n$ pour tout $n$, car il y a $n$ façons de choisir un élément de $\{1, 2, \ldots, n\}$.


• $N(n, 2) = \frac{(n-2)(n-1)}{2}$. En effet, si on choisit $1$ pour le plus petit des deux éléments, alors on a $(n-2)$ choix pour le second; si on choisit $2$, alors on a $(n-3)$ choix pour le second; et ainsi de suite. Au total, il y a donc $(n-2)+(n-3)+\ldots+2+1 = \frac{(n-2)(n-1)}{2}$ sous-ensembles vérifiant les conditions.

On se rend donc compte notamment que $N(n, 2) = C^2_{n-1}$ et $N(n,1) = C^1_n$. Il est donc raisonnable de penser que la solution générale est peut-être $N(n, k) = C ^k_{n+1-k}$, puisque cette formule est bien vérifiée pour $k \in \{0, 1, 2\}$. Il reste à prouver que cette formule est bien correcte, et on peut pour cela utiliser notre relation de récurrence.

Comme notre relation permet de remplacer $n$ par $(n-1)$ et $(n-2)$, la récurrence la plus facile à exécuter est une récurrence sur $n$. On voit facilement que la formule que nous avons devinée est bien vérifiée pour $n = 1$ et $n = 2$, ce qui constitue le cas de base de notre récurrence. Supposons à présent que la formule est correcte pour $(n-2)$ et $(n-1)$ et montrons-la pour $n$. Vu notre relation, il suffit de prouver que
$$C^k_{n+1-k} = C^k_{n-k} + C^{k-1}_{n-k}.$$ Mais il s'agit là de la relation de Pascal (où $n$ a été remplacé par $(n+1-k)$) ! Nous venons donc de montrer que
$$N(n, k) = C^k_{n-k+1}.$$