---
title: "Dénombrement"
book: "Mathématiques universitaires — Licence 1"
subject: math
language: fr
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/fr/chapter/2-denombrement
---

# Chapitre 2 — Dénombrement

Dénombrer les [ensembles finis](#def-b1-counting-card) a l’air élémentaire — et devient vite subtil. Ce chapitre définit proprement le [cardinal](#def-b1-counting-card) (par les [bijections](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), dans l’esprit du [Chapitre 1](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#ch-b1-logic)), établit la poignée de principes de dénombrement dont tout découle, puis en déduit les dénombrements classiques : listes, [permutations](#def-b1-counting-objects), 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $E$ est *fini* lorsque $E = \emptyset$ ou qu’il existe une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\intint{1}{n}$ sur $E$ pour un certain $n \in \N^*$ ; ce $n$ est alors unique ([Théorème 2.2](#thm-b1-counting-welldef)) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\intint{1}{m}$ sur $\intint{1}{n}$. Plus précisément, si $m > n$, il n’existe pas d’[injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\intint{1}{m}$ dans $\intint{1}{n}$.

**Démonstration.** Démontrons par récurrence sur $n$ l’[assertion](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-statement) : *pour tout $m > n$, il n’existe pas d’[injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) $\intint{1}{m} \to \intint{1}{n}$*. Pour $n = 0$, l’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) d’arrivée est vide et $m \geq 1$ : aucune [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) n’existe. Supposons l’[assertion](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-statement) vraie au rang $n$, et soit $f \colon
\intint{1}{m} \to \intint{1}{n+1}$ une [injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) avec $m > n + 1$. Si la valeur $n + 1$ n’est pas atteinte, $f$ est une [injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) $g$ vérifie $g(m) = n + 1$. Alors la restriction de $g$ à $\intint{1}{m-1}$ est une [injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) dans $\intint{1}{n}$ avec $m - 1 > n$ — nouvelle contradiction. ∎

**Corollaire 2.3 (Principe des tiroirs).**

