Combinatoire et dénombrement en Terminale
Cours complet, points clés à retenir et exercices d'entraînement de combinatoire et dénombrement pour les élèves de Terminale. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Principe additif : réunion d'ensembles deux à deux disjoints
- Principe multiplicatif : produit cartésien, nombre de k-uplets d'un ensemble à n éléments (nᵏ)
- Nombre de parties d'un ensemble à n éléments (2ⁿ) ; lien avec les mots binaires et les chemins d'un arbre
- k-uplets d'éléments distincts ; factorielle n! et permutations
- Combinaisons : parties à k éléments, coefficient binomial (n k)
- Symétrie, relation et triangle de Pascal
- Choisir une représentation adaptée (ensembles, arbres, tableaux, mots, chemins) pour dénombrer
Principe additif
On note $\text{Card}(E)$ le nombre d'éléments (cardinal) d'un ensemble fini $E$. Principe additif : si $A_1, A_2, \dots, A_p$ sont des ensembles finis deux à deux disjoints (aucun élément commun à deux d'entre eux), alors le cardinal de leur réunion est la somme de leurs cardinaux : $\text{Card}(A_1 \cup A_2 \cup \dots \cup A_p) = \text{Card}(A_1) + \text{Card}(A_2) + \dots + \text{Card}(A_p)$.
Exemple
Un cinéma propose ce soir 3 films et 2 documentaires, tous différents. On veut voir une seule séance : il y a $3 + 2 = 5$ choix. Contre-exemple : si 12 élèves font de l'anglais renforcé et 8 du théâtre, on ne peut pas conclure que 20 élèves sont concernés, car un élève peut faire les deux (les ensembles ne sont pas disjoints).
À retenir : On additionne les cardinaux seulement si les ensembles sont deux à deux disjoints (situations « ou » qui s'excluent).
Principe multiplicatif et k-uplets
Le produit cartésien $A \times B$ est l'ensemble des couples $(a ; b)$ avec $a \in A$ et $b \in B$ ; on a $\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B)$ (principe multiplicatif), et cela se généralise à plusieurs ensembles. Un $k$-uplet (ou $k$-liste) d'éléments de $E$ est une liste ordonnée $(x_1 ; x_2 ; \dots ; x_k)$ d'éléments de $E$, avec répétitions possibles : c'est un élément de $E^k = E \times E \times \dots \times E$. Si $E$ a $n$ éléments, il y a $n^k$ tels $k$-uplets.
Exemple
Un menu comprend une entrée parmi 4 et un dessert parmi 3 : il y a $4 \times 3 = 12$ menus (couples). Un code à 4 chiffres, chaque chiffre pouvant aller de 0 à 9, est un 4-uplet de $\{0, 1, \dots, 9\}$ : il y a $10^4 = 10\,000$ codes.
À retenir : Choix successifs indépendants : on multiplie. Nombre de $k$-uplets d'un ensemble à $n$ éléments : $n^k$ (l'ordre compte, les répétitions sont permises).
Nombre de parties d'un ensemble : $2^n$
Un ensemble à $n$ éléments possède $2^n$ parties (sous-ensembles), en comptant l'ensemble vide et l'ensemble lui-même. Justification : on numérote les éléments $x_1, \dots, x_n$ ; à chaque partie, on associe le mot binaire de longueur $n$ dont le $i$-ème caractère vaut 1 si $x_i$ est dans la partie et 0 sinon. Chaque partie correspond à un seul mot et chaque mot à une seule partie ; or il y a $2^n$ mots binaires de longueur $n$ (des $n$-uplets de $\{0 ; 1\}$). C'est aussi le nombre de chemins d'un arbre à $n$ niveaux dont chaque nœud a deux branches (« je prends » / « je ne prends pas »).
Exemple
$E = \{a, b, c\}$ a $2^3 = 8$ parties : $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a, b\}$, $\{a, c\}$, $\{b, c\}$, $\{a, b, c\}$. La partie $\{a, c\}$ correspond au mot binaire 101.
À retenir : Un ensemble à $n$ éléments a $2^n$ parties, autant que de mots binaires de longueur $n$.
k-uplets d'éléments distincts, factorielle et permutations
Si $E$ a $n$ éléments et $1 \leq k \leq n$, le nombre de $k$-uplets d'éléments distincts de $E$ (l'ordre compte, sans répétition) est $n \times (n-1) \times \dots \times (n-k+1)$ : $n$ choix pour le premier, $n - 1$ pour le deuxième, etc. On note $n! = n \times (n-1) \times \dots \times 2 \times 1$ (factorielle $n$), avec $0! = 1$ ; ce nombre s'écrit aussi $\frac{n!}{(n-k)!}$. Une permutation de $E$ est un $n$-uplet d'éléments distincts de $E$ (une façon d'ordonner tous ses éléments) : il y en a $n!$.
Exemple
Ranger 5 livres différents sur une étagère : $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ rangements. Attribuer les médailles d'or, d'argent et de bronze à 3 des 8 finalistes : $8 \times 7 \times 6 = 336$ podiums.
À retenir : $k$-uplets d'éléments distincts : $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$ ; permutations : $n!$.
Combinaisons et coefficient binomial
Une combinaison de $k$ éléments d'un ensemble $E$ à $n$ éléments est une partie de $E$ à $k$ éléments : on choisit sans ordre et sans répétition. Leur nombre se note $\binom{n}{k}$ (lu « $k$ parmi $n$ »). Chaque partie à $k$ éléments peut être ordonnée de $k!$ façons, ce qui donne les $k$-uplets d'éléments distincts ; donc $\binom{n}{k} \times k! = \frac{n!}{(n-k)!}$, soit $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$ pour $0 \leq k \leq n$.
Exemple
Choisir 3 joueurs parmi 10 pour une équipe, sans rôles différents : $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ équipes.
À retenir : $\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}$ ; $\binom{n}{0} = 1$, $\binom{n}{1} = n$, $\binom{n}{2} = \frac{n(n-1)}{2}$.
Symétrie, relation de Pascal et triangle de Pascal
Symétrie : $\binom{n}{k} = \binom{n}{n-k}$, car choisir les $k$ éléments qu'on garde revient à choisir les $n - k$ qu'on laisse. Relation de Pascal : pour $1 \leq k \leq n - 1$, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. Justification : on fixe un élément $a$ de $E$ ; les parties à $k$ éléments qui contiennent $a$ sont au nombre de $\binom{n-1}{k-1}$, celles qui ne le contiennent pas au nombre de $\binom{n-1}{k}$, et ces deux ensembles sont disjoints. Le triangle de Pascal range les $\binom{n}{k}$ ligne par ligne : chaque nombre intérieur est la somme des deux nombres situés au-dessus de lui.
Exemple
Lignes $n = 0$ à $n = 4$ : 1 ; 1 1 ; 1 2 1 ; 1 3 3 1 ; 1 4 6 4 1. Par exemple $\binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6$. La somme des nombres de la ligne 4 vaut $16 = 2^4$ : en comptant les parties selon leur nombre d'éléments, on retrouve $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.
À retenir : $\binom{n}{k} = \binom{n}{n-k}$ ; $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ ; $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.
Choisir une représentation adaptée pour dénombrer
Avant de calculer, on modélise la situation : ensembles (pour appliquer le principe additif), arbre (choix successifs), tableau à double entrée (couples), mots ou chemins. Les questions à se poser : l'ordre compte-t-il ? Les répétitions sont-elles possibles ? Selon les réponses, on compte des $k$-uplets ($n^k$), des $k$-uplets d'éléments distincts ($\frac{n!}{(n-k)!}$) ou des parties ($\binom{n}{k}$).
Exemple
Combien de mots de 5 lettres formés uniquement de A et de B contiennent exactement 2 lettres A ? Un tel mot est entièrement déterminé par les positions des deux A, c'est-à-dire par une partie à 2 éléments de $\{1, 2, 3, 4, 5\}$ : il y en a $\binom{5}{2} = 10$. De même, sur un quadrillage, un chemin de 5 pas formé de 2 pas « haut » et 3 pas « droite » se code par un mot de ce type : il y a 10 chemins.
À retenir : Ordre qui compte + répétitions : $n^k$. Ordre qui compte, sans répétition : $\frac{n!}{(n-k)!}$. Ordre qui ne compte pas, sans répétition : $\binom{n}{k}$.
Les points clés
- Principe additif pour des ensembles deux à deux disjoints ; principe multiplicatif pour un produit cartésien
- Nombre de $k$-uplets d'un ensemble à $n$ éléments : $n^k$ ; nombre de parties : $2^n$
- $k$-uplets d'éléments distincts : $\frac{n!}{(n-k)!}$ ; permutations : $n!$
- Nombre de parties à $k$ éléments : $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$
- Symétrie $\binom{n}{k} = \binom{n}{n-k}$ et relation de Pascal $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
- Bien modéliser (arbre, mots, chemins, ensembles) : l'ordre compte-t-il ? Y a-t-il des répétitions ?
L'essentiel
Dénombrer, c'est modéliser : on additionne pour des cas disjoints, on multiplie pour des choix successifs, puis on choisit le bon objet (k-uplet, k-uplet d'éléments distincts, partie) selon que l'ordre compte et que les répétitions sont permises.
Exercices d'entraînement
Entraîne-toi sur ces exercices, puis fais-toi corriger pas à pas par le tuteur.
Exercice 1
Un restaurant propose 5 entrées, 8 plats et 4 desserts. a) Combien de menus « entrée + plat + dessert » peut-on composer ? b) Le restaurant propose aussi des formules « plat + dessert » (sans entrée). Combien de repas différents un client peut-il commander au total, en choisissant soit un menu complet, soit une formule ?
Corrige cet exercice avec le tuteur →Exercice 2
Dans une classe de 25 élèves, a) combien y a-t-il de façons de choisir un délégué et un suppléant (deux élèves différents) ? b) combien de groupes de 3 élèves peut-on former pour un exposé ? c) combien de sous-ensembles d'élèves (y compris le groupe vide) peut-on former ? (donner le résultat sous forme de puissance)
Corrige cet exercice avec le tuteur →