Mathématiques du lycée · Grades 10–12

27Combinatoire et dénombrement

La combinatoire est l’art de compter sans énumérer. Ses deux principes élémentaires — ajouter les cardinaux d’alternatives disjointes, multiplier les nombres de choix indépendants — suffisent à compter les arrangements, les permutations et les parties d’un ensemble fini, et culminent dans la formule du binôme.

27.1 Les deux principes de dénombrement

On note $\abs{E}$ le nombre d’éléments (le cardinal) d’un ensemble fini $E$ .

Proposition 27.1 (Principe d’addition)

Si un ensemble fini $E$ est partitionné en sous-ensembles $A_1, \dots, A_k$ (deux à deux disjoints, d’union $E$ ), alors

\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.

Proposition 27.2 (Principe de multiplication)

Si un objet est construit par une succession de $k$ choix, avec $n_1$ options pour le premier choix et, quels que soient les choix précédents, $n_i$ options pour le $i$ -ième, alors le nombre d’objets construits est $n_1 \times n_2 \times \dots \times n_k$ .

Démonstration. Les deux énoncés se prouvent par récurrence sur $k$ ; le cas $k = 2$ du second revient à compter un tableau rectangulaire par lignes. ∎

Exemple 27.3

Un restaurant propose 4 entrées, 6 plats, 3 desserts : $4 \times 6 \times 3 = 72$ menus à trois plats différents.

27.2 Listes, permutations, factorielles

Définition 27.4 ( $k$ -uplets)

Un $k$ -uplet d’un ensemble $E$ est une liste ordonnée $(x_1, \dots, x_k)$ d’éléments de $E$ , répétitions autorisées. Un $k$ -uplet d’éléments distincts est un arrangement de $k$ éléments de $E$ .

Proposition 27.5

Soit $\abs E = n$ . Le nombre de $k$ -uplets de $E$ est $n^k$ . Le nombre d’arrangements de $k$ éléments de $E$ ( $0 \leq k \leq n$ ) est

n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},

où $n! = 1 \times 2 \times \dots \times n$ (et $0! = 1$ ) est la factorielle de $n$ .

Démonstration. Principe de multiplication : pour un $k$ -uplet il y a $n$ options à chacune des $k$ étapes ; pour un arrangement, $n$ options pour $x_1$ , puis $n - 1$ pour $x_2$ (un élément est déjà pris), …, $n - k + 1$ pour $x_k$ . ∎

Définition 27.6 (Permutation)

Une permutation de $E$ est un arrangement des $n$ éléments de $E$ : un ordre total de $E$ . Par la Proposition 27.5 (cas $k = n$ ), le nombre de permutations d’un ensemble à $n$ éléments est $n!$ .

Exemple 27.7

Cinq coureurs peuvent finir une course dans $5! = 120$ ordres différents. Le nombre de podiums possibles (trois premières places) est $5 \times 4 \times 3 = 60$ .

27.3 Combinaisons et coefficients binomiaux

Définition 27.8 (Combinaisons)

Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments (sans ordre, sans répétition). Leur nombre s’écrit $\dbinom{n}{k}$ , lu « $n$ parmi $k$ » ou « $k$ parmi $n$ ».

Théorème 27.9

Pour $0 \leq k \leq n$ :

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} .

Démonstration. Compter les arrangements de $k$ éléments de $E$ de deux manières. Directement : $\frac{n!}{(n-k)!}$ . Alternativement, choisir d’abord le sous-ensemble sous-jacent ( $\binom nk$ façons), puis l’ordonner ( $k!$ façons) ; le principe de multiplication donne $\binom{n}{k}\,k!$ . En égalant, $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Proposition 27.10 (Identités de base)

Pour $0 \leq k \leq n$ :

\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k},