Si $\abs{E} > \abs{F}$, aucune [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) $f \colon E \to F$ n’est [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) : 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) $u \colon \intint1m \to E$ et $v \colon F \to \intint1n$. Si $f$ était [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), $v \circ f \circ u$ serait une [injection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\intint1m$ dans $\intint1n$ (composée d’[injections](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), [Proposition 1.26](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#prop-b1-logic-comp)), ce qui contredirait le [Théorème 2.2](#thm-b1-counting-welldef). ∎

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

La démonstration du [Théorème 2.2](#thm-b1-counting-welldef) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de départ *et* le dernier point $n+1$ de l’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) ailleurs. Le remède : composer $f$ avec la transposition des deux *valeurs* $f(a)$ et $f(m)$ — une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de l’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) d’arrivée, donc l’[injectivité](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](#def-b1-counting-objects) tout au long du problème du [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures) sur le groupe symétrique.

**Proposition 2.5 (Injections, surjections et cardinal).**

Soient $E, F$ des [ensembles finis](#def-b1-counting-card) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj). Alors $f$ est une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $E$ dans $F \setminus \{y_0\}$, [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de [cardinal](#def-b1-counting-card) $\abs{F} - 1 < \abs{E}$ — impossible d’après le [principe des tiroirs](#cor-b1-counting-pigeonhole). Donc $f(E) = F$ : $f$ est [surjective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), donc [bijective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj).

Supposons $f$ [surjective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj). 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) ([Proposition 1.26](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#prop-b1-logic-comp)). D’après le paragraphe précédent appliqué à $s$ (les cardinaux sont égaux), $s$ est [bijective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj). De $f \circ s =
\mathrm{id}_F$ on tire $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$, donc $f$ est [bijective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj). Enfin, une [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) [bijective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) est par définition à la fois [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) et [surjective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), ce qui referme le cycle d’implications. ∎

**Exemple 2.6 (La finitude est essentielle).**

Sur un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) *[fini](#def-b1-counting-card)*, la [Proposition 2.5](#prop-b1-counting-injsur) est un raccourci puissant : toute [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $E$ dans lui-même est automatiquement une [permutation](#def-b1-counting-objects) de $E$ — la moitié de la [bijectivité](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) est offerte. Les deux implications s’effondrent sur les [ensembles](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) infinis : $n \mapsto n + 1$ est [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\N$ dans $\N$ mais rate $0$, et l’[application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) $\N \to \N$ qui envoie $0 \mapsto 0$ et $n \mapsto n - 1$ pour $n \geq 1$ est [surjective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) sans être [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj). 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#ch-b1-logic) explore par l’autre bout, là où les [ensembles](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) infinis sont précisément ceux qui admettent de telles [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) d’eux-mêmes dans eux-mêmes.

**Exemple 2.7 (La moitié du travail, gratuitement).**

Considérons l’[application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) $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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) ? L’[injectivité](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) suffit à elle seule ([Proposition 2.5](#prop-b1-counting-injsur)) : 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 secondaire et démontré au [Chapitre 6](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith)) ; avec $\abs{k - k'} \leq 6$ cela force $k = k'$. La [surjectivité](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith)), 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) si et seulement s’il est [surjectif](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) » ([Chapitre 19](https://one-course.com/books/math/3/fr/chapter/19-dimension-finie#ch-b1-findim)).

## 2.2 Les principes de dénombrement

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

Soient $E, F$ des [ensembles finis](#def-b1-counting-card).

1. Si $E \cap F = \emptyset$ , alors $\abs{E \cup F} = \abs{E} +  \abs{F}$ ; plus généralement, pour une [partition](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#thm-b1-logic-partition) de $E$ en parties $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
2. En général, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap  F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. L’ [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $F^E$ des [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) de $E$ dans $F$ vérifie $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) é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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $\{x\} \times F$, chacun de [cardinal](#def-b1-counting-card) $\abs{F}$ ; on applique (1).

(4) Une [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), et $\abs{F^m} = \abs{F}^m$ par (3) et récurrence.

(5) Les parties de $E$ correspondent bijectivement aux [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) $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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) déguisée ([Méthode 2.19](#met-b1-counting-which)).

![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.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-c18b678ecdd9.svg)

*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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) avec $\abs{E} = n$, et soit $0 \leq k \leq n$.

- Un *$k$-arrangement* de $E$ est un $k$ -uplet [injectif](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) d’éléments de $E$ (une sélection ordonnée sans répétition) ;
- une *permutation* de $E$ est une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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$ :

1. le nombre de $k$ -arrangements de $E$ vaut $n (n-1) \cdots  (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
2. le nombre de [permutations](#def-b1-counting-objects) de $E$ vaut $n!$ ;
3. $\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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) à 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) entre les parties à $k$ éléments et celles à $n-k$ éléments. [Formule de Pascal](#prop-b1-counting-identities) : 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](#prop-b1-counting-rules) (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](#prop-b1-counting-identities).) ∎

**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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) non vide, exactement la moitié sont de [cardinal](#def-b1-counting-card) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $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](#exo-b1-counting-10)) |

Cherchez ensuite une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) ou une [partition](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#thm-b1-logic-partition) ramenant le problème à ces dénombrements modèles ; un dénombrement correct est une [bijection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) déguisée.

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

1. *Sommer des cas non disjoints.* La règle de somme exige une [partition](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#thm-b1-logic-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](#thm-b1-counting-inclexcl) ) ou une disjonction de cas plus fine.
2. *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.
3. *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.
4. *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](#ex-b1-counting-complement) ).

**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](#def-b1-counting-card) que les deux membres comptent — typiquement un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de *couples* — et évaluez son [cardinal](#def-b1-counting-card) 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](#exo-b1-counting-12) et plusieurs questions du devoir maison ci-dessous.

**Exemple 2.23 (La partie moyenne).**

Quel est le [cardinal](#def-b1-counting-card) moyen d’une partie d’un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $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](#exo-b1-counting-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](#def-b1-counting-card) $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](#def-b1-counting-card) $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](#ex-b1-counting-binomial). Chaque élément de la réunion est donc compté exactement une fois. ∎

**Exemple 2.25 (Dénombrer les entiers premiers avec 120120120).**

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](https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers#ch-b1-arith) et se développe dans le volume de Licence 2.

**Exemple 2.26 (Dérangements).**

Un *dérangement* est une [permutation](#def-b1-counting-objects) sans point fixe. Soit $A_i$ l’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) des [permutations](#def-b1-counting-objects) 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](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/fr/chapter/17-series-numeriques#ch-b1-series)), environ $37\,\%$ des [permutations](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly) (développement de $(X + a)^n$), la formule de Leibniz pour la dérivée $n$-ième d’un produit au [Chapitre 14](https://one-course.com/books/math/3/fr/chapter/14-derivation#ch-b1-derivative), et les coefficients des développements de Taylor au [Chapitre 16](https://one-course.com/books/math/3/fr/chapter/16-formules-de-taylor-et-developpements-limites#ch-b1-taylor). Les [permutations](#def-b1-counting-objects) reviennent en tant que groupe — avec la signature construite en comptant les inversions — au [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures), et la signature définit à son tour les déterminants au [Chapitre 22](https://one-course.com/books/math/3/fr/chapter/22-determinants-et-systemes-lineaires#ch-b1-det). 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](#ex-b1-counting-derangement) 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 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 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 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 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](#cor-b1-counting-pigeonhole)).

*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 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](#prop-b1-counting-identities). (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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) strictement croissantes de $\intint{1}{k}$ dans $\intint{1}{n}$ ? En déduire le nombre d’[applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) croissantes (au sens large). *Indication pour le second dénombrement : $f$ croissante $\mapsto$ $g(i) = f(i) + i - 1$.*

**Solution de Exercice 2.6.**

Une [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map). D’où $\binom nk$ [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), donc il y a $\binom{n + k - 1}{k}$ [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) croissantes.

**Exercice 2.7 ★★.**

(Vandermonde) Démontrer, en comptant les parties à $k$ éléments d’un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) 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 de Exercice 2.7.**

Scindons un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $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 de Exercice 2.8.**

Soit $A_d$ l’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) 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](#thm-b1-counting-inclexcl)) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) d’un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à $4$ éléments sur un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à $2$ éléments ; puis sur un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à $3$ éléments. *Indication : compter les [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) non [surjectives](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) par le crible sur les valeurs manquées.*

**Solution de Exercice 2.9.**

Sur $2$ éléments : les $2^4 = 16$ [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map), sauf les $2$ [applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) constantes : $14$ [surjections](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj).

Sur $3$ éléments : par le crible sur les valeurs manquées, le nombre d’[applications](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) d’un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à $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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) en tout ; [surjections](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) : $81 - 45 = 36$. (Vérification : une [surjection](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) d’un [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à $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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](#ex-b1-counting-derangement) 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](#def-b1-counting-objects) selon leur [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de points fixes).

**Solution de Exercice 2.11.**

Avec $A_i = \{\sigma : \sigma(i) = i\}$, une [permutation](#def-b1-counting-objects) 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](#def-b1-counting-card) $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](#def-b1-counting-objects) $\sigma$ de $\intint{1}{n}$ selon leur [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de points fixes $F(\sigma)$. Pour une partie $F$ à $k$ éléments fixée, les [permutations](#def-b1-counting-objects) 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 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](#ex-b1-counting-derangement). 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](#def-b1-counting-objects) 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](#def-b1-counting-objects) sans point fixe) de $\intint1n$, avec la convention $D_0 = 1$ (la [permutation](#def-b1-counting-objects) vide n’a pas de point fixe).

**Partie I — Petits cas et recensement des points fixes.**

1. 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$ .)
2. Pour $0 \leq k \leq n$ , montrer que le nombre $P_k(n)$ de [permutations](#def-b1-counting-objects) de $\intint1n$ ayant *exactement* $k$ points fixes vaut $\binom nk D_{n-k}$ .
3. 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 ?
4. Par un double comptage ([Méthode 2.22](#met-b1-counting-doublecount)) des couples $(\sigma, i)$ tels que $\sigma(i) = i$, montrer que $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ en moyenne, une [permutation](#def-b1-counting-objects) 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.**

5. 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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$.
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).$$
7. À partir de la question 6, démontrer par récurrence la formule de l’[Exemple 2.26](#ex-b1-counting-derangement), $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — une démonstration entièrement indépendante du crible.
8. (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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) d’un [sous-ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets)* $\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](#ex-b1-counting-binomial).)
9. Appliquer la question 8 à l’identité $n! = \sum_k \binom nk  D_{n-k}$ de l’ [Exercice 2.11](#exo-b1-counting-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](https://one-course.com/books/math/3/fr/chapter/17-series-numeriques#ch-b1-series) — 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$.

10. Montrer que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ pour tout $n \in \N$ .
11. 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$ ?
12. 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.)
13. 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$ ).
14. (La probabilité du vestiaire) Soit $p_n = D_n/n!$ la probabilité qu’une [permutation](#def-b1-counting-objects) 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.**

15. Fixons $k \in \N$. Montrer que la proportion des [permutations](#def-b1-counting-objects) 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.)
16. 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.
17. Calculer la proportion des [permutations](#def-b1-counting-objects) 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$ .
18. 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}$ .
19. (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.**

20. 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$ .
21. 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.)
22. 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}$ .
23. 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$ .
24. 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.
25. 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 de Problème 2.1.**

**1.** $D_1 = 0$ (l’unique [permutation](#def-b1-counting-objects) 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](#def-b1-counting-objects) ayant exactement $k$ points fixes est déterminée par le choix de son [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de points fixes $F$ ($\binom nk$ façons) et par sa restriction au complémentaire, qui doit être une [permutation](#def-b1-counting-objects) de $n - k$ points *sans* point fixe ($D_{n-k}$ façons). Les deux choix sont indépendants et la correspondance est [bijective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) : $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](#def-b1-counting-objects) qui fixent $i$ sont les [permutations](#def-b1-counting-objects) 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](#def-b1-counting-objects) : 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](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj), 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) d’un [sous-ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets), 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](#def-b1-counting-card) :

$$
\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](#thm-b1-counting-binomial)), 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](#exo-b1-counting-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](#def-b1-counting-objects) qui fixent à la fois $i$ et $j$ sont les [permutations](#def-b1-counting-objects) 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](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) 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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) de [permutations](#def-b1-counting-objects) 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](#ex-b1-counting-derangement) et [Exercice 2.11](#exo-b1-counting-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](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) « 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.