Cours · Combinatoire et dénombrement

5 hPrérequis : ensembles, arbres de choix, raisonnement par récurrence.

Combien de codes PIN différents existe-t-il ? Combien de podiums possibles dans une course de 10 coureurs ? Combien de groupes de 3 élèves dans une classe de 30 ? Dénombrer, c'est répondre à ce genre de question sans tout écrire.

Tout le chapitre repose sur deux réflexes :

quand on sépare en cas qui ne se recouvrent pas, on additionne ;
quand on enchaîne des choix, on multiplie.

Le reste consiste à reconnaître la bonne situation : l'ordre compte-t-il, les répétitions sont-elles permises ?

1. Les deux règles de base

Additionner : séparer en cas

Une classe compte 12 filles et 15 garçons. Personne n'est à la fois fille et garçon, donc la classe compte $12+15=27$ élèves. C'est le principe additif.

Multiplier : enchaîner des choix

Un menu se compose d'une entrée, d'un plat et d'un dessert. Pour chaque entrée, on a le même nombre de plats possibles, et pour chaque couple (entrée, plat), le même nombre de desserts. L'arbre ci-dessous montre pourquoi le nombre total de menus est un produit. Change le nombre de choix à chaque étape.

Entrées3

Plats4

Desserts2

3 × 4 × 2 = 24 menus

Chaque chemin de la racine à une feuille est un menu. À chaque étape, chaque branche se divise de la même façon : le nombre de feuilles est le produit des nombres de choix.

Un menu est un triplet (entrée, plat, dessert) : c'est un élément d'un produit cartésien.

2. Les listes avec répétition

Un code PIN, c'est 4 chiffres écrits dans un ordre précis, et un même chiffre peut revenir : 0 0 7 2 est un code valable, différent de 7 2 0 0. C'est une liste, qu'on appelle un $k$ -uplet.

Pour remplir chacune des $k$ cases, on a à chaque fois les $n$ éléments de $E$ à disposition. Le principe multiplicatif donne $n\times n\times\dots\times n$ .

Combien de parties a un ensemble ?

Une partie de $E$ (ou sous-ensemble) s'obtient en décidant, pour chaque élément, s'il est dedans ou dehors. On peut coder cette décision par 1 ou 0 : une partie devient alors une liste de 0 et de 1.

Partie : { a, c } · code : 1010

Touche un élément pour le mettre dedans (1) ou dehors (0). Avec 4 éléments, il y a 2 × 2 × 2 × 2 = 16 codes, donc 16 parties de E = {a, b, c, d}.

Démonstration

Notons $E=\{x_1,\dots,x_n\}$ . À toute partie $A$ de $E$ , on associe le $n$ -uplet $(\varepsilon_1,\dots,\varepsilon_n)$ de $\{0\,;1\}^n$ défini par

\varepsilon_i=\begin{cases}1 & \text{si } x_i\in A,\\ 0 & \text{si } x_i\notin A.\end{cases}

Réciproquement, tout $n$ -uplet de $\{0\,;1\}^n$ définit une unique partie : celle formée des $x_i$ tels que $\varepsilon_i=1$ . On a donc une correspondance un à un (une bijection) entre $\Parties(E)$ et $\{0\,;1\}^n$ . Les deux ensembles ont le même cardinal :

\Card\big(\Parties(E)\big)=\Card\big(\{0\,;1\}^n\big)=2^n.

3. Les listes sans répétition

Pour un podium, le premier, le deuxième et le troisième sont trois coureurs différents. L'ordre compte toujours, mais un élément ne peut plus revenir.

La factorielle

Elle grandit très vite : $3!=6$ , $5!=120$ , $10!=3\,628\,800$ .

Les k-uplets d'éléments distincts

On remplit les $k$ cases une par une. Pour la première, on a $n$ choix. Pour la deuxième, il en reste $n-1$ , puisque l'élément déjà pris est exclu. Et ainsi de suite jusqu'à la $k$ -ième case, pour laquelle il reste $n-k+1$ choix.