et la règle de Pascal : pour $1 \leq k \leq n-1$ ,

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Démonstration. La symétrie $\binom nk = \binom{n}{n-k}$ vaut car le passage au complémentaire met en bijection les parties à $k$ éléments avec celles à $(n-k)$ éléments. Pour la règle de Pascal, fixer un élément $a \in E$ et trier les parties à $k$ éléments en celles contenant $a$ — obtenues en adjoignant $a$ à une partie à $(k-1)$ éléments de $E \setminus \{a\}$ , au nombre de $\binom{n-1}{k-1}$ — et celles évitant $a$ , qui sont les parties à $k$ éléments de $E \setminus \{a\}$ , au nombre de $\binom{n-1}{k}$ . Conclure par le principe d’addition. ∎

La règle de Pascal engendre les coefficients ligne par ligne — le triangle de Pascal : chaque entrée est la somme des deux au-dessus d’elle.

Le triangle de Pascal, lignes n = 0 à 5 : la règle de Pascal 41 + 42 = 52 en action. — Le triangle de Pascal, lignes $n = 0$ à $5$ : la règle de Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ en action.

Théorème 27.11 (Formule du binôme)

Pour tous $a, b \in \R$ (ou $\C$ ) et $n \in \N$ :

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{k}\, b^{\,n-k} .

Démonstration. Développer le produit $(a+b)(a+b)\cdots(a+b)$ ( $n$ facteurs) : chaque terme du développement choisit $a$ ou $b$ dans chaque facteur, produisant $a^k b^{n-k}$ où $k$ est le nombre de facteurs contribuant $a$ . Le nombre de façons de choisir ces $k$ facteurs parmi $n$ est $\binom nk$ , qui est donc le coefficient de $a^k b^{n-k}$ . ∎

Corollaire 27.12

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ et $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ ( $n \geq 1$ ).

Démonstration. Prendre $a = b = 1$ , puis $a = -1$ , $b = 1$ dans la formule du binôme. La première identité a aussi un sens direct : un ensemble à $n$ éléments a $2^n$ parties (chaque élément est dedans ou dehors : principe de multiplication), triées par taille. ∎

Méthode 27.13 (Choisir le bon modèle)

Avant de compter, répondre à deux questions : l’ordre compte-t-il ? et les répétitions sont-elles autorisées ?

	l’ordre compte	l’ordre n’importe pas
répétitions autorisées	$n^k$ (listes)	(université)
sans répétition	$\frac{n!}{(n-k)!}$ (arrangements)	$\binom nk$ (parties)

Tirer des boules d’une urne : avec remise, dans l’ordre $\to$ listes ; sans remise, dans l’ordre $\to$ arrangements ; une poignée d’un coup $\to$ parties.

27.4 Exercices

Exercice 27.1 ★

Une plaque d’immatriculation se compose de 2 lettres (A–Z), puis 3 chiffres, puis 2 lettres. Combien de plaques sont possibles ? Combien n’ont aucun caractère répété ?

Solution

Solution de Exercice 27.1.

Principe de multiplication : $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Sans caractère répété, les quatre lettres doivent être distinctes ( $26 \times 25 \times 24 \times 23$ façons, en remplissant les positions des lettres dans l’ordre) et les trois chiffres distincts ( $10 \times 9 \times 8$ ) :

26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 .

Exercice 27.2 ★

Calculer $\dbinom{8}{3}$ , $\dbinom{10}{8}$ , et simplifier $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$ .

Solution

Solution de Exercice 27.2.

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$ ; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ ;

\frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.

Exercice 27.3 ★

Dans une classe de 30 élèves, il faut élire un comité de 4 élèves, puis un président et un trésorier au sein du comité (une même personne ne peut occuper les deux postes). Combien d’issues sont possibles ?

Solution

Solution de Exercice 27.3.

Choisir le comité : $\binom{30}{4}$ façons. Puis choisir président et trésorier parmi les 4, dans l’ordre : $4 \times 3 = 12$ façons. Total

\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .

Exercice 27.4 ★

Développer $(x + 2)^5$ et $(1 - x)^6$ à l’aide de la formule du binôme. Quel est le coefficient de $x^3$ dans $(2x + 3)^7$ ?

Solution

Solution de Exercice 27.4.

