Terminale⏱ 4 séances

Combinatoire et dénombrement

Ce que tu vas apprendre

Utiliser les principes additif et multiplicatif et le produit cartésien
Dénombrer les k-uplets d'un ensemble à n éléments et les parties d'un ensemble
Dénombrer les k-uplets d'éléments distincts et les permutations (factorielle)
Dénombrer les combinaisons et calculer des coefficients binomiaux
Démontrer la relation de Pascal et la somme des coefficients binomiaux
Choisir le bon modèle (ordre, répétitions) pour résoudre un problème de dénombrement

Notions cléscardinal d'un ensembleprincipe additif, principe multiplicatifproduit cartésien, k-uplet2^n partiesfactorielle n!k-uplets d'éléments distinctscombinaisons, coefficient binomialrelation et triangle de Pascal

Ce que tu sais déjà. Tu as dénombré des issues avec des arbres et des tableaux à double entrée pour calculer des probabilités (Seconde — Probabilités) et utilisé le vocabulaire des ensembles (réunion, intersection, produit cartésien). Tu sais manipuler des listes en Python (Première — Listes en Python). On apprend ici à compter sans tout énumérer.

1. Principes additif et multiplicatif

Cardinal. Le nombre d’éléments d’un ensemble fini $E$ est son cardinal, noté $\mathrm{Card}(E)$ .

Principe additif. Si $A$ et $B$ sont deux ensembles finis disjoints ( $A \cap B = \varnothing$ ), alors $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B)$ . (Plus généralement, $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B) - \mathrm{Card}(A \cap B)$ .)

Produit cartésien. $A \times B$ est l’ensemble des couples $(a\,;\,b)$ avec $a \in A$ et $b \in B$ .

Principe multiplicatif. $\mathrm{Card}(A \times B) = \mathrm{Card}(A) \times \mathrm{Card}(B)$ . Plus généralement, si un choix se fait en plusieurs étapes successives avec $n_1$ possibilités, puis $n_2$ , …, puis $n_p$ , le nombre total est $n_1 \times n_2 \times \dots \times n_p$ .

Un menu : 3 entrées, puis 2 plats pour chaque entrée. L'arbre a 3 × 2 = 6 branches complètes, qui correspondent aux 6 couples de l'ensemble produit.

Exemples.

Une cantine propose 3 entrées, 4 plats et 2 desserts : $3 \times 4 \times 2 = 24$ menus différents.

Dans une classe de 14 filles et 13 garçons, on choisit un délégué : $14 + 13 = 27$ choix (principe additif).

→ S’entraîner : Exercice 1

2. k-uplets et parties d’un ensemble

Définition. Soit $E$ un ensemble à $n$ éléments et $k$ un entier naturel non nul. 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$ , les répétitions étant autorisées : c’est un élément de $E^k = E \times E \times \dots \times E$ .

Propriété. Le nombre de $k$ -uplets d’un ensemble à $n$ éléments est $n^k$ .

Exemples.

Un code de carte bancaire à 4 chiffres : $10^4 = 10\,000$ codes possibles.

On lance 3 fois un dé à 6 faces : $6^3 = 216$ résultats (triplets).

Propriété. Un ensemble à $n$ éléments possède $2^n$ parties (sous-ensembles), en comptant l’ensemble vide et l’ensemble lui-même.

Justification. Pour $E = \{e_1, \dots, e_n\}$ , une partie est déterminée par la réponse « oui / non » à la question « $e_i$ est-il dans la partie ? » pour chaque $i$ : c’est un $n$ -uplet de $\{\text{oui}\,;\,\text{non}\}$ , et il y en a $2^n$ .

Exemple. $\{a\,;\,b\,;\,c\}$ a $2^3 = 8$ parties : $\varnothing$ , $\{a\}$ , $\{b\}$ , $\{c\}$ , $\{a\,;\,b\}$ , $\{a\,;\,c\}$ , $\{b\,;\,c\}$ , $\{a\,;\,b\,;\,c\}$ .

