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$ .

27.5 Problème : l’art de compter deux fois

Problème 27.1

Devoir du week-end — étoiles et barres, chapeaux déjoués, et des identités démontrées en comptant une même chose de deux façons

La plus profonde astuce du dénombrement est d’une simplicité désarmante : compter deux fois la même collection, par deux méthodes différentes, puis égaler les réponses. Ce problème fait travailler les modèles de la Méthode 27.13, ajoute une technique dont le cours du chapitre n’avait pas eu besoin — les étoiles et barres du dénombrement des glaces — puis compte exactement les célèbres chapeaux déjoués, et trouve le nombre $\frac1\eu$ qui attend au fond de la pile de chapeaux, sa troisième apparition dans ce livre.

Partie I — Choisir le modèle.

Dénombrer les plaques d’immatriculation faites de $2$ lettres suivies de $3$ chiffres ; puis les anagrammes de BANANE.
Dans un jeu de $32$ cartes, dénombrer les mains de $5$ cartes ; puis les mains contenant exactement $2$ des $4$ as.
Un robot va de $(0,0)$ à $(4,3)$ en n’effectuant que des pas unitaires vers la droite ou vers le haut : combien de chemins ? (Coder un chemin par un mot en D et H.)
Développer $(1 + x)^4$ par la formule du binôme (Théorème 27.11) ; puis évaluer en $x = 1$ et en $x = -1$ : quelles deux identités sur les nombres $\binom nk$ en tombent ?
Démontrer par double dénombrement que $k\binom nk = n\binom{n-1}{k-1}$ (compter de deux façons les comités munis d’un président), et en déduire $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

Partie II — Étoiles et barres.

