Mathématiques universitaires — Licence 1 · Bachelor Year 1

2Dénombrement

Dénombrer les ensembles finis a l’air élémentaire — et devient vite subtil. Ce chapitre définit proprement le cardinal (par les bijections, dans l’esprit du Chapitre 1), établit la poignée de principes de dénombrement dont tout découle, puis en déduit les dénombrements classiques : listes, permutations, parties, coefficients binomiaux.

2.1 Cardinal des ensembles finis

Définition 2.1 (Ensemble fini, cardinal)

Pour $n \in \N^*$ , on note $\intint{1}{n} = \{1, 2, \dots, n\}$ . Un ensemble $E$ est fini lorsque $E = \emptyset$ ou qu’il existe une bijection de $\intint{1}{n}$ sur $E$ pour un certain $n \in \N^*$ ; ce $n$ est alors unique (Théorème 2.2) et c’est le cardinal de $E$ , noté $\abs{E}$ (avec $\abs{\emptyset} = 0$ ).

Théorème 2.2 (Le cardinal est bien défini)

Si $m \neq n$ , il n’existe pas de bijection de $\intint{1}{m}$ sur $\intint{1}{n}$ . Plus précisément, si $m > n$ , il n’existe pas d’injection de $\intint{1}{m}$ dans $\intint{1}{n}$ .

Démonstration. Démontrons par récurrence sur $n$ l’assertion : pour tout $m > n$ , il n’existe pas d’injection $\intint{1}{m} \to \intint{1}{n}$ . Pour $n = 0$ , l’ensemble d’arrivée est vide et $m \geq 1$ : aucune application n’existe. Supposons l’assertion vraie au rang $n$ , et soit $f \colon \intint{1}{m} \to \intint{1}{n+1}$ une injection avec $m > n + 1$ . Si la valeur $n + 1$ n’est pas atteinte, $f$ est une injection dans $\intint{1}{n}$ , ce qui contredit l’hypothèse de récurrence. Sinon, $f(a) = n + 1$ pour exactement un $a$ ; échangeons $f(a)$ et $f(m)$ (formellement : composons avec la transposition des deux valeurs), de sorte que la nouvelle injection $g$ vérifie $g(m) = n + 1$ . Alors la restriction de $g$ à $\intint{1}{m-1}$ est une injection dans $\intint{1}{n}$ avec $m - 1 > n$ — nouvelle contradiction. ∎

Corollaire 2.3 (Principe des tiroirs)

Si $\abs{E} > \abs{F}$ , aucune application $f \colon E \to F$ n’est injective : deux éléments au moins de $E$ ont la même image.

Démonstration. Écrivons $\abs E = m$ , $\abs F = n$ avec $m > n$ , et choisissons des bijections $u \colon \intint1m \to E$ et $v \colon F \to \intint1n$ . Si $f$ était injective, $v \circ f \circ u$ serait une injection de $\intint1m$ dans $\intint1n$ (composée d’injections, Proposition 1.26), ce qui contredirait le Théorème 2.2. ∎

Remarque 2.4 (Interlude : pourquoi l’échange dans la démonstration du théorème ?)

La démonstration du Théorème 2.2 contient la première idée vraiment astucieuse du chapitre, qui mérite d’être rejouée lentement. L’obstacle : pour appliquer l’hypothèse de récurrence, on voudrait supprimer le dernier point $m$ de l’ensemble de départ et le dernier point $n+1$ de l’ensemble d’arrivée, mais $f$ peut envoyer un autre point $a$ sur $n + 1$ , et supprimer alors ce point d’arrivée abîme l’application ailleurs. Le remède : composer $f$ avec la transposition des deux valeurs $f(a)$ et $f(m)$ — une bijection de l’ensemble d’arrivée, donc l’injectivité est préservée — après quoi la valeur gênante $n + 1$ occupe la position inoffensive $m$ , et les deux suppressions sont propres. Ce schéma « normaliser d’abord, couper ensuite » reviendra : c’est ainsi que la récurrence des dérangements redirige $\sigma^{-1}(n+1)$ dans le devoir maison de ce chapitre, et ainsi que l’on rafistole les permutations tout au long du problème du Chapitre 7 sur le groupe symétrique.

Proposition 2.5 (Injections, surjections et cardinal)

Soient $E, F$ des ensembles finis avec $\abs{E} = \abs{F}$ , et $f \colon E \to F$ . Alors

f \text{ injective} \iff f \text{ surjective} \iff f \text{ bijective}.

Démonstration. Supposons $f$ injective. Alors $f$ est une bijection de $E$ sur $f(E)$ , donc $\abs{f(E)} = \abs{E} = \abs{F}$ . Si $f(E)$ ratait un point $y_0$ de $F$ , $f$ serait une injection de $E$ dans $F \setminus \{y_0\}$ , ensemble de cardinal $\abs{F} - 1 < \abs{E}$ — impossible d’après le principe des tiroirs. Donc $f(E) = F$ : $f$ est surjective, donc bijective.

Supposons $f$ surjective. Choisissons pour chaque $y \in F$ un antécédent $s(y) \in E$ ; alors $f \circ s = \mathrm{id}_F$ , donc $s$ est injective (Proposition 1.26). D’après le paragraphe précédent appliqué à $s$ (les cardinaux sont égaux), $s$ est bijective. De $f \circ s = \mathrm{id}_F$ on tire $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , donc $f$ est bijective. Enfin, une application bijective est par définition à la fois injective et surjective, ce qui referme le cycle d’implications. ∎

Exemple 2.6 (La finitude est essentielle)

Sur un ensemble fini, la Proposition 2.5 est un raccourci puissant : toute application injective de $E$ dans lui-même est automatiquement une permutation de $E$ — la moitié de la bijectivité est offerte. Les deux implications s’effondrent sur les ensembles infinis : $n \mapsto n + 1$ est injective de $\N$ dans $\N$ mais rate $0$ , et l’application $\N \to \N$ qui envoie $0 \mapsto 0$ et $n \mapsto n - 1$ pour $n \geq 1$ est surjective sans être injective. Chaque fois que cette proposition est invoquée, l’hypothèse de finitude travaille réellement — un thème que le devoir maison du Chapitre 1 explore par l’autre bout, là où les ensembles infinis sont précisément ceux qui admettent de telles applications d’eux-mêmes dans eux-mêmes.

Exemple 2.7 (La moitié du travail, gratuitement)

Considérons l’application $f$ sur $\{0, 1, \dots, 6\}$ qui envoie $k$ sur le reste de $3k$ dans la division par $7$ ; sa table de valeurs est

0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .

$f$ est-elle bijective ? L’injectivité suffit à elle seule (Proposition 2.5) : si $3k$ et $3k'$ ont le même reste, $7$ divise $3(k - k')$ , et comme $7$ est premier et ne divise pas $3$ , il divise $k - k'$ (lemme d’Euclide, utilisé ici au niveau du lycée et démontré au Chapitre 6) ; avec $\abs{k - k'} \leq 6$ cela force $k = k'$ . La surjectivité vient gratuitement — inutile de résoudre $3k \equiv c$ pour chaque $c$ , même si la table confirme que chaque valeur apparaît exactement une fois. Le raccourci est une bête de somme : il donne l’inversibilité de la multiplication modulaire (Chapitre 6), il fait fonctionner l’appariement du théorème de Wilson, et il revient en algèbre linéaire sous la forme « un endomorphisme d’un espace de dimension finie est injectif si et seulement s’il est surjectif » (Chapitre 19).