→ S’entraîner : Exercice 2

3. k-uplets d’éléments distincts et permutations

Définition. Un $k$ -uplet d’éléments distincts de $E$ est une liste ordonnée de $k$ éléments de $E$ deux à deux distincts (tirage sans remise et avec ordre).

Factorielle. Pour tout entier $n \geqslant 1$ , $n! = 1 \times 2 \times \dots \times n$ (« factorielle $n$ »), et par convention $0! = 1$ . $1! = 1$ , $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , $10! = 3\,628\,800$ .

Propriétés. Soit $E$ un ensemble à $n$ éléments et $1 \leqslant k \leqslant n$ .

Le nombre de $k$ -uplets d’éléments distincts de $E$ est $n \times (n - 1) \times \dots \times (n - k + 1) = \frac{n!}{(n - k)!}.$
Une permutation de $E$ est un $n$ -uplet d’éléments distincts (on range tous les éléments) : il y en a $n!$ .

Justification. $n$ choix pour le premier élément, $n - 1$ pour le deuxième (il doit être différent), …, $n - k + 1$ pour le $k$ -ième : principe multiplicatif.

Exemples.

Podium (or, argent, bronze) d’une course de 10 coureurs : $10 \times 9 \times 8 = 720$ podiums.

Anagrammes du mot MATHS (5 lettres distinctes) : $5! = 120$ .

→ S’entraîner : Exercice 3

4. Combinaisons

Définition. Soit $E$ un ensemble à $n$ éléments et $0 \leqslant k \leqslant n$ . Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments (tirage simultané : sans ordre, sans répétition). Leur nombre se note $\dbinom nk$ (« $k$ parmi $n$ ») : c’est un coefficient binomial.

Propriété. $\binom nk = \frac{n!}{k!\,(n - k)!} = \frac{n \times (n - 1) \times \dots \times (n - k + 1)}{k!}.$

Justification. Chaque combinaison de $k$ éléments peut être ordonnée de $k!$ façons, ce qui donne des $k$ -uplets d’éléments distincts. Donc $\dbinom nk \times k! = \dfrac{n!}{(n - k)!}$ .

Valeurs à connaître. $\dbinom n0 = \dbinom nn = 1$ ; $\dbinom n1 = n$ ; $\dbinom n2 = \dfrac{n(n - 1)}{2}$ ; symétrie : $\dbinom nk = \dbinom n{n - k}$ (choisir les $k$ éléments qu’on garde revient à choisir les $n - k$ qu’on laisse).

Exemples.

Former une délégation de 3 élèves dans une classe de 25 : $\dbinom{25}{3} = \dfrac{25 \times 24 \times 23}{6} = 2\,300$ .

Mains de 5 cartes dans un jeu de 32 : $\dbinom{32}{5} = 201\,376$ .

Propriété (démonstration exigible). Pour tout entier naturel $n$ : $\displaystyle\sum_{k=0}^{n} \binom nk = \binom n0 + \binom n1 + \dots + \binom nn = 2^n$ .

🧠 Démonstration par dénombrement — la somme des coefficients binomiaux vaut 2ⁿ (exigible au programme)

Soit $E$ un ensemble à $n$ éléments. On compte ses parties de deux façons.

D’une part, $E$ a $2^n$ parties (§ 2).
D’autre part, on range les parties selon leur nombre d’éléments $k$ , de $0$ à $n$ . Ces catégories sont disjointes, et il y a $\dbinom nk$ parties à $k$ éléments. Par le principe additif, le nombre total de parties est $\displaystyle\sum_{k=0}^n \binom nk$ .

Les deux décomptes sont égaux : $\displaystyle\sum_{k=0}^n \binom nk = 2^n$ .

→ S’entraîner : Exercice 4 · Exercice 5

5. Relation et triangle de Pascal