Démonstration

Le principe multiplicatif donne le produit $n\times(n-1)\times\dots\times(n-k+1)$ , qui compte $k$ facteurs. En multipliant et en divisant par $(n-k)!$ :

n\times\dots\times(n-k+1)=\frac{n\times\dots\times(n-k+1)\times(n-k)!}{(n-k)!}=\frac{n!}{(n-k)!}.

Exemple pour $E=\{a,b,c,d\}$ et $k=2$ . On obtient $4\times3=12$ couples d'éléments distincts :

\begin{array}{cccc} (a,b) & (b,a) & (c,a) & (d,a)\\ (a,c) & (b,c) & (c,b) & (d,b)\\ (a,d) & (b,d) & (c,d) & (d,c) \end{array}

Les permutations

Quand on range tous les éléments ( $k=n$ ), on parle de permutation.

4. Les combinaisons : quand l'ordre ne compte plus

Reprenons les 10 coureurs. Si les trois premiers reçoivent le même prix, on ne s'intéresse plus qu'au groupe des trois gagnants. Or chaque groupe de 3 correspond à $3!=6$ podiums (les 6 façons de les ranger). Il y a donc $\dfrac{720}{6}=120$ groupes possibles.

C'est toute l'idée des combinaisons : on compte les listes, puis on divise par le nombre de façons de ranger chaque groupe.

Démonstration

On compte les $k$ -uplets d'éléments distincts de $E$ de deux façons.

Première façon. D'après la partie 3, il y en a $\dfrac{n!}{(n-k)!}$ .

Deuxième façon. On choisit d'abord l'ensemble des $k$ éléments ( $\binom nk$ façons), puis on les range ( $k!$ façons). Il y en a donc $\binom nk\times k!$ .

En égalant, $\binom nk\times k!=\dfrac{n!}{(n-k)!}$ , d'où $\binom nk=\dfrac{n!}{k!\,(n-k)!}$ .

Exemple pour $n=4$ et $k=2$ . Les 12 couples de la partie 3 se regroupent par paquets de $2!=2$ , un paquet par partie :

\begin{array}{lll} \{a,b\}:(a,b),(b,a) & \{a,c\}:(a,c),(c,a) & \{a,d\}:(a,d),(d,a)\\ \{b,c\}:(b,c),(c,b) & \{b,d\}:(b,d),(d,b) & \{c,d\}:(c,d),(d,c) \end{array}

Il y a donc $\binom42=\dfrac{12}{2}=6$ parties à 2 éléments.

Propriétés des coefficients binomiaux

Démonstration exigible au bac · somme des coefficients binomiaux

Soit $E$ un ensemble à $n$ éléments. On compte ses parties de deux façons.

Première façon. D'après la partie 2, $E$ possède $2^n$ parties.

Deuxième façon. On range les parties selon leur nombre d'éléments $k\in\{0,1,\dots,n\}$ . Pour $k$ fixé, il y a $\binom nk$ parties à $k$ éléments. Ces $n+1$ cas sont disjoints et couvrent toutes les parties, donc par le principe additif, il y a $\sum_{k=0}^n\binom nk$ parties.

En égalant les deux résultats, $\sum_{k=0}^{n}\binom nk=2^n$ .

Exemple pour $E=\{a,b,c\}$ :

\underbrace{\varnothing}_{\binom30=1}\qquad \underbrace{\{a\},\{b\},\{c\}}_{\binom31=3}\qquad \underbrace{\{a,b\},\{a,c\},\{b,c\}}_{\binom32=3}\qquad \underbrace{\{a,b,c\}}_{\binom33=1}

et l'on retrouve $1+3+3+1=8=2^3$ .

Le triangle de Pascal

On range les coefficients $\binom nk$ en triangle : ligne $n$ , colonne $k$ . Chaque nombre est alors la somme des deux nombres situés juste au-dessus. Survole les cases pour le vérifier.

ligne 4, colonne 2 : 3 + 3 = 6

Lignes7