2.2 Les principes de dénombrement

Proposition 2.8 (Règles de somme et de produit)

Soient $E, F$ des ensembles finis.

Si $E \cap F = \emptyset$ , alors $\abs{E \cup F} = \abs{E} + \abs{F}$ ; plus généralement, pour une partition de $E$ en parties $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
En général, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
L’ensemble $F^E$ des applications de $E$ dans $F$ vérifie $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

Démonstration. (1) Concaténons les énumérations : si $E = \{x_1, \dots, x_m\}$ et $F = \{y_1, \dots, y_n\}$ sans répétition, alors $x_1, \dots, x_m, y_1, \dots, y_n$ énumère $E \cup F$ sans répétition (les deux ensembles étant disjoints). Une récurrence étend cela à $k$ parties.

(2) $E \cup F$ est la réunion disjointe de $E$ et de $F \setminus E$ , et $F$ est la réunion disjointe de $F \cap E$ et de $F \setminus E$ ; donc $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} - \abs{E \cap F}$ .

(3) $E \times F$ est la réunion disjointe, pour $x \in E$ , des ensembles $\{x\} \times F$ , chacun de cardinal $\abs{F}$ ; on applique (1).

(4) Une application de $E = \{x_1, \dots, x_m\}$ dans $F$ n’est rien d’autre que le choix du $m$ -uplet $(f(x_1), \dots, f(x_m)) \in F^m$ ; cette correspondance est une bijection, et $\abs{F^m} = \abs{F}^m$ par (3) et récurrence.

(5) Les parties de $E$ correspondent bijectivement aux applications $E \to \{0, 1\}$ (à $A$ on associe sa fonction indicatrice) ; on applique (4). ∎

Exemple 2.9 (Dénombrement par le complémentaire)

Combien de codes PIN à $4$ chiffres (chiffres de $0$ à $9$ , l’ordre compte, répétitions autorisées) contiennent au moins un chiffre répété ? Les compter directement oblige à jongler avec les cas « exactement une paire, deux paires, un brelan, un carré » — cinq configurations qui se chevauchent. Comptons plutôt le complémentaire : les codes sont au nombre de $10^4 = 10\,000$ (règle du produit), les codes à quatre chiffres distincts au nombre de $10 \times 9 \times 8 \times 7 = 5\,040$ ( $4$ -arrangements), de sorte que la réponse est

10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960 .

Près de la moitié des codes PIN répètent un chiffre. L’idée à retenir : dès qu’un dénombrement s’énonce avec « au moins » ou « pas tous », il faut essayer le complémentaire d’abord — la règle de somme garantit que $\abs{A} = \abs{E} - \abs{\overline A}$ , et le complémentaire est souvent une unique configuration bien propre.

Exemple 2.10 (Chemins sur un réseau)

Dénombrons les chemins les plus courts allant du coin $(0,0)$ au coin $(4, 3)$ d’un quadrillage, chaque pas allant d’une unité vers la droite (D) ou d’une unité vers le haut (H). Un tel chemin comporte exactement $7$ pas, dont $4$ sont D et $3$ sont H ; réciproquement, tout mot de longueur $7$ en les lettres D, H comportant quatre D décrit exactement un chemin. Les chemins correspondent donc bijectivement aux choix des positions des D :

\binom{7}{4} = 35 .

L’idée est le codage : le dénombrement est devenu trivial dès l’instant où chaque chemin a été traduit en un mot, c’est-à-dire en une partie de positions — une illustration de plus du slogan selon lequel un dénombrement correct est une bijection déguisée (Méthode 2.19).

L’un des 74 = 35 chemins les plus courts de (0,0) à (4,3) : le chemin représenté code le mot DHDDHDH, c’est-à-dire le choix des positions \1,3,4,6\ pour la lettre D parmi les sept pas. — L’un des $\binom74 = 35$ chemins les plus courts de $(0,0)$ à $(4,3)$ : le chemin représenté code le mot DHDDHDH, c’est-à-dire le choix des positions $\{1,3,4,6\}$ pour la lettre D parmi les sept pas.

2.3 Listes, permutations, parties

Définition 2.11 (Arrangements, permutations, combinaisons)

Soit $E$ un ensemble avec $\abs{E} = n$ , et soit $0 \leq k \leq n$ .

Un $k$ -arrangement de $E$ est un $k$ -uplet injectif d’éléments de $E$ (une sélection ordonnée sans répétition) ;
une permutation de $E$ est une bijection de $E$ sur lui-même — de façon équivalente, un $n$ -arrangement ;
une $k$ -combinaison est une partie de $E$ à $k$ éléments (une sélection non ordonnée sans répétition). Leur nombre se note $\binom{n}{k}$ , lu « $k$ parmi $n$ » .

Théorème 2.12 (Les trois dénombrements)

Avec $n = \abs{E}$ et $0 \leq k \leq n$ :

le nombre de $k$ -arrangements de $E$ vaut $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
le nombre de permutations de $E$ vaut $n!$ ;
$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

Démonstration. (1) On choisit la première coordonnée ( $n$ possibilités), puis la deuxième ( $n - 1$ choix restants), …, puis la $k$ -ième ( $n - k + 1$ choix). Formellement, récurrence sur $k$ . Pour $k = 1$ il y a $n$ uplets injectifs à un terme. Supposons le dénombrement acquis au rang $k - 1$ . Chaque $k$ -arrangement $(x_1, \dots, x_k)$ s’obtient à partir d’un unique $(k-1)$ -arrangement — son tronqué $(x_1, \dots, x_{k-1})$ — en lui ajoutant une dernière coordonnée hors de $\{x_1, \dots, x_{k-1}\}$ , pour laquelle exactement $n - (k - 1)$ valeurs sont disponibles. La troncature partitionne donc les $k$ -arrangements en classes de taille commune $n - k + 1$ indexées par les $(k-1)$ -arrangements, et la règle de somme donne

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

(2) est (1) avec $k = n$ .

(3) Chaque partie à $k$ éléments s’ordonne en $k!$ $k$ -arrangements distincts, et tout $k$ -arrangement provient d’une unique partie : donc $\frac{n!}{(n-k)!} = \binom nk \cdot k!$ . ∎

Exemple 2.13 (Tables rondes : quotienter par une symétrie)

De combien de façons $n$ convives peuvent-ils s’asseoir autour d’une table ronde, deux placements étant identiques lorsque chaque convive a les mêmes voisins de gauche et de droite — c’est-à-dire à rotation près ? Chaque placement circulaire correspond à exactement $n$ placements linéaires (on coupe le cercle à l’une des $n$ places), de sorte que les $n!$ ordres linéaires s’effondrent par paquets de $n$ :

\frac{n!}{n} = (n-1)! \quad\text{placements circulaires.}

Autrement dit : on assied un convive distingué n’importe où (ce qui tue la liberté de rotation), puis on ordonne les $n - 1$ convives restants dans le sens des aiguilles d’une montre. Pour $n = 6$ : $120$ tables. Les deux solutions illustrent les deux remèdes standard au surcomptage : diviser par le nombre exact de répétitions, ou briser la symétrie en fixant un objet. Tous deux exigent que le paquet de répétitions ait la même taille pour chaque configuration — ce dont la démonstration de la formule $\binom nk = \frac{n!}{k!\,(n-k)!}$ ci-dessus s’est également servie, avec $k!$ à la place de $n$ .

Exemple 2.14 (Ajouter une contrainte)

