Combinatoire et dénombrement — fiche résumé
L'essentiel du chapitre en une page : 12 points à retenir et 6 méthodes. À relire avant un contrôle, ou à imprimer.
À retenir
1. Ensembles finis et cardinal
Définitions
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.
Principe additif
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|.
2. Produit cartésien et principe multiplicatif
Définition
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|.
Principe multiplicatif
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.
3. k-uplets et arrangements
Propriété
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.
Définition
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)!.
4. Factorielle et permutations
Définition
Pour tout entier n ≥ 1, la factorielle de n est n! = 1 × 2 × … × n. Par convention, 0! = 1.
Permutations
Une permutation d'un ensemble à n éléments est un rangement ordonné de tous ses éléments. Le nombre de permutations est n!.
5. Combinaisons et coefficients binomiaux
Définition
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.
Identités fondamentales
- 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.
Nombre de parties et mots binaires
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.
6. Binôme de Newton (approfondissement)
Formule du binômeapprofondissement
Pour tous réels a, b et tout entier naturel n :
(a + b)n = ∑k=0n C(n,k) an−kbk.
Les méthodes
Ce qu'il faut savoir faire, et dans quel ordre.
Méthode 1Justification de la formule
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.
Méthode 2Démonstration
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!.
Méthode 3
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).
Méthode 4Démonstration combinatoire de la relation de Pascal
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.
Méthode 5Choisir le bon modèle de dénombrement
- 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.
Méthode 6Erreurs fréquentes
- 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.
Le cours en détail, avec les exemples → 8 exercices corrigés