Combinatoire et dénombrement — cours de Terminale
Ensembles finis et cardinal, Produit cartésien et principe multiplicatif, k-uplets et arrangements, Factorielle et permutations Lecture ≈ 5 min.
1. Ensembles finis et cardinal
Un ensemble est fini lorsqu'il possède un nombre fini d'éléments. Son cardinal, noté Card(E) ou |E|, est ce nombre d'éléments. La réunion A ∪ B contient les éléments appartenant à au moins l'un des ensembles ; l'intersection A ∩ B contient ceux qui appartiennent aux deux. Deux ensembles sont disjoints si leur intersection est vide.
Si A et B sont finis et disjoints, alors |A ∪ B| = |A| + |B|. Dans le cas général :
|A ∪ B| = |A| + |B| − |A ∩ B|.
En additionnant |A| et |B|, chaque élément de l'intersection est compté deux fois. Retrancher |A ∩ B| le ramène à un seul comptage. C'est le principe d'inclusion-exclusion pour deux ensembles.
Dans une classe de 35 élèves, 22 étudient l'espagnol, 16 l'allemand et 8 les deux langues. Le nombre d'élèves étudiant au moins une des deux langues vaut 22 + 16 − 8 = 30. Il reste donc 35 − 30 = 5 élèves qui n'étudient aucune des deux.
2. Produit cartésien et principe multiplicatif
Le produit cartésien A × B est l'ensemble des couples (a ; b) avec a ∈ A et b ∈ B. Si A et B sont finis, alors |A × B| = |A| × |B|.
Une procédure comportant p étapes successives, avec n1 choix à la première étape, n2 à la deuxième, ..., np à la dernière, possède n1n2…np issues, à condition que le nombre de choix annoncé à chaque étape ne dépende pas des choix précédents.
Un code contient deux lettres, suivies de trois chiffres. Les répétitions sont autorisées.
- Chacune des deux positions alphabétiques offre 26 choix.
- Chacune des trois positions numériques offre 10 choix.
- Il existe donc 262 × 103 = 676 000 codes.
Si les deux lettres doivent être différentes, le premier choix reste 26 mais le second devient 25 : on obtient 26 × 25 × 103 = 650 000.
3. k-uplets et arrangements
Si un ensemble E contient n éléments, le nombre de k-uplets d'éléments de E, avec répétitions possibles et ordre pris en compte, est nk.
Un arrangement de k éléments parmi n est une liste ordonnée de k éléments distincts choisis parmi n. Il y en a :
n(n − 1)…(n − k + 1) = n!/(n − k)!.
Pour attribuer les médailles d'or, d'argent et de bronze à 12 finalistes, il faut choisir trois personnes distinctes et l'ordre compte. Il y a 12 × 11 × 10 = 1320 podiums.
4. Factorielle et permutations
Pour tout entier n ≥ 1, la factorielle de n est n! = 1 × 2 × … × n. Par convention, 0! = 1.
Une permutation d'un ensemble à n éléments est un rangement ordonné de tous ses éléments. Le nombre de permutations est n!.
Pour remplir la première place, il y a n choix. Une fois ce choix effectué, il reste n − 1 choix pour la deuxième place, puis n − 2, jusqu'à un seul choix. Le principe multiplicatif donne n(n − 1)…1 = n!.
Combien d'anagrammes du mot BANANE ? Les six lettres auraient 6! ordres si elles étaient toutes distinctes. Mais les deux A sont indiscernables et les deux N aussi. Chaque mot a été compté 2! × 2! fois. Le nombre recherché est donc 6!/(2! × 2!) = 180. Cette formule de permutations avec répétitions est une application, non une nouvelle notion à mémoriser isolément.
5. Combinaisons et coefficients binomiaux
Une combinaison de k éléments parmi n est une partie à k éléments d'un ensemble à n éléments : l'ordre ne compte pas et aucun élément ne se répète. Son nombre est le coefficient binomial :
C(n,k) = n!/[k!(n − k)!], pour 0 ≤ k ≤ n.
Les arrangements comptent les listes ordonnées : n!/(n − k)!. Une même partie de k éléments apparaît dans chacun de ses k! ordres. En divisant par k!, on obtient C(n,k).
- C(n,0) = C(n,n) = 1 ; C(n,1) = C(n,n − 1) = n.
- Symétrie : C(n,k) = C(n,n − k).
- Relation de Pascal : C(n,k) = C(n − 1,k − 1) + C(n − 1,k), pour 1 ≤ k ≤ n − 1.
- Somme d'une ligne : ∑k=0n C(n,k) = 2n.
Un ensemble à n éléments possède 2n parties. En effet, pour construire une partie, chacun des n éléments offre deux choix indépendants : être retenu (codé 1) ou non (codé 0). Les parties sont donc en bijection avec les mots binaires de longueur n, au nombre de 2n. En regroupant les parties selon leur cardinal, on retrouve ∑k=0nC(n,k) = 2n.
Dans un groupe de n personnes, fixons Alice. Une équipe de k personnes contient Alice ou ne la contient pas. Avec Alice, on choisit les k − 1 autres parmi n − 1 : C(n − 1,k − 1) possibilités. Sans Alice, on choisit les k membres parmi les n − 1 autres : C(n − 1,k). Les deux cas sont disjoints et couvrent toutes les équipes.
6. Binôme de Newton (approfondissement)
Pour tous réels a, b et tout entier naturel n :
(a + b)n = ∑k=0n C(n,k) an−kbk.
(2x − 1)4 = ∑k=04 C(4,k)(2x)4−k(−1)k.
La ligne 4 du triangle de Pascal est 1, 4, 6, 4, 1. Ainsi :
(2x − 1)4 = 16x4 − 32x3 + 24x2 − 8x + 1.
- L'ordre intervient-il ? Si non, penser aux combinaisons.
- Les répétitions sont-elles autorisées ? Si oui et si l'ordre intervient, penser aux k-uplets.
- Tous les éléments sont-ils rangés ? Si oui, penser aux permutations.
- Le problème se décompose-t-il en cas disjoints ? Additionner. En étapes successives ? Multiplier.
- Pour « au moins un », il est souvent plus simple de compter le complément : total − aucun.
- Utiliser C(n,k) quand l'ordre compte : un podium n'est pas un groupe.
- Écrire nk alors qu'une répétition est interdite.
- Ajouter des nombres de choix correspondant à des étapes successives au lieu de les multiplier.
- Oublier que C(n,k) n'a de sens combinatoire que pour 0 ≤ k ≤ n.