Survole ou touche une case : chaque nombre est la somme des deux nombres situés juste au-dessus. La case de la ligne n, colonne k contient le coefficient binomial « k parmi n ».

Démonstration exigible au bac · relation de Pascal

Par dénombrement. Soit $E$ un ensemble à $n$ éléments et $a$ un élément fixé de $E$ . On sépare les parties de $E$ à $k$ éléments en deux cas disjoints :

celles qui contiennent $a$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k-1}$ parties ;
celles qui ne contiennent pas $a$ : on choisit les $k$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k}$ parties.

Par le principe additif, $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ .

Par le calcul. On réduit au même dénominateur $k!\,(n-k)!$ , avec $k!=k\times(k-1)!$ et $(n-k)!=(n-k)\times(n-1-k)!$ :

\begin{aligned} \binom{n-1}{k-1}+\binom{n-1}{k} &=\frac{(n-1)!\times k}{k!\,(n-k)!}+\frac{(n-1)!\times(n-k)}{k!\,(n-k)!}\\[4pt] &=\frac{(n-1)!\,\big[k+(n-k)\big]}{k!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}=\binom nk. \end{aligned}

5. Quel modèle choisir ?

Face à un exercice, deux questions suffisent presque toujours.

L'ordre compte-t-il ? Si l'on échange deux éléments, obtient-on un résultat différent ? Un code, un podium, un mot : oui. Une main de cartes, un groupe, un tirage simultané : non.
Les répétitions sont-elles possibles ? Un même élément peut-il apparaître plusieurs fois ? Tirage avec remise, code : oui. Tirage sans remise, personnes distinctes : non.

L’ordre compte-t-il ?

Les répétitions sont-elles possibles ?

n = 10k = 3

k-uplets d’éléments distincts

n! / (n − k)! = 10! / 7! = 720

Tirer 3 jetons parmi 10, sans remise, en notant l’ordre de sortie.

Réponds aux deux questions : le modèle et la formule s’en déduisent. n est le nombre d’éléments disponibles, k le nombre d’éléments choisis.

Ordre	Répétitions	Modèle	Nombre
oui	oui	$k$ -uplets	$n^k$
oui	non	$k$ -uplets d'éléments distincts	$\dfrac{n!}{(n-k)!}$
non	non	combinaisons	$\dbinom nk$

La technique du « au moins un »

Dès qu'un énoncé dit « au moins un », le plus simple est souvent de compter le contraire, « aucun », puis de soustraire au total.

À retenir

Séparer en cas disjoints : on additionne. Enchaîner des choix : on multiplie.
Listes avec répétition : $n^k$ . Ensemble des parties : $2^n$ .
Listes sans répétition : $\dfrac{n!}{(n-k)!}$ . Permutations : $n!$ .
Parties à $k$ éléments : $\dbinom nk=\dfrac{n!}{k!\,(n-k)!}$ , avec $\dbinom nk=\dbinom n{n-k}$ , $\displaystyle\sum_{k=0}^n\binom nk=2^n$ et la relation de Pascal.
« Au moins un » : on passe par le contraire.

5 hPrérequis : ensembles, arbres de choix, raisonnement par récurrence.

Tout le chapitre repose sur deux réflexes :

quand on sépare en cas qui ne se recouvrent pas, on additionne ;
quand on enchaîne des choix, on multiplie.

Le reste consiste à reconnaître la bonne situation : l'ordre compte-t-il, les répétitions sont-elles permises ?

1. Les deux règles de base

Additionner : séparer en cas

Une classe compte 12 filles et 15 garçons. Personne n'est à la fois fille et garçon, donc la classe compte $12+15=27$ élèves. C'est le principe additif.

Multiplier : enchaîner des choix

Entrées3

Plats4

Desserts2

3 × 4 × 2 = 24 menus

Chaque chemin de la racine à une feuille est un menu. À chaque étape, chaque branche se divise de la même façon : le nombre de feuilles est le produit des nombres de choix.

Un menu est un triplet (entrée, plat, dessert) : c'est un élément d'un produit cartésien.

