Fiche de cours Logimaths | Terminale spécialité
Fiche de cours : Combinatoire et dénombrement
Compter sans énumérer : k-uplets, arrangements, permutations, combinaisons
I. Les deux principes de base
Cardinal, principe additif
Le cardinal d'un ensemble fini E, noté \text{Card}(E), est son nombre d'éléments.
Principe additif : si des ensembles sont deux à deux disjoints (aucun élément commun), le cardinal de leur réunion est la somme des cardinaux.
S'ils ne sont pas disjoints, on passe par un diagramme pour ne rien compter deux fois : 16 latinistes, 14 théâtreux dont 5 font les deux et 8 ne font rien donnent 11 + 5 + 9 + 8 = 33 élèves.
Principe additif : si des ensembles sont deux à deux disjoints (aucun élément commun), le cardinal de leur réunion est la somme des cardinaux.
S'ils ne sont pas disjoints, on passe par un diagramme pour ne rien compter deux fois : 16 latinistes, 14 théâtreux dont 5 font les deux et 8 ne font rien donnent 11 + 5 + 9 + 8 = 33 élèves.
Principe multiplicatif
Pour compter des listes de choix successifs indépendants, on multiplie les nombres de possibilités : \text{Card}(E_1 \times E_2 \times \dots \times E_p) = \text{Card}(E_1) \times \dots \times \text{Card}(E_p).
Exemple : 3 entrées, 4 plats, 2 desserts : 3 \times 4 \times 2 = 24 menus.
Exemple : 3 entrées, 4 plats, 2 desserts : 3 \times 4 \times 2 = 24 menus.
🎮 Entraîne-toi : le principe multiplicatif
Un choix, PUIS un autre, PUIS un autre : on multiplie.
II. k-uplets et permutations : quand l'ordre compte
k-uplets : ordre ET répétitions
Un k-uplet d'un ensemble à n éléments est une liste ordonnée de k éléments, répétitions autorisées. Il y en a n^k.
Exemple : un code de 4 chiffres : {10^4 = 10\,000} possibilités.
Exemple : un code de 4 chiffres : {10^4 = 10\,000} possibilités.
Factorielle et permutations
Factorielle n : n! = 1 \times 2 \times \dots \times n (et 0! = 1 par convention). Ainsi 5! = 120.
Une permutation range TOUS les n éléments dans un ordre : il y en a n! (n choix pour la première place, n − 1 pour la deuxième, etc.).
Une permutation range TOUS les n éléments dans un ordre : il y en a n! (n choix pour la première place, n − 1 pour la deuxième, etc.).
Arrangements : ordre SANS répétition
Un k-uplet d'éléments distincts (arrangement de k parmi n) est une liste ordonnée sans répétition : il y en a n \times (n-1) \times \dots \times (n - k + 1) = \dfrac{n!}{(n-k)!}.
Exemple : un podium (or, argent, bronze) parmi 8 coureurs : {8 \times 7 \times 6 = 336}.
Exemple : un podium (or, argent, bronze) parmi 8 coureurs : {8 \times 7 \times 6 = 336}.
🎮 Entraîne-toi : permutations et factorielles
Ranger n objets tous différents : n! façons.
🎮 Entraîne-toi : codes et podiums
Répétitions permises → n^k ; interdites → n × (n−1) × …
III. Les combinaisons : quand l'ordre ne compte pas
Combinaison et coefficient binomial
Une combinaison de k éléments de E est un sous-ensemble à k éléments : ni ordre, ni répétition. Leur nombre est le coefficient binomial : \binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}.
Lecture : on compte les arrangements \frac{n!}{(n-k)!} puis on divise par k! car les k! ordres d'un même sous-ensemble ne comptent qu'une fois.
Cas particuliers : \begin{aligned}\binom{n}{0} &= \binom{n}{n} \\ &= 1\end{aligned} et \binom{n}{1} = n.
Lecture : on compte les arrangements \frac{n!}{(n-k)!} puis on divise par k! car les k! ordres d'un même sous-ensemble ne comptent qu'une fois.
Cas particuliers : \begin{aligned}\binom{n}{0} &= \binom{n}{n} \\ &= 1\end{aligned} et \binom{n}{1} = n.
Le bon modèle en trois questions
- L'ordre compte-t-il ? Les répétitions sont-elles permises ?
- ordre + répétitions : k-uplets, n^k (codes, lancers successifs) ;
- ordre sans répétition : arrangements, \frac{n!}{(n-k)!} (podiums, tiercés) ;
- ni ordre ni répétition : combinaisons, \binom{n}{k} (mains de cartes, délégations, loto).
⚠️ Délégué ≠ podium
Choisir 3 délégués parmi 20 (aucun rôle distinct) : \binom{20}{3} = 1140. Choisir un président, un secrétaire et un trésorier : 20 \times 19 \times 18 = 6840. Même tirage, mais les rôles créent de l'ordre : facteur {3! = 6} entre les deux.
🎮 Entraîne-toi : les combinaisons
Sous-ensembles sans ordre : le coefficient binomial fait le travail.
IV. Symétrie et triangle de Pascal
Deux propriétés à connaître
- Symétrie : \binom{n}{k} = \binom{n}{n-k} (choisir les k élus, c'est choisir les n − k recalés) : ainsi \begin{aligned}\binom{25}{24} &= \binom{25}{1} \\ &= 25\end{aligned}
- Triangle de Pascal : {\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}} : chaque case du triangle est la somme des deux cases au-dessus, ce qui permet de calculer tous les coefficients de proche en proche (1 ; 1 1 ; 1 2 1 ; 1 3 3 1 ; 1 4 6 4 1…).
▶ 🎓 Démonstration au programme (exigible) : la relation de Pascal, version « dénombrement »
On compte les parties à k + 1 éléments d'un ensemble à n + 1 éléments, en isolant un élément particulier a :
(La preuve calculatoire par les factorielles, en réduisant au même dénominateur, est aussi exigible.)
- celles qui contiennent a : il reste k éléments à choisir parmi n, soit \binom{n}{k} ;
- celles qui ne contiennent pas a : k + 1 éléments à choisir parmi n, soit \binom{n}{k+1}.
(La preuve calculatoire par les factorielles, en réduisant au même dénominateur, est aussi exigible.)
👆 ▶ À toi : calcule C(6, 2) avec la formule, puis retrouve-le dans le triangle de Pascal. Vérifie
\begin{aligned}\binom{6}{2} &= \dfrac{6 \times 5}{2!} \\ &= 15\end{aligned}
Ligne 6 du triangle : 1 ; 6 ; 15 ; 20 ; 15 ; 6 ; 1 ✔ (et la symétrie donne aussi \binom{6}{4} = 15).
Ligne 6 du triangle : 1 ; 6 ; 15 ; 20 ; 15 ; 6 ; 1 ✔ (et la symétrie donne aussi \binom{6}{4} = 15).