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

Bijection

Il n'est cependant pas toujours possible de compter directement le nombre de possibilités. Considérons 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?

Dans l'idée de procéder comme dans la section précédente, on peut essayer de choisir les $k$ éléments un par un. On a, pour le premier élément, $n$ choix possibles. Disons que l'on a choisi $x_1$. Lors du choix du deuxième élément $x_2$, on ne peut alors plus prendre $x_1$, mais on ne peut pas non plus prendre $x_1 - 1$ ou $x_1+1$. Si $x_1 = 1$, alors il y a deux valeurs interdites ($1$ et $2$), tout comme si $x_1 = n$ ($n$ et $n-1$), mais il y a trois valeurs interdites lorsque $x_1 \in \{2, 3, \ldots, n-1\}$. Il faut donc pour continuer distinguer le cas où $x_1$ vaut $1$ ou $n$ des autres cas. Mais maintenant, lors du choix du troisième élément, le nombre de valeurs interdites dépend de $x_1$ et de $x_2$, et le nombre de cas ne fait que grandir! Il n'est donc pas possible de trouver une solution avec cette méthode. (Notons que si elle avait abouti, il aurait fallu diviser le résultat par $k!$ à la fin puisque l'on aurait tenu compte de l'ordre de nos choix.)

On peut alors décider d'effectuer un comptage plus astucieux, en choisissant nos éléments dans l'ordre croissant. On a alors à nouveau $n$ possibilités pour $x_1$. Pour $x_2$, il nous faut choisir une valeur supérieure ou égale à $x_1+2$ : il y a donc $n-x_1-1$ possibilités. Ce nombre dépendant de $x_1$, il semble encore une fois compliqué de continuer dans cette voie. En effet, le nombre de possibilités pour $x_3$ dépendra à son tour des valeurs de $x_1$ et $x_2$ et ainsi de suite, et cette dépendance ne peut pas être gérée facilement.

Ce problème ne semble pas aussi simple à résoudre que l'exemple précédent. Dans une telle situation, une technique est d'essayer de se ramener à un problème plus simple. Notre exemple ressemble fort au nombre de combinaisons de $k$ objets parmi $n$, il y a uniquement la contrainte que l'on ne peut pas prendre des nombres consécutifs. Ne serait-il pas possible de passer d'une situation à l'autre?

Lorsque l'on choisit simplement $k$ éléments $\{y_1, y_2, \ldots, y_k\}$ (disons avec $y_1 < y_2 < \ldots < y_k$) dans $\{1, 2, \ldots, n\}$, l'unique problème est qu'il se peut que certains éléments soient consécutifs. Une idée serait donc, une fois que l'on a choisi $\{y_1, y_2, \ldots, y_k\}$, de modifier ces choix pour être certain que les éléments ne soient pas consécutifs. Une façon simple de procéder est de remplacer $y_2$ par $y_2 + 1$ (de sorte que ce nouvel élément ne soit jamais consécutif à $y_1$), puis $y_3$ par $y_3+2$, et ainsi de suite jusque $y_k$ que l'on remplace par $y_k+k-1$. Evidemment le lecteur averti aura remarqué qu'il se peut maintenant que ces éléments dépassent $n$. On peut cependant éviter ce dépassement en imposant à nos $y_1, y_2, \ldots, y_k$ d'être inférieurs ou égaux à $n-k+1$ et non plus $n$. En résumé, il est possible d'associer à
$$\{y_1, y_2, \ldots, y_k\} \subseteq \{1, 2, \ldots, n-k+1\}$$ (avec $y_1 < y_2 < \ldots < y_k$) l'ensemble
$$\{x_1, x_2, \ldots, x_k\} = \{y_1, y_2+1, \ldots, y_k+k-1\} \subseteq \{1, 2, \ldots, n\}$$ (avec $x_1 < x_2 < \ldots < x_k$) , et ce nouvel ensemble ne contient pas d'entiers consécutifs! Or, on se convainc facilement qu'avec cette méthode, nous allons atteindre tous les sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n\}$ ne contenant pas d'entiers consécutifs. En effet, un tel sous-ensemble
$$\{x_1, x_2, \ldots, x_k\} \subseteq \{1, 2, \ldots, n\}$$ proviendra toujours du sous-ensemble
$$\{y_1, y_2, \ldots, y_n\} = \{x_1, x_2-1, \ldots, x_k-k+1\} \subseteq \{1, 2, \ldots, n-k+1\}.$$
Ce que nous venons de montrer, c'est qu'il existe une bijection entre les sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n-k+1\}$ et les sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n\}$ ne contenant pas d'entiers consécutifs. Une bijection entre deux ensembles $A$ et $B$ consiste en effet en une fonction associant à chaque élément de $A$ un élément de $B$, de sorte que l'on puisse, à partir d'un élément de $B$, retrouver l'élément de $A$ duquel il provient (on montre en fait qu'il existe une fonction inverse). Or, lorsque l'on a une telle bijection entre $A$ et $B$, les deux ensembles ont forcément le même cardinal (ils ont le même nombre d'éléments).

Dans notre exemple, cela signifie que le nombre de sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n-k+1\}$ est exactement égal au nombre de sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n\}$ sans entiers consécutifs, c'est-à-dire la valeur que nous cherchons. Or, le nombre de sous-ensembles à $k$ éléments de $\{1, 2, \ldots, n-k+1\}$ est simplement le nombre de combinaisons de $k$ objets parmi $n-k+1$, ce qui est égal à $C^k_{n-k+1}$. Il s'agit donc de la réponse attendue.