Poursuivons avec la table ronde : parmi les $(n-1)!$ tables de $n \geq 3$ convives, combien séparent deux convives donnés $A$ et $B$ (non voisins) ? Comptons le complémentaire. Les tables où $A$ et $B$ sont assis côte à côte : collons-les en un seul bloc — $n - 1$ objets autour de la table, soit $(n-2)!$ dispositions circulaires — puis ordonnons la paire à l’intérieur de son bloc ( $2$ façons) : $2\,(n-2)!$ tables où ils sont voisins. Donc

(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr) = (n-3)\,(n-2)!

tables les séparent. Vérifications : $n = 3$ donne $0$ (autour d’un triangle, tout le monde touche tout le monde) et $n = 4$ donne $2$ , faciles à lister à la main. L’astuce du collage — traiter un bloc imposé comme un seul objet, puis compter ses dispositions internes — est le remède standard aux contraintes de voisinage, linéaires ou circulaires.

Proposition 2.15 (Identités de base)

Pour $0 \leq k \leq n$ :

\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1 \leq k \leq n-1), \qquad \sum_{k=0}^{n} \binom{n}{k} = 2^n .

Démonstration. Première identité : $A \mapsto E \setminus A$ est une bijection entre les parties à $k$ éléments et celles à $n-k$ éléments. Formule de Pascal : fixons un élément $a \in E$ ; les parties à $k$ éléments se scindent en celles qui contiennent $a$ (on choisit les $k - 1$ autres : $\binom{n-1}{k-1}$ ) et celles qui évitent $a$ ( $\binom{n-1}{k}$ ). Troisième identité : les deux membres comptent toutes les parties de $E$ , réparties selon leur taille dans le membre de gauche (Proposition 2.8 (1) et (5)). ∎

Théorème 2.16 (Formule du binôme de Newton)

Pour tous $a, b$ dans un anneau commutatif (disons $\R$ ou $\C$ ) et tout $n \in \N$ :

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

Démonstration. Développer $(a+b)(a+b)\cdots(a+b)$ par distributivité produit un terme par choix, dans chaque facteur, de $a$ ou de $b$ : le terme $a^k b^{n-k}$ apparaît une fois pour chaque façon de choisir lesquels des $n$ facteurs, au nombre de $k$ , fournissent $a$ — c’est-à-dire $\binom nk$ fois. (Variante : récurrence sur $n$ à l’aide de la formule de Pascal.) ∎

Exemple 2.17

Deux spécialisations classiques : $a = b = 1$ redonne $\sum_k \binom nk = 2^n$ ; $a = -1$ , $b = 1$ donne $\sum_{k} (-1)^k \binom nk = 0$ pour $n \geq 1$ : parmi les parties d’un ensemble non vide, exactement la moitié sont de cardinal pair.

Exemple 2.18 (Une identité, deux démonstrations)

La spécialisation $a = 2$ , $b = 1$ de la formule du binôme s’écrit

\sum_{k=0}^{n} \binom nk\,2^k = 3^n .

Voici la même identité sans le moindre calcul algébrique. Le membre de droite compte les mots de longueur $n$ sur l’alphabet $\{0, 1, 2\}$ (règle du produit). Classons chaque mot selon l’ensemble $K$ des positions portant une lettre non nulle : choisir $K$ avec $\abs K = k$ coûte $\binom nk$ , puis chaque position de $K$ porte indépendamment $1$ ou $2$ : $2^k$ façons. La règle de somme sur $k$ donne le membre de gauche. Au-delà du plaisir de l’accord, les deux démonstrations ont des vertus différentes : l’algébrique se généralise à toute valeur de $a$ , la combinatoire explique la formule et s’adapte à des contraintes (interdire la lettre $2$ en dernière position, par exemple) qu’aucune substitution ne capture. Garder les deux techniques actives est la compétence pratique que ce chapitre entraîne.

Méthode 2.19 (Quel dénombrement appliquer ?)

Avant de calculer, répondez à deux questions sur la sélection : l’ordre compte-t-il, et les répétitions sont-elles autorisées ?

	l’ordre compte	l’ordre ne compte pas
sans répétition	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
[6pt] avec répétition	$n^k$	(Exercice 2.10)

Cherchez ensuite une bijection ou une partition ramenant le problème à ces dénombrements modèles ; un dénombrement correct est une bijection déguisée.

Remarque 2.20 (Pièges classiques du dénombrement)

Sommer des cas non disjoints. La règle de somme exige une partition ; si des configurations peuvent relever de deux cas à la fois, elles sont comptées deux fois — le remède est la formule du crible (Théorème 2.24) ou une disjonction de cas plus fine.
Ordonné contre non ordonné. Choisir « un comité de deux », c’est $\binom n2$ , et non $n(n-1)$ : décidez avant de calculer si la sélection porte un ordre, et si un dénombrement ordonné est plus facile, divisez par le nombre d’ordonnancements à la fin — mais seulement lorsque chaque objet non ordonné provient du même nombre d’objets ordonnés.
Des choix successifs qui ne sont pas indépendants. La règle du produit demande que le nombre d’options à chaque étape soit indépendant des choix précédents. « Choisir un capitaine, puis un vice-capitaine différent » convient ( $n(n-1)$ ) ; « choisir deux joueurs qui s’entendent bien » n’est pas du tout un produit à deux étapes.
Le double comptage par construction. Construire chaque objet deux fois — par exemple compter les mains contenant au moins un as comme (choisir un as) $\times$ (choisir $4$ autres cartes) — surcompte les mains à deux as. « Au moins » appelle presque toujours le complémentaire (Exemple 2.9).

Exemple 2.21 (Un dénombrement à la poker)

Dans un jeu de $52$ cartes, le nombre de mains de $5$ cartes vaut $\binom{52}{5} = 2\,598\,960$ . Les mains contenant exactement un as : on choisit l’as ( $4$ façons) puis $4$ cartes parmi les $48$ qui ne sont pas des as : $4 \binom{48}{4} = 778\,320$ . La règle du produit s’applique parce que le choix se scinde en étapes indépendantes.

Méthode 2.22 (Double dénombrement)

Pour démontrer une identité entre deux expressions de dénombrement, cherchez un unique ensemble fini que les deux membres comptent — typiquement un ensemble de couples — et évaluez son cardinal dans deux ordres différents. Le prototype est le lemme des poignées de main : dans une soirée, comptons les couples (personne, main serrée). En sommant sur les personnes on obtient $\sum_p d_p$ (le nombre $d_p$ de poignées de main de chaque personne $p$ ) ; en sommant sur les poignées de main on obtient deux fois le nombre de poignées de main (chacune en implique deux). Donc $\sum_p d_p$ est pair — de sorte que le nombre de personnes ayant serré un nombre impair de mains est toujours pair, conclusion non triviale obtenue sans la moindre formule. Le même moteur fait tourner l’Exercice 2.12 et plusieurs questions du devoir maison ci-dessous.

Exemple 2.23 (La partie moyenne)

Quel est le cardinal moyen d’une partie d’un ensemble $E$ à $n$ éléments, les $2^n$ parties étant équiprobables ? Comptons doublement les couples $(A, a)$ avec $a \in A$ : en sommant sur les parties on obtient $\sum_A \abs A$ , le total cherché ; en sommant sur les éléments on obtient $n \cdot 2^{n-1}$ (chacun des $n$ éléments appartient à exactement la moitié des parties — on apparie chaque $A$ contenant $a$ avec $A \setminus \{a\}$ ). Donc

\frac{1}{2^n}\sum_{A \subseteq E} \abs A = \frac{n\,2^{n-1}}{2^n} = \frac n2 :

