Il n'est cependant pas toujours possible de compter directement le nombre de possibilités. Considérons l'exemple suivant.
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 ?
Solution
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$. Évidemment 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 situation, 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.