Résumé — Combinatoire et dénombrement

Ce résumé condense l’exigible du chapitre. Tout dénombrement commence par deux questions : l’ordre intervient-il ? Les répétitions sont-elles autorisées ? Les réponses déterminent le modèle.

Les deux principes de base

Principe additif

$\text{Card}(A \cup B) = \text{Card}\,A + \text{Card}\,B$

Valable si A et B sont DISJOINTS. Sinon : Card(A∪B) = Card A + Card B − Card(A∩B).

Principe multiplicatif

$\text{Card}(A \times B) = \text{Card}\,A \times \text{Card}\,B$

Pour des choix successifs indépendants — le principe qui fonde tous les arbres de dénombrement.

Les quatre modèles

k-uplet (ordre, répétitions autorisées) : $n^k$ listes — les codes PIN, les mots de k lettres.
k-uplet d’éléments distincts (ordre, sans répétition) : $n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}$ — les podiums, les tiercés.
Permutation (ranger tous les éléments) : $n!$ — les anagrammes, les files d’attente. Rappel : $n! = 1 \times 2 \times \cdots \times n$ , et $0! = 1$ .
Combinaison (l’ordre ne compte pas, sans répétition) : choisir une partie à $k$ éléments — les mains de cartes, les délégations.

Le coefficient binomial

« k parmi n »

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

Nombre de parties à k éléments d’un ensemble à n éléments. Cas usuels : (n choose 0) = 1, (n choose 1) = n, (n choose 2) = n(n−1)/2.

Symétrie et Pascal

$\binom{n}{k} = \binom{n}{n-k} \qquad \binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}$

La relation de Pascal engendre le triangle : chaque coefficient est la somme des deux au-dessus.

Nombre de parties

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Un ensemble à n éléments a 2ⁿ parties : pour chaque élément, on le prend ou non.

Les démonstrations exigibles

$\sum \binom{n}{k} = 2^n$ : on compte les parties de deux manières — d’une part chaque élément est pris ou non ( $2^n$ ), d’autre part on trie les parties selon leur nombre $k$ d’éléments ( $\binom{n}{k}$ chacune, familles disjointes).
Relation de Pascal : on fixe un élément $a$ ; les parties à $k$ éléments se répartissent en celles qui contiennent $a$ ( $\binom{n-1}{k-1}$ ) et celles qui ne le contiennent pas ( $\binom{n-1}{k}$ ) — deux familles disjointes.

Les pièges classiques

Les réflexes qui sauvent

Se demander d’abord si l’ordre intervient, puis si les répétitions sont autorisées. Le principe additif exige des ensembles disjoints. Et « k parmi n » se note $\binom{n}{k}$ : le grand nombre en haut.

La phrase qui résume tout

Sans ordre et sans répétition, on compte des parties, donc des coefficients binomiaux. Avec ordre, on compte des listes : $n^k$ avec répétitions, $\frac{n!}{(n-k)!}$ sans.