2. Les listes avec répétition

Un code PIN, c'est 4 chiffres écrits dans un ordre précis, et un même chiffre peut revenir : 0 0 7 2 est un code valable, différent de 7 2 0 0. C'est une liste, qu'on appelle un $k$ -uplet.

Pour remplir chacune des $k$ cases, on a à chaque fois les $n$ éléments de $E$ à disposition. Le principe multiplicatif donne $n\times n\times\dots\times n$ .

Combien de parties a un ensemble ?

Partie : { a, c } · code : 1010

Touche un élément pour le mettre dedans (1) ou dehors (0). Avec 4 éléments, il y a 2 × 2 × 2 × 2 = 16 codes, donc 16 parties de E = {a, b, c, d}.

Démonstration

Notons $E=\{x_1,\dots,x_n\}$ . À toute partie $A$ de $E$ , on associe le $n$ -uplet $(\varepsilon_1,\dots,\varepsilon_n)$ de $\{0\,;1\}^n$ défini par

\varepsilon_i=\begin{cases}1 & \text{si } x_i\in A,\\ 0 & \text{si } x_i\notin A.\end{cases}

\Card\big(\Parties(E)\big)=\Card\big(\{0\,;1\}^n\big)=2^n.

3. Les listes sans répétition

Pour un podium, le premier, le deuxième et le troisième sont trois coureurs différents. L'ordre compte toujours, mais un élément ne peut plus revenir.

La factorielle

Elle grandit très vite : $3!=6$ , $5!=120$ , $10!=3\,628\,800$ .

Les k-uplets d'éléments distincts

Démonstration

Le principe multiplicatif donne le produit $n\times(n-1)\times\dots\times(n-k+1)$ , qui compte $k$ facteurs. En multipliant et en divisant par $(n-k)!$ :

n\times\dots\times(n-k+1)=\frac{n\times\dots\times(n-k+1)\times(n-k)!}{(n-k)!}=\frac{n!}{(n-k)!}.

Exemple pour $E=\{a,b,c,d\}$ et $k=2$ . On obtient $4\times3=12$ couples d'éléments distincts :

\begin{array}{cccc} (a,b) & (b,a) & (c,a) & (d,a)\\ (a,c) & (b,c) & (c,b) & (d,b)\\ (a,d) & (b,d) & (c,d) & (d,c) \end{array}

Les permutations

Quand on range tous les éléments ( $k=n$ ), on parle de permutation.

4. Les combinaisons : quand l'ordre ne compte plus

C'est toute l'idée des combinaisons : on compte les listes, puis on divise par le nombre de façons de ranger chaque groupe.

Démonstration

On compte les $k$ -uplets d'éléments distincts de $E$ de deux façons.

Première façon. D'après la partie 3, il y en a $\dfrac{n!}{(n-k)!}$ .

Deuxième façon. On choisit d'abord l'ensemble des $k$ éléments ( $\binom nk$ façons), puis on les range ( $k!$ façons). Il y en a donc $\binom nk\times k!$ .

En égalant, $\binom nk\times k!=\dfrac{n!}{(n-k)!}$ , d'où $\binom nk=\dfrac{n!}{k!\,(n-k)!}$ .

Exemple pour $n=4$ et $k=2$ . Les 12 couples de la partie 3 se regroupent par paquets de $2!=2$ , un paquet par partie :

\begin{array}{lll} \{a,b\}:(a,b),(b,a) & \{a,c\}:(a,c),(c,a) & \{a,d\}:(a,d),(d,a)\\ \{b,c\}:(b,c),(c,b) & \{b,d\}:(b,d),(d,b) & \{c,d\}:(c,d),(d,c) \end{array}

Il y a donc $\binom42=\dfrac{12}{2}=6$ parties à 2 éléments.

Propriétés des coefficients binomiaux

Démonstration exigible au bac · somme des coefficients binomiaux

Soit $E$ un ensemble à $n$ éléments. On compte ses parties de deux façons.