les parties sont, en moyenne, à moitié pleines — ce que prédit également la symétrie $A \leftrightarrow \overline A$ (qui apparie les tailles $k$ et $n - k$ ). Deux démonstrations, une seule réponse, et toutes deux évitent le calcul direct $\sum_k k\binom nk$ de l’Exercice 2.5 : un appariement bien choisi remplace souvent une identité.

2.4 Formule du crible (inclusion-exclusion)

Théorème 2.24 (Formule du crible)

Pour des ensembles finis $A_1, \dots, A_p$ :

\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr| = \sum_{\emptyset \neq I \subseteq \intint{1}{p}} (-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .

Pour $p = 3$ : $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} - \abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$ .

Démonstration. Fixons un élément $x$ de la réunion et comptons sa contribution au membre de droite. Posons $J = \{i : x \in A_i\}$ , de cardinal $m \geq 1$ . L’élément $x$ est compté une fois dans $\abs{\bigcap_{i \in I} A_i}$ exactement lorsque $\emptyset \neq I \subseteq J$ , avec le signe $(-1)^{\abs I + 1}$ ; sa contribution totale vaut

\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1} = 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1

d’après l’Exemple 2.17. Chaque élément de la réunion est donc compté exactement une fois. ∎

Exemple 2.25 (Dénombrer les entiers premiers avec $120$ )

Combien d’entiers de $\intint1{120}$ sont premiers avec $120 = 2^3 \times 3 \times 5$ ? Un entier a un facteur commun avec $120$ exactement lorsqu’il est divisible par $2$ , $3$ ou $5$ ; comptons donc le complémentaire de $A_2 \cup A_3 \cup A_5$ , où $A_d$ rassemble les multiples de $d$ . Dans $\intint1{120}$ , les multiples de $d$ sont au nombre de $120/d$ dès que $d$ divise $120$ — aucune partie entière n’est nécessaire — et $A_2 \cap A_3 = A_6$ , etc. La formule du crible donne

\abs{A_2 \cup A_3 \cup A_5} = 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,

donc $120 - 88 = 32$ entiers sont premiers avec $120$ . Il est instructif de regrouper le calcul sous forme de produit :

120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 - \frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 32 :

développer les trois parenthèses reproduit exactement les huit termes signés du crible, un par partie de $\{2, 3, 5\}$ . Cette forme multiplicative définit l’indicatrice d’Euler, dont le rôle arithmétique apparaît avec les congruences du Chapitre 6 et se développe dans le volume de Licence 2.

Exemple 2.26 (Dérangements)

Un dérangement est une permutation sans point fixe. Soit $A_i$ l’ensemble des permutations de $\intint{1}{n}$ qui fixent $i$ ; alors $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , et la formule du crible compte les permutations ayant au moins un point fixe ; les dérangements sont donc au nombre de

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

Comme $\sum (-1)^k / k! \to \eu^{-1}$ (voir Chapitre 17), environ $37\,\%$ des permutations sont des dérangements, quel que soit $n$ .

Remarque 2.27 (Où ce chapitre est utilisé)

Les coefficients binomiaux sont les objets de ce chapitre les plus réutilisés : ils font marcher la formule du binôme au Chapitre 8 (développement de $(X + a)^n$ ), la formule de Leibniz pour la dérivée $n$ -ième d’un produit au Chapitre 14, et les coefficients des développements de Taylor au Chapitre 16. Les permutations reviennent en tant que groupe — avec la signature construite en comptant les inversions — au Chapitre 7, et la signature définit à son tour les déterminants au Chapitre 22. La formule du crible et les principes de dénombrement forment l’ossature finie des probabilités discrètes, développées dans le volume de Licence 2 ; les nombres de dérangements de l’Exemple 2.26 sont étudiés en profondeur dans le devoir maison ci-dessous.

2.5 Exercices

Exercice 2.1 ★

Une plaque d’immatriculation est formée de deux lettres (A–Z), puis de trois chiffres, puis de deux lettres. Combien de plaques sont possibles ? Combien sans lettre répétée parmi les quatre ?

Solution

Solution de Exercice 2.1.

Étapes indépendantes et règle du produit : $26^2 \times 10^3 \times 26^2 = 26^4 \times 1000 = 456\,976\,000$ plaques. Si les quatre lettres sont deux à deux distinctes, les étapes des lettres forment un $4$ -arrangement de l’alphabet : $26 \times 25 \times 24 \times 23 = 358\,800$ façons, donc $358\,800 \times 1000 = 358\,800\,000$ plaques.

Exercice 2.2 ★

Combien d’anagrammes (réarrangements des lettres, ayant un sens ou non) possède le mot orange ? Et banana ?

Solution

Solution de Exercice 2.2.

orange a $6$ lettres distinctes : $6! = 720$ anagrammes. banana a $6$ lettres avec répétitions ( $3$ a, $2$ n, $1$ b) : chaque anagramme est déterminé par les positions des a ( $\binom 63$ choix), puis des n parmi les $3$ places restantes ( $\binom 32$ ), le b occupant la dernière place : $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagrammes (de façon équivalente, $6!/(3!\,2!\,1!) = 60$ ).

Exercice 2.3 ★

Un comité de $4$ personnes est choisi parmi $7$ femmes et $5$ hommes. Combien de comités : au total ? avec exactement $2$ femmes ? avec au moins un homme ?

Solution

Solution de Exercice 2.3.

Total : $\binom{12}{4} = 495$ . Exactement $2$ femmes : on les choisit ( $\binom 72 = 21$ ) ainsi que $2$ hommes ( $\binom 52 = 10$ ) : $210$ comités. Au moins un homme : complémentaire de « aucun homme », $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$ .

Exercice 2.4 ★

Démontrer que dans tout groupe de $13$ personnes, deux ont le même mois de naissance ; et que parmi $n + 1$ entiers choisis dans $\intint{1}{2n}$ , deux sont consécutifs. (Les tiroirs les deux fois : nommez les boîtes.)

Solution

Solution de Exercice 2.4.

Anniversaires : les boîtes sont les $12$ mois ; $13$ personnes dans $12$ boîtes en forcent deux dans la même boîte (Corollaire 2.3).

Entiers consécutifs : les boîtes sont les $n$ paires $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ , qui partitionnent $\intint{1}{2n}$ . Choisir $n + 1$ entiers en place deux dans la même paire, et les deux éléments d’une paire sont consécutifs.

Exercice 2.5 ★

Calculer $\sum_{k=0}^{n} k \binom{n}{k}$ . Indication : dériver $(1 + x)^n$ , ou utiliser $k \binom nk = n \binom{n-1}{k-1}$ (le démontrer).

Solution

Solution de Exercice 2.5.

Pour $1 \leq k \leq n$ ,

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

En sommant et en réindexant par $j = k - 1$ :

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

d’après la Proposition 2.15. (Variante : dériver $(1+x)^n = \sum_k \binom nk x^k$ puis faire $x = 1$ .)

Exercice 2.6 ★★

Combien y a-t-il d’applications strictement croissantes de $\intint{1}{k}$ dans $\intint{1}{n}$ ? En déduire le nombre d’applications croissantes (au sens large). Indication pour le second dénombrement : $f$ croissante $\mapsto$ $g(i) = f(i) + i - 1$ .

Solution

Solution de Exercice 2.6.