Un glacier vend $4$ parfums ; vous commandez $10$ boules (les parfums peuvent se répéter, l’ordre dans le pot est sans importance). Coder une commande par une rangée de $10$ étoiles (les boules) séparées par $3$ barres (les changements de parfum), et dénombrer les commandes.
Dénombrer les triplets d’entiers naturels tels que $x + y + z = 12$ .
Dénombrer les triplets d’entiers strictement positifs tels que $x + y + z = 12$ (poser $x = 1 + x'$ , etc.).
Combien de monômes distincts apparaissent dans le développement de $(a + b + c)^5$ ?
Contrôle de bon sens de la méthode : dénombrer par la formule les commandes de $3$ boules parmi $2$ parfums, puis les énumérer toutes et comparer.
Dire précisément où « les boules sont indiscernables » est entré dans le codage — et dénombrer ce qui se passe si, au contraire, les boules sont mangées dans l’ordre (positions distinctes), avec la liste de contrôle de la Méthode 27.13.

Partie III — Les chapeaux déjoués. Un dérangement est une redistribution de $n$ chapeaux à leurs $n$ propriétaires dans laquelle personne ne reçoit son propre chapeau ; notons $D_n$ leur nombre. (Le Problème 18.1 a montré qu’un invité en moyenne récupère son chapeau — nous comptons maintenant exactement les soirées totalement malchanceuses.)

Calculer $D_1$ , $D_2$ , $D_3$ en énumérant, puis $D_4$ patiemment (ou astucieusement).
Justifier la récurrence $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : l’invité 1 reçoit un chapeau $k \neq 1$ ( $n - 1$ choix) ; distinguer selon que l’invité $k$ reçoit ou non le chapeau 1. Vérifier qu’elle redonne $D_4$ , et calculer $D_5$ .
Pour $n = 3$ , démontrer par inclusion-exclusion (retrancher les distributions fixant au moins un chapeau, rajouter ce qui a été compté en trop) que $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , puis énoncer la formule générale.
Calculer $\frac{D_5}{5!}$ et le comparer à $\frac1\eu \approx 0.3679$ : la probabilité qu’une grande soirée mélangée soit entièrement dérangée vaut $\frac1\eu$ — la troisième apparition de cette constante, après la loterie et le recrutement du Problème 23.1. (Pourquoi : la formule de la question 14 est le début d’une série célèbre pour $\eu^{-1}$ , racontée dans les volumes universitaires.)
Tirage au sort des cadeaux entre $10$ amis : les noms sont tirés uniformément au hasard. Quelle est la probabilité que le tirage soit valide (personne ne se tire soi-même), et combien de nouveaux tirages le groupe doit-il prévoir ?

Partie IV — Compter deux fois, gagner deux fois.

Le lemme des poignées de main : dans toute soirée, sommer sur les invités le nombre de mains serrées compte chaque poignée exactement deux fois. En déduire que le nombre d’invités ayant serré un nombre impair de mains est toujours pair — et vérifier que l’affirmation a du sens dans une soirée à trois invités.
Démontrer par récurrence le joyau $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ , et le vérifier pour $n = 3$ . (La somme du petit Gauss, élevée au carré, compte des cubes.)
L’identité de Vandermonde (Exercice 27.9) par les chemins : interpréter $\binom{2n}{n}$ comme le nombre de chemins du type de la question 3 allant de $(0,0)$ à $(n,n)$ , couper chaque chemin à sa traversée de l’antidiagonale, et expliquer comment $\sum_j \binom nj^2$ apparaît.
Pour finir — les quatre gestes du dénombreur, une ligne chacun avec un exemple tiré de ce problème : multiplier les étapes et additionner les cas ; coder habilement (étoiles et barres, mots de chemins) ; compter deux fois la même chose (comité avec président, poignées de main) ; retrancher l’indésirable et corriger les doublons (dérangements). Et noter où le dénombrement s’emploiera ensuite : les probabilités, et les chemins du chapitre sur les matrices et les graphes.

Solution

Solution de Problème 27.1.

1. $26^2 \times 10^3 = 676\,000$ plaques. BANANE : $6$ lettres avec le A répété trois fois et le N deux fois : $\frac{6!}{3!\,2!} = 60$ anagrammes.

2. $\binom{32}{5} = 201\,376$ mains ; $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ avec exactement deux as.

3. Un chemin est un mot comportant $4$ D et $3$ H : on choisit la place des H, soit $\binom73 = 35$ .

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . En $x = 1$ : $\sum_k \binom nk = 2^n$ ; en $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — sommes des lignes et sommes alternées des lignes du triangle de Pascal.

5. Comités de $k$ personnes munis d’un président, choisis parmi $n$ : on choisit le comité puis son président ( $\binom nk \times k$ ), ou bien le président puis les autres membres ( $n \times \binom{n-1}{k-1}$ ) : les deux comptages coïncident. En sommant sur $k$ , le membre de droite donne $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

6. Une rangée de $10$ étoiles et $3$ barres code la commande (les boules du parfum 1 avant la première barre, etc.) ; la rangée compte $13$ symboles et est déterminée par la position des barres : $\binom{13}{3} = 286$ commandes.

7. $12$ étoiles, $2$ barres : $\binom{14}{2} = 91$ .

8. Avec $x', y', z' \geq 0$ et $x' + y' + z' = 9$ : $\binom{11}{2} = 55$ .

9. Un monôme $a^i b^j c^k$ avec $i + j + k = 5$ : $\binom72 = 21$ .

10. Par la formule : $3$ étoiles, $1$ barre, soit $\binom41 = 4$ ; par énumération : $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : cela concorde.

11. L’indiscernabilité est entrée au moment où l’on a déclaré qu’une commande n’était rien d’autre que les effectifs par parfum — les étoiles ne portent aucun nom. Si les boules sont mangées dans l’ordre, chacune des $10$ positions distinctes choisit librement un parfum : $4^{10} = 1\,048\,576$ suites — un autre modèle et un autre monde (Méthode 27.13 : toujours se demander ordonné ? distinct ? répétitions autorisées ?).

12. $D_1 = 0$ ; $D_2 = 1$ (l’échange) ; $D_3 = 2$ (les deux cycles de longueur $3$ ) ; $D_4 = 9$ .

13. L’invité 1 reçoit le chapeau $k \neq 1$ : $n - 1$ choix. Si l’invité $k$ reçoit le chapeau 1, les $n - 2$ invités restants dérangent leurs propres chapeaux : $D_{n-2}$ façons. Si l’invité $k$ ne reçoit pas le chapeau 1, on renomme le chapeau 1 en « chapeau interdit de l’invité $k$ » : les $n - 1$ invités restants dérangent : $D_{n-1}$ façons. D’où $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Vérification : $D_4 = 3(2 + 1) = 9$ ; et $D_5 = 4(9 + 2) = 44$ .

14. Sur les $3! = 6$ distributions, on retranche celles qui fixent au moins un chapeau : trois fixent un chapeau donné ( $2!$ chacune, soit $3 \times 2 = 6$ ), ce qui compte deux fois les paires ( $3$ paires, $1!$ chacune) qu’il faut rajouter, et il faut retrancher de nouveau l’identité ( $1$ ) : $D_3 = 6 - 6 + 3 - 1 = 2$ , c’est-à-dire $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ . En général, $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , déjà proche de $\frac1\eu \approx 0.3679$ : la somme alternée $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ marche vers $\eu^{-1}$ . Les chapeaux d’une grande soirée se dérangent complètement environ $36.8\,\%$ du temps — la constante de la loterie et du recrutement, troisième observation.

16. $\P(\text{valide}) = \frac{D_{10}}{10!} \approx 0.368$ . Chaque nouveau tirage réussit avec la probabilité $\approx \frac1\eu$ , donc le nombre espéré de tirages vaut environ $\eu \approx 2.7$ : prévoir trois passages du chapeau.

17. Chaque poignée de main contribue pour $2$ au total des degrés, donc la somme des nombres de poignées de tous les invités est paire. Or une somme d’entiers n’est paire que si le nombre de termes impairs est pair : les invités impairs vont par nombre pair. (À trois invités : aucun profil possible n’a exactement une ou trois entrées impaires — vérifier les quatre graphes possibles.)

18. $n = 1$ : $1 = 1$ . Si $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ , alors en ajoutant $(n+1)^3$ :

\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :

hérédité. Pour $n = 3$ : $1 + 8 + 27 = 36 = 6^2$ .

19. Un chemin menant à $(n, n)$ effectue $2n$ pas et traverse l’antidiagonale $x + y = n$ en exactement un point du réseau, $(j, n - j)$ ; la première moitié est un chemin comportant $j$ pas D parmi $n$ ( $\binom nj$ choix), et la seconde moitié, lue à rebours, de même ( $\binom nj$ encore, par symétrie). En sommant sur le point de traversée : $\binom{2n}{n} = \sum_j \binom nj^2$ — l’identité de Vandermonde, dessinée.

20. Multiplier les étapes, additionner les cas : les plaques et les mains de cartes. Coder : les chemins en mots DH, les commandes en étoiles et barres. Compter deux fois : les comités avec président, les poignées de main, les chemins coupés en leur milieu. Retrancher et corriger : les chapeaux dérangés, avec $\frac1\eu$ pour résidu. Prochaines étapes : ces dénombrements sous les fractions des probabilités, et la puissance de comptage de chemins des matrices d’adjacence, deux chapitres plus loin.

Termes définis dans ce chapitre

Voir les 395 termes du glossaire