Première façon. D'après la partie 2, $E$ possède $2^n$ parties.

En égalant les deux résultats, $\sum_{k=0}^{n}\binom nk=2^n$ .

Exemple pour $E=\{a,b,c\}$ :

\underbrace{\varnothing}_{\binom30=1}\qquad \underbrace{\{a\},\{b\},\{c\}}_{\binom31=3}\qquad \underbrace{\{a,b\},\{a,c\},\{b,c\}}_{\binom32=3}\qquad \underbrace{\{a,b,c\}}_{\binom33=1}

et l'on retrouve $1+3+3+1=8=2^3$ .

Le triangle de Pascal

On range les coefficients $\binom nk$ en triangle : ligne $n$ , colonne $k$ . Chaque nombre est alors la somme des deux nombres situés juste au-dessus. Survole les cases pour le vérifier.

ligne 4, colonne 2 : 3 + 3 = 6

Lignes7

Survole ou touche une case : chaque nombre est la somme des deux nombres situés juste au-dessus. La case de la ligne n, colonne k contient le coefficient binomial « k parmi n ».

Démonstration exigible au bac · relation de Pascal

Par dénombrement. Soit $E$ un ensemble à $n$ éléments et $a$ un élément fixé de $E$ . On sépare les parties de $E$ à $k$ éléments en deux cas disjoints :

celles qui contiennent $a$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k-1}$ parties ;
celles qui ne contiennent pas $a$ : on choisit les $k$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k}$ parties.

Par le principe additif, $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ .

Par le calcul. On réduit au même dénominateur $k!\,(n-k)!$ , avec $k!=k\times(k-1)!$ et $(n-k)!=(n-k)\times(n-1-k)!$ :

\begin{aligned} \binom{n-1}{k-1}+\binom{n-1}{k} &=\frac{(n-1)!\times k}{k!\,(n-k)!}+\frac{(n-1)!\times(n-k)}{k!\,(n-k)!}\\[4pt] &=\frac{(n-1)!\,\big[k+(n-k)\big]}{k!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}=\binom nk. \end{aligned}

5. Quel modèle choisir ?

Face à un exercice, deux questions suffisent presque toujours.

L'ordre compte-t-il ? Si l'on échange deux éléments, obtient-on un résultat différent ? Un code, un podium, un mot : oui. Une main de cartes, un groupe, un tirage simultané : non.
Les répétitions sont-elles possibles ? Un même élément peut-il apparaître plusieurs fois ? Tirage avec remise, code : oui. Tirage sans remise, personnes distinctes : non.

L’ordre compte-t-il ?

Les répétitions sont-elles possibles ?

n = 10k = 3

k-uplets d’éléments distincts

n! / (n − k)! = 10! / 7! = 720

Tirer 3 jetons parmi 10, sans remise, en notant l’ordre de sortie.

Réponds aux deux questions : le modèle et la formule s’en déduisent. n est le nombre d’éléments disponibles, k le nombre d’éléments choisis.

Ordre	Répétitions	Modèle	Nombre
oui	oui	$k$ -uplets	$n^k$
oui	non	$k$ -uplets d'éléments distincts	$\dfrac{n!}{(n-k)!}$
non	non	combinaisons	$\dbinom nk$

La technique du « au moins un »

Dès qu'un énoncé dit « au moins un », le plus simple est souvent de compter le contraire, « aucun », puis de soustraire au total.

À retenir

Séparer en cas disjoints : on additionne. Enchaîner des choix : on multiplie.
Listes avec répétition : $n^k$ . Ensemble des parties : $2^n$ .
Listes sans répétition : $\dfrac{n!}{(n-k)!}$ . Permutations : $n!$ .
Parties à $k$ éléments : $\dbinom nk=\dfrac{n!}{k!\,(n-k)!}$ , avec $\dbinom nk=\dbinom n{n-k}$ , $\displaystyle\sum_{k=0}^n\binom nk=2^n$ et la relation de Pascal.
« Au moins un » : on passe par le contraire.