Une application strictement croissante $f \colon \intint{1}{k} \to \intint{1}{n}$ est déterminée par son image, une partie à $k$ éléments de $\intint{1}{n}$ (on liste la partie dans l’ordre croissant) ; réciproquement, toute partie à $k$ éléments donne exactement une telle application. D’où $\binom nk$ applications strictement croissantes.

Si $f$ est seulement croissante, posons $g(i) = f(i) + i - 1$ . Alors $g$ est strictement croissante (entre deux arguments consécutifs, $f$ gagne $\geq 0$ et $i - 1$ gagne $1$ ) à valeurs dans $\intint{1}{n + k - 1}$ ; et $f(i) = g(i) - i + 1$ reconstitue $f$ à partir de n’importe quelle $g$ strictement croissante à valeurs dans $\intint{1}{n+k-1}$ . C’est une bijection, donc il y a $\binom{n + k - 1}{k}$ applications croissantes.

Exercice 2.7 ★★

(Vandermonde) Démontrer, en comptant les parties à $k$ éléments d’un ensemble scindé en deux blocs de tailles $m$ et $n$ :

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

En déduire $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$ .

Solution

Solution de Exercice 2.7.

Scindons un ensemble $E$ à $m + n$ éléments en deux blocs $M$ ( $m$ éléments) et $N$ ( $n$ éléments). Une partie de $E$ à $k$ éléments contient un certain nombre $j$ d’éléments de $M$ ( $0 \leq j \leq k$ ) et $k - j$ éléments de $N$ ; à $j$ fixé, il y a $\binom mj \binom{n}{k-j}$ telles parties, et les cas $j = 0, \dots, k$ partitionnent les parties à $k$ éléments. La règle de somme 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 $\binom{n}{n-j} = \binom nj$ .

Exercice 2.8 ★★

Combien d’entiers de $\intint{1}{1000}$ sont divisibles par $2$ , $3$ ou $5$ ? (Formule du crible ; $\lfloor 1000/6 \rfloor$ compte les multiples de $6$ , etc.)

Solution

Solution de Exercice 2.8.

Soit $A_d$ l’ensemble des multiples de $d$ dans $\intint{1}{1000}$ , de sorte que $\abs{A_d} = \lfloor 1000/d \rfloor$ . La formule du crible (Théorème 2.24) appliquée à $A_2, A_3, A_5$ , en notant que $A_2 \cap A_3 = A_6$ , etc., donne :

500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .

Donc $734$ entiers sont divisibles par $2$ , $3$ ou $5$ .

Exercice 2.9 ★★

Dénombrer les surjections d’un ensemble à $4$ éléments sur un ensemble à $2$ éléments ; puis sur un ensemble à $3$ éléments. Indication : compter les applications non surjectives par le crible sur les valeurs manquées.

Solution

Solution de Exercice 2.9.

Sur $2$ éléments : les $2^4 = 16$ applications, sauf les $2$ applications constantes : $14$ surjections.

Sur $3$ éléments : par le crible sur les valeurs manquées, le nombre d’applications d’un ensemble à $4$ éléments dans un ensemble à $3$ éléments manquant au moins une valeur vaut $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ; il y a $3^4 = 81$ applications en tout ; surjections : $81 - 45 = 36$ . (Vérification : une surjection d’un ensemble à $4$ éléments sur $3$ éléments double exactement une valeur : on choisit la valeur doublée ( $3$ ), la paire qui s’y envoie ( $\binom 42 = 6$ ), et une bijection pour le reste ( $2$ ) : $3 \times 6 \times 2 = 36$ .)

Exercice 2.10 ★★

(Étoiles et barres) Démontrer que le nombre de sélections de $k$ objets parmi $n$ avec répétition, l’ordre étant ignoré — de façon équivalente, le nombre de $(x_1, \dots, x_n) \in \N^n$ tels que $x_1 + \dots + x_n = k$ — vaut $\binom{n + k - 1}{k}$ . Indication : coder une solution par une rangée de $k$ étoiles et $n - 1$ barres.

Solution

Solution de Exercice 2.10.

Une solution de $x_1 + \dots + x_n = k$ dans $\N^n$ se code par une rangée de $k$ étoiles et $n - 1$ barres : on écrit $x_1$ étoiles, une barre, $x_2$ étoiles, une barre, …, en terminant par $x_n$ étoiles. C’est une bijection sur les mots de longueur $k + n - 1$ formés de $k$ étoiles et $n - 1$ barres, et ces mots sont déterminés par les positions des étoiles : $\binom{n + k - 1}{k}$ . Les sélections avec répétition correspondent aux solutions de l’équation ( $x_i$ = nombre de copies de l’objet $i$ ), donc le dénombrement est le même.

Exercice 2.11 ★★★

Démontrer en détail la formule de l’Exemple 2.26 pour $D_n$ , et en déduire $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (démontrer également cette identité directement, en classant les permutations selon leur ensemble de points fixes).

Solution

Solution de Exercice 2.11.

Avec $A_i = \{\sigma : \sigma(i) = i\}$ , une permutation de $\bigcap_{i \in I} A_i$ fixe chaque $i \in I$ et permute librement les $n - \abs I$ autres points : $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ . La formule du crible :

\Bigl|\bigcup_i A_i\Bigr| = \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,

puisqu’il y a $\binom nk$ parties $I$ de cardinal $k$ . Donc

D_n = n! - \Bigl|\bigcup_i A_i\Bigr| = n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

Pour la seconde identité : classons les permutations $\sigma$ de $\intint{1}{n}$ selon leur ensemble de points fixes $F(\sigma)$ . Pour une partie $F$ à $k$ éléments fixée, les permutations telles que $F(\sigma) = F$ sont exactement les dérangements du complémentaire : il y en a $D_{n-k}$ . En sommant sur les $\binom nk$ choix de $F$ , pour chaque $k$ : $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$ .

Exercice 2.12 ★★★

Pour $n \in \N^*$ , démontrer par un double comptage des couples (partie, élément marqué) :

\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1}, \qquad\text{puis}\qquad \sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .

Pour la seconde : compter les couples d’éléments marqués, égaux ou non.

Solution

Solution de Exercice 2.12.

Première identité. Comptons les couples $(A, a)$ où $A \subseteq E$ ( $\abs E = n$ ) et $a \in A$ . Par taille de $A$ : $\sum_k \binom nk k$ couples. En choisissant d’abord l’élément marqué : $n$ choix pour $a$ , puis n’importe quelle partie des $n - 1$ éléments restants pour compléter $A$ : $n\,2^{n-1}$ couples.

Seconde identité. Comptons les triplets $(A, a, b)$ avec $a, b \in A$ (éventuellement $a = b$ ). Par taille : $\sum_k k^2 \binom nk$ . Directement : soit $a = b$ ( $n\,2^{n-1}$ triplets, dénombrement précédent), soit $a \neq b$ ( $n(n-1)$ choix ordonnés, puis n’importe quelle partie des $n - 2$ autres éléments : $n(n-1)\,2^{n-2}$ ). Au total

n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1) = n(n+1)\,2^{n-2} .

2.6 Problème : les dérangements, ou les lettres mal adressées

Problème 2.1

Une secrétaire glisse au hasard $n$ lettres dans $n$ enveloppes déjà adressées : quelle est la probabilité que personne ne reçoive la bonne lettre ? Cette question classique (Montmort, 1708) conduit aux nombres de dérangements $D_n$ de l’Exemple 2.26. La formule du crible n’est que le coup d’ouverture : ce problème développe les récurrences qui calculent $D_n$ , deux démonstrations indépendantes supplémentaires de la formule, le théorème frappant selon lequel $D_n$ est l’entier le plus proche de $n!/\eu$ , la loi complète des points fixes d’une permutation aléatoire, et la curieuse arithmétique de la suite $(D_n)$ . Dans tout le problème, $D_n$ désigne le nombre de dérangements (permutations sans point fixe) de $\intint1n$ , avec la convention $D_0 = 1$ (la permutation vide n’a pas de point fixe).