Propriété (relation de Pascal). Pour tous entiers $n \geqslant 1$ et $1 \leqslant k \leqslant n - 1$ : $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}.$

🧠 Démonstrations de la relation de Pascal, par le calcul et par dénombrement (exigibles au programme)

Par le calcul. $\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!} = \frac{(n-1)!}{k!\,(n-k)!}\big(k + (n - k)\big) = \frac{n!}{k!\,(n-k)!} = \binom nk,$ en mettant au même dénominateur $k!\,(n-k)!$ (on multiplie la première fraction par $\frac kk$ et la seconde par $\frac{n-k}{n-k}$ ).

Par dénombrement. 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$ : il reste à choisir $k - 1$ éléments parmi les $n - 1$ autres, soit $\dbinom{n-1}{k-1}$ parties ;
celles qui ne contiennent pas $a$ : on choisit $k$ éléments parmi les $n - 1$ autres, soit $\dbinom{n-1}{k}$ parties.

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

Triangle de Pascal. On range les $\dbinom nk$ en tableau : chaque coefficient est la somme de celui qui est au-dessus et de celui qui est au-dessus à gauche.

Le triangle de Pascal jusqu'à n = 7. Exemple de la relation de Pascal : 15 + 20 = 35, c'est-à-dire « 2 parmi 6 » + « 3 parmi 6 » = « 3 parmi 7 ». La somme de la ligne n vaut 2ⁿ.

def ligne_pascal(n):
    """Liste des coefficients binomiaux (n, k) pour k de 0 à n."""
    ligne = [1]
    for i in range(n):
        ligne = [1] + [ligne[k - 1] + ligne[k] for k in range(1, len(ligne))] + [1]
    return ligne

print(ligne_pascal(7))   # [1, 7, 21, 35, 35, 21, 7, 1]

→ S’entraîner : Exercice 6 · Exercice 7

6. Choisir le bon modèle

Situation	L’ordre compte ?	Répétitions ?	Modèle	Nombre
Tirages successifs avec remise	oui	oui	$k$ -uplets	$n^k$
Tirages successifs sans remise	oui	non	$k$ -uplets d’éléments distincts	$\dfrac{n!}{(n-k)!}$
Ranger tous les éléments	oui	non	permutations	$n!$
Tirage simultané (poignée, comité)	non	non	combinaisons	$\dbinom nk$

📋 Méthode — « Au moins un » : passer par le complémentaire

Pour compter les choix contenant au moins un élément d’un certain type, on compte tous les choix, puis on retire ceux qui n’en contiennent aucun.

Exemple : dans une classe de 12 filles et 15 garçons, nombre de groupes de 5 élèves avec au moins une fille : $\dbinom{27}{5} - \dbinom{15}{5} = 80\,730 - 3\,003 = 77\,727$ .

Exemple (chemins). Sur un quadrillage, pour aller du coin $(0\,;\,0)$ au point $(5\,;\,3)$ en ne se déplaçant que vers la droite (D) ou vers le haut (H), on fait 8 pas dont 3 vers le haut. Un chemin est déterminé par le choix des positions des 3 pas « H » parmi les 8 : $\dbinom83 = 56$ chemins.

→ S’entraîner : Exercice 8 · Exercice 9

À retenir.

Principe additif (cas disjoints) ; principe multiplicatif (étapes successives) ; $\mathrm{Card}(A \times B) = \mathrm{Card}(A) \times \mathrm{Card}(B)$ .
$k$ -uplets : $n^k$ ; parties : $2^n$ ; $k$ -uplets distincts : $\dfrac{n!}{(n-k)!}$ ; permutations : $n!$ .
Combinaisons : $\dbinom nk = \dfrac{n!}{k!(n-k)!}$ ; $\dbinom nk = \dbinom n{n-k}$ ; $\displaystyle\sum_k \binom nk = 2^n$ .
Pascal : $\dbinom nk = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ .