Cours et exercices corrigés de terminale : Dénombrement et combinatoire : k-uplets, arrangements, permutations et combinaisons

1. Principes additif et multiplicatif

Soient $A$ et $B$ deux ensembles finis ; on note $\text{Card}(A)$ le nombre d'éléments de $A$.

• Principe additif : si $A$ et $B$ sont disjoints ($A \cap B = \emptyset$), alors $\text{Card}(A \cup B) = \text{Card}(A) + \text{Card}(B)$. On l'utilise pour découper un problème en cas qui ne se recouvrent pas.
• Principe multiplicatif : le produit cartésien $A \times B$ (ensemble des couples $(a ; b)$) a pour cardinal $\text{Card}(A) \times \text{Card}(B)$. On l'utilise pour des choix successifs : s'il y a $p$ choix pour une première étape puis $q$ choix pour la seconde, il y a $p \times q$ issues.
• Complémentaire : si $A \subset E$, $\text{Card}(\overline{A}) = \text{Card}(E) - \text{Card}(A)$ ; très utile pour les conditions « au moins un ».

2. $k$-uplets : l'ordre compte, répétitions permises

Soit $E$ un ensemble à $n$ éléments et $k \ge 1$ un entier.

• Un $k$-uplet (ou $k$-liste) de $E$ est une liste ordonnée $(x_1 ; x_2 ; \dots ; x_k)$ d'éléments de $E$, non nécessairement distincts.
• Propriété : il y a $n^k$ $k$-uplets de $E$ (chaque position offre $n$ choix).
• Exemples : codes à $4$ chiffres : $10^4 = 10\,000$ ; tirages successifs avec remise de $3$ boules parmi $8$ : $8^3 = 512$ ; mots de $5$ lettres : $26^5$.

3. Arrangements et permutations : l'ordre compte, sans répétition

• Pour $n \in \mathbb{N}$, factorielle $n$ : $n! = 1 \times 2 \times \dots \times n$, avec la convention $0! = 1$.
• Un arrangement de $k$ éléments de $E$ ($k \le n$) est un $k$-uplet d'éléments deux à deux distincts. Leur nombre est

$$n \times (n-1) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!}$$

• Une permutation de $E$ est un arrangement de ses $n$ éléments : il y en a $n!$.
• Exemples : podiums (or, argent, bronze) dans une course de $10$ coureurs : $10 \times 9 \times 8 = 720$ ; manières de ranger $6$ livres : $6! = 720$ ; tirages successifs sans remise de $3$ boules parmi $8$ : $8 \times 7 \times 6 = 336$.

4. Combinaisons : l'ordre ne compte pas, sans répétition

• Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments (un sous-ensemble, sans ordre).
• Le nombre de combinaisons est le coefficient binomial $\binom{n}{k}$ (« $k$ parmi $n$ ») :

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n \times (n-1) \times \dots \times (n-k+1)}{k!}$$

• Justification : chaque partie à $k$ éléments donne $k!$ arrangements (en ordonnant ses éléments), donc $\binom{n}{k} \times k! = \frac{n!}{(n-k)!}$.
• Valeurs utiles : $\binom{n}{0} = \binom{n}{n} = 1$, $\binom{n}{1} = n$, $\binom{n}{2} = \frac{n(n-1)}{2}$.
• Exemples : mains de $5$ cartes dans un jeu de $32$ : $\binom{32}{5} = 201\,376$ ; tirages simultanés de $3$ boules parmi $8$ : $\binom{8}{3} = 56$.
• Le lien avec la loi binomiale (nombre de chemins à $k$ succès dans un arbre) est développé dans le chapitre TS1.

5. Symétrie, relation de Pascal et triangle de Pascal

• Symétrie : $\binom{n}{k} = \binom{n}{n-k}$ (choisir les $k$ éléments pris revient à choisir les $n-k$ éléments laissés).
• Relation de Pascal : pour $1 \le k \le n - 1$,

$$\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}$$
Preuve combinatoire : on fixe un élément $a$ de $E$. Les parties à $k$ éléments contenant $a$ sont au nombre de $\binom{n-1}{k-1}$, celles qui ne le contiennent pas au nombre de $\binom{n-1}{k}$ ; ces deux cas sont disjoints.

• Triangle de Pascal : chaque coefficient est la somme des deux coefficients situés juste au-dessus (au-dessus et au-dessus à gauche) :

6. Nombre de parties d'un ensemble et calcul en Python

• Un ensemble à $n$ éléments possède $2^n$ parties (chaque élément est pris ou non : $2 \times 2 \times \dots \times 2$).
• En regroupant les parties selon leur nombre d'éléments : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.
• Calcul des coefficients binomiaux par la relation de Pascal :

def pascal(n):
    ligne = [1]
    for i in range(n):
        nouvelle = [1]
        for k in range(1, len(ligne)):
            nouvelle.append(ligne[k - 1] + ligne[k])
        nouvelle.append(1)
        ligne = nouvelle
    return ligne

pascal(4) renvoie [1, 4, 6, 4, 1], et la somme de cette liste vaut $2^4 = 16$. Le module math fournit aussi factorial(n) et comb(n, k).

7. Démonstration : un ensemble à $n$ éléments possède $2^n$ parties

Soit $E = \{e_1 ; e_2 ; \dots ; e_n\}$.

• Par les $n$-uplets : à chaque partie $A$ de $E$, on associe le $n$-uplet $(c_1 ; \dots ; c_n)$ de $\{0 ; 1\}^n$ où $c_i = 1$ si $e_i \in A$ et $c_i = 0$ sinon. Chaque partie donne un unique $n$-uplet et chaque $n$-uplet provient d'une unique partie : il y a autant de parties que de $n$-uplets de $\{0 ; 1\}$, soit $2^n$ (principe multiplicatif).
• Par les tailles : pour chaque $k \in \{0, 1, \dots, n\}$, il y a $\binom{n}{k}$ parties à $k$ éléments, et ces cas sont disjoints. Le principe additif donne $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.

Exemple : $E = \{a ; b ; c\}$ a $2^3 = 8$ parties : $\emptyset$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a ; b\}$, $\{a ; c\}$, $\{b ; c\}$ et $E$ ; on retrouve $1 + 3 + 3 + 1 = 8$.

8. Démonstration : relation de Pascal par le calcul

Pour $1 \le k \le n - 1$ :
$$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!}$$
On réduit au même dénominateur $k!\,(n-k)!$ en utilisant $k! = k \times (k-1)!$ et $(n-k)! = (n-k) \times (n-k-1)!$ :
$$= \frac{(n-1)! \times k + (n-1)! \times (n-k)}{k!\,(n-k)!} = \frac{(n-1)! \times n}{k!\,(n-k)!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}$$
La preuve combinatoire (par dénombrement) est donnée au point 5.

9. Algorithmes : parties à deux éléments et permutations

def parties_2(E):
    L = []
    for i in range(len(E)):
        for j in range(i + 1, len(E)):
            L.append([E[i], E[j]])
    return L

def permutations(E):
    L = [[]]
    for x in E:
        nouvelle = []
        for p in L:
            for i in range(len(p) + 1):
                nouvelle.append(p[:i] + [x] + p[i:])
        L = nouvelle
    return L

parties_2(['a', 'b', 'c', 'd']) renvoie les $\binom{4}{2} = 6$ paires ; permutations([1, 2, 3]) renvoie les $3! = 6$ permutations (chaque nouvel élément est inséré à toutes les places possibles). Pour tirer une permutation au hasard, on peut utiliser la fonction shuffle du module random.