Partie I — Petits cas et recensement des points fixes.

Calculer directement $D_1, D_2, D_3$ , et $D_4$ en listant les dérangements de $\{1, 2, 3, 4\}$ groupés selon la valeur de $\sigma(1)$ . (Vous devez trouver $D_4 = 9$ .)
Pour $0 \leq k \leq n$ , montrer que le nombre $P_k(n)$ de permutations de $\intint1n$ ayant exactement $k$ points fixes vaut $\binom nk D_{n-k}$ .
Vérifier le recensement pour $n = 4$ : calculer $P_0(4), \dots, P_4(4)$ et contrôler que leur somme vaut $4! = 24$ . Qu’est-ce qui est le plus probable pour quatre lettres : aucune coïncidence, ou exactement une ?
Par un double comptage (Méthode 2.22) des couples $(\sigma, i)$ tels que $\sigma(i) = i$ , montrer que

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

en moyenne, une permutation aléatoire a exactement un point fixe, quel que soit $n \geq 1$ .

Partie II — Deux récurrences et deux nouvelles démonstrations de la formule.

Démontrer combinatoirement, pour $n \geq 1$ :

$D_{n+1} = n\,(D_n + D_{n-1}) .$

(Classer les dérangements $\sigma$ de $\intint1{n+1}$ selon $j = \sigma(n+1)$ , puis selon que $\sigma(j) = n + 1$ ou non ; dans le cas $\sigma(j) \neq n+1$ , construire une bijection avec les dérangements de $\intint1n$ en redirigeant vers $j$ l’antécédent de $n + 1$ .) Vérifier numériquement la récurrence jusqu’à $D_6$ .
En posant $u_n = D_n - n D_{n-1}$ , déduire de la question 5 que $u_{n+1} = -u_n$ , et conclure à la seconde récurrence :

$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$
À partir de la question 6, démontrer par récurrence la formule de l’Exemple 2.26,

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$

— une démonstration entièrement indépendante du crible.
(Inversion binomiale) Soient $(a_n)$ et $(b_n)$ deux suites telles que $a_n = \sum_{k=0}^n \binom nk b_k$ pour tout $n$ . Démontrer que

$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k \qquad (n \in \N).$

(Établir d’abord l’identité du sous-ensemble d’un sous-ensemble $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$ , puis utiliser la somme alternée d’une ligne du triangle de Pascal de l’Exemple 2.17.)
Appliquer la question 8 à l’identité $n! = \sum_k \binom nk D_{n-k}$ de l’Exercice 2.11 pour obtenir une troisième démonstration de la formule donnant $D_n$ .

Partie III — L’entier le plus proche de $n!/\eu$ . Dans cette partie, on admettra — la théorie est construite au Chapitre 17 — que $\eu^{-1} = \lim_{n \to \infty} s_n$ où $s_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ , avec la majoration stricte des séries alternées $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ pour tout $n$ .

Montrer que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ pour tout $n \in \N$ .
En déduire le théorème vedette : pour tout $n \geq 1$ , $D_n$ est l’entier le plus proche de $n!/\eu$ . Pourquoi l’argument exige-t-il $n \geq 1$ ?
Déterminer le signe de l’erreur : montrer que $D_n > n!/\eu$ exactement lorsque $n$ est pair. (Localiser le premier terme négligé de la série alternée.)
Calculer $D_7$ à $D_{10}$ avec la récurrence de la question 5, puis comparer $D_{10}$ à $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2{,}718281828$ ).
(La probabilité du vestiaire) Soit $p_n = D_n/n!$ la probabilité qu’une permutation tirée uniformément au hasard soit un dérangement. Montrer que $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ et calculer $p_6$ à cinq décimales. Commentaire : pourquoi la réponse à la question de Montmort est-elle essentiellement indépendante de $n$ — et cela dès une douzaine de lettres ?

Partie IV — La loi des points fixes.

Fixons $k \in \N$ . Montrer que la proportion des permutations de $\intint1n$ ayant exactement $k$ points fixes vérifie

$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!} \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$

