Combinatoire et dénombrement

Compter sans tout énumérer : codes, podiums, mains de cartes, chemins… Quelques principes (additif, multiplicatif) et trois familles d'objets (k-uplets, permutations, combinaisons) suffisent pour la plupart des situations.

Utiliser les principes additif et multiplicatif
Dénombrer k-uplets, permutations, combinaisons
Calculer et utiliser les coefficients binomiaux
Démontrer la relation de Pascal

Cours

1. Principes de base

Le cardinal d'un ensemble fini $E$, noté $\mathrm{Card}(E)$, est son nombre d'éléments. Le produit cartésien $E \times F$ est l'ensemble des couples $(x\,;\,y)$ avec $x \in E$, $y \in F$ ; plus généralement $E_1 \times \dots \times E_k$ est l'ensemble des k-uplets $(x_1, \dots, x_k)$.

Si $A$ et $B$ sont disjoints : $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B)$. On l'utilise quand on distingue des cas qui s'excluent.

$\mathrm{Card}(E \times F) = \mathrm{Card}(E) \times \mathrm{Card}(F)$ et plus généralement $\mathrm{Card}(E_1 \times \dots \times E_k) = \mathrm{Card}(E_1) \times \dots \times \mathrm{Card}(E_k)$. On l'utilise pour des choix successifs (« et ensuite »).

2. k-uplets

Si $\mathrm{Card}(E) = n$, le nombre de k-uplets d'éléments de $E$ (avec répétitions possibles, l'ordre compte) est $\mathrm{Card}(E^k) = n^k$.

Exemples : codes à 4 chiffres : $10^4$ ; mots de longueur $n$ sur $\{0, 1\}$ : $2^n$ ; issues de $n$ épreuves de Bernoulli : $2^n$.

Le nombre de k-uplets d'éléments distincts d'un ensemble à $n$ éléments ($k \leqslant n$) est $$n \times (n - 1) \times \dots \times (n - k + 1) = \frac{n!}{(n - k)!}.$$

Pour $n \in \mathbb{N}^*$, $n! = 1 \times 2 \times \dots \times n$, et $0! = 1$. Le nombre de permutations (façons d'ordonner) d'un ensemble à $n$ éléments est $n!$.

Exemple : 8 coureurs peuvent arriver dans $8! = 40\,320$ ordres différents ; il y a $8 \times 7 \times 6 = 336$ podiums possibles.

3. Combinaisons

Une combinaison de $k$ éléments d'un ensemble $E$ à $n$ éléments est une partie de $E$ à $k$ éléments (l'ordre ne compte pas). Leur nombre est noté $\dbinom{n}{k}$ (« $k$ parmi $n$ ») : $$\binom{n}{k} = \frac{n!}{k!\,(n - k)!} = \frac{n(n-1)\cdots(n - k + 1)}{k!}.$$

Justification : chaque partie à $k$ éléments peut être ordonnée de $k!$ façons, donc $\binom{n}{k} \times k! = \frac{n!}{(n-k)!}$.