(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,

(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .

Dans $(2x+3)^7$ , le terme en $x^3$ est $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ : le coefficient est $22\,680$ .

Exercice 27.5 ★★

Une main de poker standard se compose de 5 cartes tirées d’un jeu de 52 cartes.

Combien y a-t-il de mains ?
Combien de mains contiennent exactement un as ? Au moins un as ?
Combien de mains sont des « fulls » (trois cartes d’une valeur, deux d’une autre) ?

Solution

Solution de Exercice 27.5.

1. $\dbinom{52}{5} = 2\,598\,960$ .

2. Exactement un as : le choisir ( $4$ façons) et compléter avec $4$ non-as : $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Au moins un as : dénombrement complémentaire, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Choisir la valeur du brelan ( $13$ ), ses couleurs ( $\binom43 = 4$ ), la valeur de la paire ( $12$ restantes), ses couleurs ( $\binom42 = 6$ ) : $13 \times 4 \times 12 \times 6 = 3744$ .

Exercice 27.6 ★★

Combien d’anagrammes (réarrangements de lettres, sensés ou non) le mot MATH possède-t-il ? Le mot BANANA ? (Indication pour BANANA : placer d’abord les trois A.)

Solution

Solution de Exercice 27.6.

MATH a 4 lettres distinctes : $4! = 24$ anagrammes.

BANANA a 6 lettres : trois A, deux N, un B. Choisir les positions des A ( $\binom63$ ), puis des N parmi le reste ( $\binom32$ ), le B prend la dernière place :

\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .

(De façon équivalente $\frac{6!}{3!\,2!\,1!} = 60$ .)

Exercice 27.7 ★★

Prouver l’identité $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) de deux façons : par la formule factorielle, et en comptant de deux manières les couples (comité de $k$ personnes, son président) choisis parmi $n$ personnes.

Solution

Solution de Exercice 27.7.

Algébriquement :

k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}.

Par double dénombrement : compter les couples (comité de $k$ , président dedans). Soit choisir le comité ( $\binom nk$ ) puis son président ( $k$ ) : $k\binom nk$ couples. Soit choisir d’abord le président ( $n$ options) puis les $k-1$ autres membres parmi les $n-1$ restants : $n\binom{n-1}{k-1}$ couples.

Exercice 27.8 ★★

Un chemin dans le plan va de $(0,0)$ à $(m, n)$ par des pas unitaires Est ou Nord. Montrer que le nombre de tels chemins est $\dbinom{m+n}{m}$ .

Solution

Solution de Exercice 27.8.

Un chemin se compose d’exactement $m + n$ pas, dont $m$ sont Est et $n$ sont Nord ; il est entièrement déterminé par l’ensemble des instants (parmi les $m+n$ ) où l’on avance vers l’Est. Il y a $\binom{m+n}{m}$ tels choix.

Exercice 27.9 ★★★

Prouver l’identité de Vandermonde : pour $0 \leq k \leq m + n$ ,

\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j},

en comptant les parties à $k$ éléments d’un ensemble scindé en un groupe de $m$ et un groupe de $n$ . En déduire que $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Solution

Solution de Exercice 27.9.

Scinder un ensemble de $m + n$ personnes en un groupe $A$ de $m$ et un groupe $B$ de $n$ . Une partie à $k$ éléments contient un certain nombre $j$ de membres de $A$ ( $0 \leq j \leq k$ ) et $k - j$ membres de $B$ ; pour $j$ fixé il y a $\binom mj \binom{n}{k-j}$ telles parties, et le principe d’addition sur $j$ donne l’identité de Vandermonde.

Avec $m = n = k$ :

\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j} = \sum_{j=0}^n \binom nj^{2},

en utilisant la symétrie $\binom{n}{n-j} = \binom nj$ .

Exercice 27.10 ★★★

À l’aide de la formule du binôme, montrer que pour tout $n \geq 1$ ,

\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.

(Indication : soit dériver $(1+x)^n$ , soit utiliser l’Exercice 27.7.)

Solution

Solution de Exercice 27.10.

Via l’Exercice 27.7 :

\sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1},

par le Corollaire 27.12. Via dérivation : dériver $(1+x)^n = \sum_k \binom nk x^k$ donne $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; évaluer en $x = 1$ .