(Ces valeurs limites, de somme $1$ , forment la loi de Poisson de paramètre $1$ , objet central du cours de probabilités du volume de Licence 2.)
Par un double comptage des triplets $(\sigma, i, j)$ où $i \neq j$ sont tous deux fixés par $\sigma$ , montrer que $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\, (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ pour $n \geq 2$ . Combiné à la question 4 : la moyenne de $\abs{\mathrm{Fix}}^2$ vaut $2$ , donc la « dispersion » (variance) du nombre de points fixes vaut $1$ — là encore indépendante de $n$ , là encore conforme à la loi de Poisson.
Calculer la proportion des permutations ayant au moins un point fixe pour $n = 4, 5, 6$ (en fractions et à quatre décimales), et comparer avec $1 - \eu^{-1} \approx 0{,}6321$ .
Montrer directement — sans aucun passage à la limite — que $s_{n+2} - s_n = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , et en déduire que les probabilités $p_n = s_n$ de la question 14 oscillent : $p_0 > p_2 > p_4 > \dots$ et $p_1 < p_3 < p_5 < \dots$ , les valeurs paires (resp. impaires) décroissant (resp. croissant) vers la limite commune $\eu^{-1}$ .
(Père Noël secret) $n$ personnes tirent chacune un nom dans un chapeau ; si l’une d’elles tire son propre nom, tout le tirage est recommencé de zéro. En utilisant le fait standard qu’un événement de probabilité $p$ demande en moyenne $1/p$ tentatives, estimer le nombre moyen de tirages complets nécessaires, et conclure que la procédure coûte en moyenne environ $\eu \approx 2{,}72$ tirages, essentiellement indépendamment de $n$ .

Partie V — L’arithmétique de $D_n$ , et une synthèse.

Affiner la question 5 : montrer que, pour $j \in \intint2n$ fixé, les dérangements de $\intint1n$ tels que $\sigma(1) = j$ sont exactement au nombre de $D_{n-1} + D_{n-2}$ , indépendamment de $j$ . En déduire que $n - 1$ divise $D_n$ pour tout $n \geq 2$ .
Démontrer que $D_n$ est impair si et seulement si $n$ est pair. (Travailler modulo $2$ dans la récurrence de la question 6.)
Démontrer que $D_n \equiv (-1)^n \pmod n$ pour $n \geq 1$ , et vérifier la congruence sur le dernier chiffre de $D_{10}$ .
Déduire de la question 6 que $\dfrac{D_n}{D_{n-1}} = n + \dfrac{(-1)^n}{D_{n-1}}$ pour $n \geq 3$ , de sorte que le rapport de deux nombres de dérangements consécutifs vaut presque exactement $n$ ; expliquer en une phrase pourquoi cela est cohérent avec $D_n \approx n!/\eu$ .
Où exactement ce problème a-t-il utilisé : (i) les règles de produit et de somme ; (ii) le double comptage ; (iii) la formule du binôme ; (iv) la majoration admise des séries alternées ? Une phrase chacun.
Synthèse. La formule donnant $D_n$ a maintenant trois démonstrations (le crible ; la relation de récurrence suivie d’une démonstration par récurrence ; l’inversion binomiale). En un court paragraphe, comparer ce que chaque démonstration explique : laquelle calcule le plus vite, laquelle se généralise à d’autres dénombrements de points fixes, et laquelle révèle pourquoi $\eu$ apparaît dans un problème d’enveloppes.

Solution

Solution de Problème 2.1.

1. $D_1 = 0$ (l’unique permutation fixe $1$ ), $D_2 = 1$ (l’échange), $D_3 = 2$ (en notation à une ligne : $231$ et $312$ ). Pour $n = 4$ , groupons selon $\sigma(1)$ : pour $\sigma(1) = 2$ , les dérangements sont $2143$ , $2341$ , $2413$ ; pour $\sigma(1) = 3$ : $3142$ , $3412$ , $3421$ ; pour $\sigma(1) = 4$ : $4123$ , $4312$ , $4321$ . Trois dans chaque groupe : $D_4 = 9$ .

2. Une permutation ayant exactement $k$ points fixes est déterminée par le choix de son ensemble de points fixes $F$ ( $\binom nk$ façons) et par sa restriction au complémentaire, qui doit être une permutation de $n - k$ points sans point fixe ( $D_{n-k}$ façons). Les deux choix sont indépendants et la correspondance est bijective : $P_k(n) = \binom nk D_{n-k}$ .

3. $P_0(4) = D_4 = 9$ ; $P_1(4) = \binom41 D_3 = 4 \times 2 = 8$ ; $P_2(4) = \binom42 D_2 = 6$ ; $P_3(4) = \binom43 D_1 = 0$ (trois points fixes en forcent un quatrième) ; $P_4(4) = 1$ . Somme : $9 + 8 + 6 + 0 + 1 = 24 = 4!$ . Aucune coïncidence ( $9$ cas) l’emporte sur exactement une coïncidence ( $8$ cas) — de peu.

4. Comptons les couples $(\sigma, i)$ tels que $\sigma(i) = i$ . À $i$ fixé, les permutations qui fixent $i$ sont les permutations des $n - 1$ autres points : il y en a $(n-1)!$ . Le nombre de couples vaut donc $n \cdot (n-1)! = n!$ , et ce nombre est aussi $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$ . En divisant par le nombre $n!$ de permutations : le nombre moyen de points fixes vaut exactement $1$ , pour tout $n \geq 1$ .

5. Soit $\sigma$ un dérangement de $\intint1{n+1}$ et $j = \sigma(n+1) \in \intint1n$ : $n$ valeurs possibles. Cas $\sigma(j) = n+1$ : les points $j$ et $n+1$ s’échangent, et $\sigma$ restreinte aux $n - 1$ points restants en est un dérangement arbitraire : $D_{n-1}$ possibilités. Cas $\sigma(j) \neq n+1$ : posons $i_0 = \sigma^{-1}(n+1)$ ; ici $i_0 \neq j$ et $i_0 \leq n$ . Définissons $\tau$ sur $\intint1n$ par $\tau(i) = \sigma(i)$ pour $i \neq i_0$ et $\tau(i_0) = j$ . Alors $\tau$ est une permutation de $\intint1n$ (la valeur $n+1$ a été remplacée par la valeur manquante $j$ ), et c’est un dérangement : $\tau(i_0) = j \neq i_0$ , et $\tau(i) = \sigma(i) \neq i$ ailleurs. Réciproquement, à partir d’un dérangement $\tau$ de $\intint1n$ et de la valeur $j$ , on retrouve $\sigma$ en posant $\sigma(n+1) = j$ , $\sigma(\tau^{-1}(j)) = n+1$ et $\sigma = \tau$ ailleurs : c’est une bijection, d’où $D_n$ possibilités. En sommant sur $j$ : $D_{n+1} = n(D_n + D_{n-1})$ . Numériquement : $D_5 = 4(9 + 2) = 44$ , $D_6 = 5(44 + 9) = 265$ .

6. D’après la question 5, $D_{n+1} = nD_n + nD_{n-1}$ , donc

u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n = -(D_n - nD_{n-1}) = -u_n .

Comme $u_1 = D_1 - 1 \cdot D_0 = -1$ , une récurrence donne $u_n = (-1)^n$ , c’est-à-dire $D_n = nD_{n-1} + (-1)^n$ pour $n \geq 1$ .

7. Récurrence sur $n$ . Initialisation : $D_0 = 1 = 0!\,s_0$ . Hérédité : en supposant $D_{n-1} = (n-1)!\,s_{n-1}$ ,

D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n = n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,

ce qui est la formule. Aucun crible n’a été utilisé : seulement la récurrence combinatoire de la question 5.

8. Identité du sous-ensemble d’un sous-ensemble, par les factorielles :

\binom nk \binom kj = \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!} = \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!} = \binom nj \binom{n-j}{k-j} .

Substituons maintenant $a_k = \sum_j \binom kj b_j$ et échangeons les deux sommes finies :

\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k = \sum_{j=0}^{n} b_j \binom nj \sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j} = \sum_{j=0}^{n} b_j \binom nj \sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .

D’après la formule du binôme (Théorème 2.16), la somme intérieure est le développement de $(1 + (-1))^{n-j} = 0^{n-j}$ : elle s’annule pour $j < n$ et vaut $1$ pour $j = n$ . Seul $j = n$ subsiste, et le membre de droite vaut $b_n$ , comme annoncé.

9. Par la symétrie $\binom nk = \binom n{n-k}$ , l’identité de l’Exercice 2.11 se réécrit $n! = \sum_{k=0}^n \binom nk D_k$ . Appliquons la question 8 avec $a_n = n!$ et $b_k = D_k$ :

D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k! = \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!} = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,

en réindexant par $j = n - k$ : la formule pour la troisième fois.

10. $D_n = n!\,s_n$ (question 7), donc

\Bigl| D_n - \frac{n!}{\eu} \Bigr| = n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .

11. Pour $n \geq 1$ , $\frac1{n+1} \leq \frac12$ , et l’inégalité de la question 10 est stricte : $D_n$ est à distance $< \frac12$ de $n!/\eu$ , donc c’est l’unique entier le plus proche. Pour $n = 0$ , la majoration ne donne qu’une distance $< 1$ , et l’énoncé est d’ailleurs faux dans ce cas : $0!/\eu \approx 0{,}368$ a pour entier le plus proche $0$ , alors que $D_0 = 1$ .

12. $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ est une série alternée dont les termes décroissent strictement, donc son signe est celui de son premier terme $(-1)^{n+1}/(n+1)!$ . Ainsi $s_n - \eu^{-1}$ a le signe de $(-1)^n$ : pour $n$ pair, $s_n > \eu^{-1}$ et $D_n = n!\,s_n > n!/\eu$ ; pour $n$ impair, $D_n < n!/\eu$ .

13. $D_7 = 6(265 + 44) = 6 \times 309 = 1854$ ; $D_8 = 7(1854 + 265) = 7 \times 2119 = 14\,833$ ; $D_9 = 8(14\,833 + 1854) = 8 \times 16\,687 = 133\,496$ ; $D_{10} = 9(133\,496 + 14\,833) = 9 \times 148\,329 = 1\,334\,961$ . Vérification : $10!/\eu = 3\,628\,800 / 2{,}718281828 \approx 1\,334\,960{,}92$ , dont l’entier le plus proche est $1\,334\,961$ — et $D_{10} > 10!/\eu$ , comme la question 12 le prédit pour $n$ pair.