$\dbinom{n}{0} = \dbinom{n}{n} = 1$ ; $\;\dbinom{n}{1} = n$ ; $\;\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ ; $\;\dbinom{n}{k} = \dbinom{n}{n - k}$ (choisir les $k$ éléments pris, c'est choisir les $n - k$ laissés).

Un ensemble à $n$ éléments possède $2^n$ parties. Par conséquent : $\;\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$.

Notons $E = \{e_1, \dots, e_n\}$. À chaque partie $A$ de $E$, on associe le n-uplet $(c_1, \dots, c_n) \in \{0\,;\,1\}^n$ où $c_i = 1$ si $e_i \in A$ et $c_i = 0$ sinon. Cette correspondance est une bijection (chaque n-uplet définit une et une seule partie).

Donc le nombre de parties est $\mathrm{Card}(\{0\,;\,1\}^n) = 2^n$.

Par ailleurs, en classant les parties selon leur nombre d'éléments $k$ (de 0 à $n$), cas disjoints, le principe additif donne $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}$ parties. D'où l'égalité. $\blacksquare$

Pour tous entiers $1 \leqslant k \leqslant n - 1$ : $\quad\dbinom{n}{k} = \dbinom{n - 1}{k - 1} + \dbinom{n - 1}{k}$.

Méthode combinatoire. Soit $E$ un ensemble à $n$ éléments et $a$ un élément fixé de $E$. Les parties à $k$ éléments de $E$ se répartissent en deux catégories disjointes :

celles qui contiennent $a$ : on complète $a$ par $k - 1$ éléments choisis parmi les $n - 1$ autres, soit $\binom{n-1}{k-1}$ parties ;
celles qui ne contiennent pas $a$ : on choisit les $k$ éléments parmi les $n - 1$ autres, soit $\binom{n-1}{k}$ parties.

Le principe additif donne la relation.

Méthode par le calcul. $\dbinom{n-1}{k-1} + \dbinom{n-1}{k} = \dfrac{(n-1)!}{(k-1)!\,(n-k)!} + \dfrac{(n-1)!}{k!\,(n-1-k)!} = \dfrac{(n-1)!}{k!\,(n-k)!}\big(k + (n - k)\big) = \dfrac{n!}{k!\,(n-k)!} = \dbinom{n}{k}$. $\blacksquare$

4. Méthode

	L'ordre compte	L'ordre ne compte pas
Répétitions possibles	k-uplets : $n^k$	(hors programme)
Sans répétition	$\dfrac{n!}{(n-k)!}$ (et $n!$ si $k = n$)	combinaisons : $\dbinom{n}{k}$

Mains de 5 cartes dans un jeu de 32 : $\binom{32}{5} = 201\,376$. Mains contenant exactement 2 as : $\binom{4}{2} \times \binom{28}{3} = 6 \times 3\,276 = 19\,656$ (on choisit les as, puis les autres cartes).

def permutations(L):
    if len(L) <= 1:
        return [L]
    res = []
    for i in range(len(L)):
        for p in permutations(L[:i] + L[i+1:]):
            res.append([L[i]] + p)
    return res

def parties2(L):
    return [(L[i], L[j]) for i in range(len(L)) for j in range(i + 1, len(L))]

def ligne_pascal(n):
    ligne = [1]
    for k in range(n):
        ligne = [1] + [ligne[i] + ligne[i+1] for i in range(len(ligne) - 1)] + [1]
    return ligne

print(permutations(['A', 'B', 'C']))
print(parties2(['A', 'B', 'C', 'D']))
print(ligne_pascal(6))

Le triangle « de Pascal » était connu bien avant Pascal (1654) : chez al-Karaji (X^e siècle), en Chine chez Yang Hui (XIII^e siècle) ou en Inde. Pascal en fait l'étude systématique et l'utilise pour les probabilités.

Méthodes à connaître

L'ordre compte-t-il ? Les répétitions sont-elles possibles ?
Ordre et répétitions : $n^k$ ($k$-uplets). Ordre sans répétition : $\frac{n!}{(n - k)!}$ (arrangements), $n!$ pour ordonner tout l'ensemble.
Sans ordre ni répétition : $\binom nk$ (combinaisons).
Principe multiplicatif pour des choix successifs, additif pour des cas disjoints ; « au moins un » : passe par le complémentaire.

Mini-jeux

Exercices

Un digicode comporte 3 lettres parmi A, B, C, D suivies de 2 chiffres. Combien de codes possibles ? Combien si les lettres doivent être distinctes ?

Réponse 1 :

$4^3 \times 10^2 = 6\,400$. Lettres distinctes : $4 \times 3 \times 2 \times 100 = 2\,400$.

Calculer $\binom{7}{3}$, $\binom{10}{2}$, $\binom{20}{18}$, $\binom{12}{0}$.

35 ; 45 ; $\binom{20}{2} = 190$ ; 1.

Dans une classe de 30 élèves, combien de façons d'élire 2 délégués (rôles identiques) ? Un délégué et un suppléant ?

$\binom{30}{2} = 435$ ; $30 \times 29 = 870$ (l'ordre compte).

Combien d'anagrammes (mots, même sans sens) peut-on former avec les lettres de MATHS ? de LYCEE ?

MATHS : 5 lettres distinctes, $5! = 120$. LYCEE : on place les deux E : $\binom{5}{2} = 10$ façons, puis les 3 autres lettres : $3! = 6$ ; total 60 (ou $\frac{5!}{2!}$).

Sur un quadrillage, on va de $(0\,;\,0)$ à $(5\,;\,3)$ par des pas « droite » ou « haut ». Combien de chemins ?

Un chemin est un mot de 8 lettres contenant 3 « H » : $\binom{8}{3} = 56$.

Combien de mains de 5 cartes (jeu de 32) contiennent au moins un roi ?

Complémentaire : aucune carte parmi les 4 rois : $\binom{28}{5} = 98\,280$. Donc $201\,376 - 98\,280 = 103\,096$.

En développant $(a + b)^n = (a + b)(a + b)\cdots(a + b)$, justifier que le coefficient de $a^kb^{n-k}$ est $\binom{n}{k}$. En déduire $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ et $\sum_{k=0}^n (-1)^k\binom{n}{k} = 0$.

Pour obtenir $a^kb^{n-k}$, on choisit dans quels $k$ facteurs on prend $a$ : $\binom{n}{k}$ façons. Avec $a = b = 1$ : $2^n$ ; avec $a = -1$, $b = 1$ : $0^n = 0$ (pour $n \geqslant 1$).