Combinaisons

4.1 Définition

Définition (programme). Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $0 \leq k \leq n$. Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments. Leur nombre se note $\binom{n}{k}, \qquad \text{qui se lit « } k \text{ parmi } n \text{ ».}$

Dans une combinaison, l'ordre ne compte pas et il n'y a pas de répétition. Les nombres $\binom{n}{k}$ sont aussi appelés coefficients binomiaux.

Exemple 12. Les parties à $2$ éléments de $E = \{a\,;b\,;c\,;d\}$ sont $\{a\,;b\}$, $\{a\,;c\}$, $\{a\,;d\}$, $\{b\,;c\}$, $\{b\,;d\}$ et $\{c\,;d\}$. Donc $\dbinom{4}{2} = 6$.

4.2 Des listes aux parties : les formules

Toujours avec $E = \{a\,;b\,;c\,;d\}$, il y a $4 \times 3 = 12$ couples d'éléments distincts. Chaque partie $\{x\,;y\}$ donne exactement deux couples, $(x\,;y)$ et $(y\,;x)$. Donc $12 = 6 \times 2$, c'est-à-dire $\dbinom42 = \dfrac{4 \times 3}{2}$.

Cas général. Les $k$ éléments d'une partie à $k$ éléments peuvent être rangés de $k!$ façons : chaque partie donne $k!$ $k$-uplets d'éléments distincts. Et chaque $k$-uplet d'éléments distincts est obtenu une seule fois, à partir de la partie formée de ses éléments. Donc $k! \times \binom{n}{k} = n(n-1)\cdots(n-k+1).$

Propriété (programme : formules). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n$ : $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{(n-k)!\,k!}.$

Pour $k = 0$, le produit du numérateur n'a aucun facteur et vaut $1$ par convention ; la seconde formule donne directement $\dfrac{n!}{n!\,0!} = 1$.

Exemple 13. $\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10$ et $\dbinom{6}{3} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = \dfrac{120}{6} = 20$.

4.3 L'ordre compte-t-il ?

Exemple 14. Une association compte $12$ membres.

• Pour élire un bureau (un président, un trésorier, un secrétaire), l'ordre compte : chaque poste est différent. Un bureau est un triplet de membres distincts : $12 \times 11 \times 10 = 1\,320$ bureaux.
• Pour désigner une commission de $3$ membres, sans poste, l'ordre ne compte pas : une commission est une partie à $3$ éléments. Il y en a $\dbinom{12}{3} = \dfrac{1\,320}{3!} = 220$.

Chaque commission correspond à $3! = 6$ bureaux : on répartit les trois postes entre ses trois membres.

Exemple 15 (un jeu de cartes). Un jeu de $32$ cartes est distribué. Une main de $5$ cartes est une partie à $5$ éléments de l'ensemble des $32$ cartes : il y a $\binom{32}{5} = \frac{32 \times 31 \times 30 \times 29 \times 28}{5!} = 201\,376 \text{ mains.}$

À la calculatrice, $\binom{n}{k}$ s'obtient avec la touche ou le menu « Combinaison » (souvent noté nCr).