Valeurs particulières, symétrie, relation de Pascal

5.1 Valeurs particulières

Pour tout entier $n \geq 0$ (et $n \geq 1$ ou $n \geq 2$ quand il le faut) :

• $\dbinom{n}{0} = 1$ : la seule partie à $0$ élément est l'ensemble vide ;
• $\dbinom{n}{1} = n$ : les parties à un élément sont les $n$ ensembles $\{x\}$ ;
• $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ : c'est la formule pour $k = 2$ ;
• $\dbinom{n}{n} = 1$ : la seule partie à $n$ éléments est $E$ lui-même.

Exemple 16. Dans un tournoi de handball, $10$ équipes se rencontrent une fois chacune. Un match correspond à une paire d'équipes, c'est-à-dire une partie à $2$ éléments : il y a $\dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ matchs.

5.2 Symétrie

Propriété (programme). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n$ : $\binom{n}{n-k} = \binom{n}{k}.$

Par le calcul. $\dbinom{n}{n-k} = \dfrac{n!}{\big(n - (n-k)\big)!\,(n-k)!} = \dfrac{n!}{k!\,(n-k)!} = \dbinom{n}{k}$.

Par le dénombrement. Choisir les $k$ éléments que l'on prend, c'est choisir les $n - k$ éléments que l'on laisse. À chaque partie $A$ à $k$ éléments, on associe son complémentaire $\overline{A}$, qui a $n - k$ éléments ; et chaque partie à $n - k$ éléments est obtenue une seule fois, comme complémentaire de son propre complémentaire. Il y a donc autant de parties à $k$ éléments que de parties à $n - k$ éléments.

Exemple 17. $\dbinom{30}{28} = \dbinom{30}{2} = \dfrac{30 \times 29}{2} = 435$ : choisir $28$ élèves sur $30$ revient à choisir les $2$ qui restent.

5.3 La relation de Pascal

Propriété (programme : relation de Pascal). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n - 1$ : $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.$

Par exemple, $\dbinom41 + \dbinom42 = 4 + 6 = 10 = \dbinom52$.

Démonstration par le calcul (programme). On part de la formule avec les factorielles : $\binom{n}{k} + \binom{n}{k+1} = \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k+1)!\,(n-k-1)!}.$ On met les deux fractions au même dénominateur $(k+1)!\,(n-k)!$, en utilisant $(k+1)! = (k+1) \times k!$ et $(n-k)! = (n-k) \times (n-k-1)!$ (valable car $n - k \geq 1$) : $\binom{n}{k} + \binom{n}{k+1} = \frac{n!\,(k+1)}{(k+1)!\,(n-k)!} + \frac{n!\,(n-k)}{(k+1)!\,(n-k)!} = \frac{n!\,\big((k+1) + (n-k)\big)}{(k+1)!\,(n-k)!} = \frac{n!\,(n+1)}{(k+1)!\,(n-k)!}.$ Or $n!\,(n+1) = (n+1)!$ et $n - k = (n+1) - (k+1)$. On reconnaît $\frac{(n+1)!}{(k+1)!\,\big((n+1)-(k+1)\big)!} = \binom{n+1}{k+1}.$

Démonstration par le dénombrement (programme : méthode combinatoire). Soit $F$ un ensemble à $n + 1$ éléments, et $a$ un élément de $F$. On compte les parties de $F$ à $k + 1$ éléments en deux groupes disjoints.

• Celles qui contiennent $a$. En retirant $a$, on obtient une partie à $k$ éléments de $F \setminus \{a\}$, qui a $n$ éléments ; et inversement, en ajoutant $a$ à une telle partie, on retrouve la partie de départ. Il y en a $\dbinom{n}{k}$.
• Celles qui ne contiennent pas $a$. Ce sont les parties à $k + 1$ éléments de $F \setminus \{a\}$. Il y en a $\dbinom{n}{k+1}$.

Par le principe additif, $\dbinom{n+1}{k+1} = \dbinom{n}{k} + \dbinom{n}{k+1}$.

Exemple 18. $F = \{a\,;b\,;c\,;d\,;e\}$. Parmi ses $\dbinom52 = 10$ parties à $2$ éléments, $4$ contiennent $a$ ($\{a\,;b\}$, $\{a\,;c\}$, $\{a\,;d\}$, $\{a\,;e\}$), et $\dbinom42 = 6$ ne le contiennent pas : $4 + 6 = 10$.