14. $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} < \frac1{(n+1)!}$ . Pour $n = 6$ : $p_6 = 265/720 = 0{,}36806$ (cinq décimales), contre $\eu^{-1} = 0{,}36788$ ; l’écart est inférieur à $1/7! = 1/5040 < 2 \times 10^{-4}$ . La majoration $1/(n+1)!$ s’effondre si vite que la probabilité est fixée à de nombreuses décimales dès une douzaine de lettres : la réponse « environ $36{,}8\,\%$ » est, à toutes fins pratiques, indépendante de $n$ — la fameuse surprise du problème.

15. D’après la question 2 et $D_m = m!\,s_m$ :

\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!} = \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!} \;\longrightarrow\; \frac{\eu^{-1}}{k!}

quand $n \to \infty$ à $k$ fixé, puisque $s_{n-k} \to \eu^{-1}$ . Les valeurs limites $\eu^{-1}/k!$ ( $k \in \N$ ) sont les poids de la loi de Poisson de paramètre $1$ .

16. Comptons les triplets $(\sigma, i, j)$ avec $i \neq j$ , $\sigma(i) = i$ , $\sigma(j) = j$ . En choisissant d’abord le couple ordonné : $n(n-1)$ façons ; les permutations qui fixent à la fois $i$ et $j$ sont les permutations des $n - 2$ points restants : il y en a $(n-2)!$ . Total : $n(n-1)(n-2)! = n!$ . En sommant plutôt d’abord sur $\sigma$ , on compte, pour chaque $\sigma$ , les couples ordonnés de points fixes distincts : $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$ . D’où l’identité annoncée ; en divisant par $n!$ , la moyenne de $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ vaut $1$ , donc la moyenne de $\abs{\mathrm{Fix}}^2$ vaut $1 + 1 = 2$ et la variance vaut $2 - 1^2 = 1$ .

17. Les proportions $1 - p_n$ : pour $n = 4$ , $1 - \frac 9{24} = \frac{15}{24} = 0{,}6250$ ; pour $n = 5$ , $1 - \frac{44}{120} = \frac{76}{120} = 0{,}6333$ ; pour $n = 6$ , $1 - \frac{265}{720} = \frac{455}{720} = 0{,}6319$ . Toutes à moins d’un pour cent de $1 - \eu^{-1} \approx 0{,}6321$ , en oscillant autour.

18. Directement :

s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} + \frac{(-1)^{n+2}}{(n+2)!} = (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),

et la parenthèse est $> 0$ . Pour $n$ pair la différence est négative : $s_{n+2} < s_n$ , donc $p_0 > p_2 > p_4 > \dots$ ; pour $n$ impair elle est positive : $p_1 < p_3 < p_5 < \dots$ Combiné à la question 12 (les rangs pairs au-dessus de $\eu^{-1}$ , les impairs en dessous) et à la question 14 (la distance à $\eu^{-1}$ tend vers $0$ ) : les deux escaliers encadrent $\eu^{-1}$ .

19. Un tirage complet est une permutation aléatoire uniforme, valide lorsque c’est un dérangement : probabilité $p_n \approx \eu^{-1}$ . D’après le fait cité, le nombre moyen de tirages nécessaires jusqu’au succès vaut $1/p_n$ , et la question 14 donne $1/p_n \approx \eu$ à une erreur près qui est négligeable dès les petites valeurs de $n$ . Un Père Noël secret avec relances coûte donc en moyenne environ $\eu \approx 2{,}72$ tirages complets — que le bureau compte $6$ personnes ou $600$ .

20. Fixons $j \geq 2$ et reprenons la classification de la question 5 sur la valeur $\sigma(1) = j$ . Si $\sigma(j) = 1$ : les $n - 2$ points restants portent un dérangement arbitraire, $D_{n-2}$ façons. Si $\sigma(j) \neq 1$ : on redirige vers $j$ l’antécédent $i_0 = \sigma^{-1}(1)$ exactement comme à la question 5 ; c’est une bijection avec les dérangements des $n - 1$ points $\{2, \dots, n\}$ : $D_{n-1}$ façons. Au total $D_{n-1} + D_{n-2}$ , le même pour chaque $j$ . En sommant sur les $n - 1$ valeurs de $j$ : $D_n = (n-1)(D_{n-1} + D_{n-2})$ , ce qui fait apparaître le facteur $n - 1$ : $(n-1) \mid D_n$ .

21. Affirmation : $D_n$ est impair si et seulement si $n$ est pair. Récurrence à l’aide de $D_n = nD_{n-1} + (-1)^n$ , c’est-à-dire $D_n \equiv nD_{n-1} + 1 \pmod 2$ . Initialisation : $D_1 = 0$ est pair, et $n = 1$ est impair : l’affirmation est vraie. Si $n$ est pair, $nD_{n-1}$ est pair et $D_n \equiv 1$ : impair, comme annoncé. Si $n$ est impair, alors $n - 1$ est pair, donc $D_{n-1}$ est impair par hypothèse, et $D_n \equiv D_{n-1} + 1 \equiv 0$ : pair. La récurrence est close.

22. Réduire $D_n = nD_{n-1} + (-1)^n$ modulo $n$ tue le premier terme : $D_n \equiv (-1)^n \pmod n$ . Pour $n = 10$ : $(-1)^{10} = 1$ , et de fait $D_{10} = 1\,334\,961$ se termine par le chiffre $1$ .

23. Pour $n \geq 3$ , $D_{n-1} \geq 1$ et la division de la récurrence de la question 6 par $D_{n-1}$ donne $D_n/D_{n-1} = n + (-1)^n/D_{n-1}$ , avec $\abs{(-1)^n/D_{n-1}} \leq 1$ tendant rapidement vers $0$ . Cohérence : si $D_n \approx n!/\eu$ , alors $D_n/D_{n-1} \approx n!/(n-1)! = n$ — le facteur $\eu$ se simplifie dans le rapport, et la récurrence le confirme à la précision $1/D_{n-1}$ .

24. (i) Les règles de produit et de somme sous-tendent chaque dénombrement : les questions 2 et 5 partitionnent des ensembles de permutations en étapes indépendantes. (ii) Le double comptage a donné la moyenne (question 4) et la variance (question 16) du nombre de points fixes, sans aucune formule pour $D_n$ . (iii) La formule du binôme a évalué la somme intérieure alternée $(1-1)^{n-j}$ qui fait fonctionner l’inversion binomiale (question 8). (iv) La majoration des séries alternées a converti la somme exacte mais opaque $n!\,s_n$ en l’énoncé transparent « l’entier le plus proche de $n!/\eu$ » (questions 10 à 14).

25. La formule du crible (Exemple 2.26 et Exercice 2.11) est la démonstration conceptuelle : elle explique la somme alternée comme une suite de corrections de surcomptage, et elle se généralise mot pour mot au dénombrement des éléments évitant une famille quelconque d’ensembles « mauvais ». La voie de la récurrence (questions 5 à 7) calcule le plus vite — en temps linéaire, en arithmétique entière exacte, sans factorielles — et c’est la source des faits arithmétiques de la partie V. L’inversion binomiale (questions 8 et 9) place la formule dans une transformation générale qui reparaîtra partout où deux systèmes triangulaires d’identités se font face. Et l’apparition de $\eu$ est le mieux expliquée par la formule elle-même : la proportion de dérangements est la somme partielle $s_n$ de la série donnant $\eu^{-1}$ , de sorte que les enveloppes de Montmort calculaient déjà le nombre $\eu$ , trois décennies avant la notation d’Euler.