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


Général

Introduction Chapitre entier

Points théoriques

Comptage direct Bijection Inclusion-exclusion Récurrence

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6

Récurrence

Une autre méthode pour résoudre des problèmes de dénombrement est la récurrence. Pour illustrer cela, considérons à nouveau l'exemple suivant.

Exemple : Quel est le nombre de sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n\}$ ne contenant pas d'entiers consécutifs?

Nous avons déjà résolu ce problème en le ramenant à un problème plus simple, via une bijection. Il est cependant aussi possible de s'en sortir sans remarquer qu'une telle bijection existe, en procédant par récurrence. Pour ce faire, 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 dans notre exemple. 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 exemple, 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-1)+\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}.$$
La principale difficulté de cette méthode est de trouver la relation de récurrence que la réponse vérifie. En effet, deviner la réponse et montrer par récurrence qu'elle est correcte constitue généralement une formalité (pourvu que l'on soit familier avec les coefficients binomiaux).

Remarque : Cette méthode semble ne fonctionner que lorsqu'une ou plusieurs variables comme $n$ et $k$ sont présentes dans le problème, mais il n'y a en fait pas réellement de telle restriction. En effet, si un problème de dénombrement ne comporte pas de variables, alors il contient généralement à la place un ou plusieurs nombres plutôt grands (de sorte que le problème ne soit pas résoluble en testant les cas un par un). Il ne faut alors pas hésiter à remplacer ce ou ces nombres par des variables, et à résoudre le problème en toute généralité. En plus de permettre une éventuelle récurrence, une telle démarche permet de donner des plus petites valeurs aux variables introduites et de parfois deviner la forme générale de la réponse (et a fortiori la réponse pour les grandes valeurs du problème). Il reste évidemment à prouver que cette réponse est correcte.