Problème — La formule d'inversion de Pascal : surjections et dérangements

Exercice de TD · niveau 3 (difficile) · mathématiques (PTSI), chapitre 15 — Dénombrement · D. Problèmes et doubles comptages

Énoncé

1) (Deux outils) Montrer que $\sum_{j = 0}^{m} (- 1)^{j} (j m) = 0$ pour tout entier $m \geq 1$ . Rappeler, d'après l'exercice 7, que $(k n) (j k) = (j n) (k - j n - j)$ pour $0 \leq j \leq k \leq n$ .

2) (Inversion) Soient $(f_{n})_{n \in N}$ et $(g_{n})_{n \in N}$ deux suites réelles telles que $f_{n} = \sum_{k = 0}^{n} (k n) g_{k}$ pour tout $n$ . Montrer que $g_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (k n) f_{k}$ pour tout $n$ (écrire une somme triangulaire, puis utiliser le 1)).

3) (Surjections) Soit $n \geq 1$ . Pour $p \in N$ , on note $s (n, p)$ le nombre de surjections d'un ensemble à $n$ éléments sur un ensemble à $p$ éléments (donc $s (n, 0) = 0$ ). En classant les applications de $E$ dans $F$ , où $∣ E ∣ = n$ et $∣ F ∣ = p$ , selon leur image, montrer que $p^{n} = \sum_{k = 0}^{p} (k p) s (n, k)$ ; en déduire $s (n, p) = \sum_{k = 0}^{p} (- 1)^{p - k} (k p) k^{n}$ .

4) (Contrôles) Vérifier que $s (n, 2) = 2^{n} - 2$ , que $s (n, n) = n!$ et que $s (n, n - 1) = (2 n) (n - 1)!$ pour $n \geq 2$ . Justifier que $s (n, p) = 0$ pour $p > n$ ; que dit ce dernier point de la somme $\sum_{k = 0}^{p} (- 1)^{k} (k p) k^{n}$ ?

5) (Dérangements) On note $d_{n}$ le nombre de permutations de ${1, \dots, n}$ sans point fixe, avec $d_{0} = 1$ . En classant les permutations selon leur ensemble de points fixes, montrer que $n! = \sum_{k = 0}^{n} (k n) d_{k}$ ; en déduire $d_{n} = n! \sum_{j = 0}^{n} \frac{( - 1 ) ^{j}}{j !}$ , puis $d_{1}, \dots, d_{5}$ .

6) (Un peu plus d'un tiers) À l'aide de l'inégalité de Taylor-Lagrange appliquée à l'exponentielle sur $[- 1, 0]$ , montrer que $\frac{d _{n}}{n !} - \frac{1}{e} \leq \frac{1}{( n + 1 )!}$ ; en déduire que $\frac{d _{n}}{n !}$ tend vers $\frac{1}{e}$ , puis que $d_{n}$ est l'entier le plus proche de $\frac{n !}{e}$ pour tout $n \geq 1$ . Énoncer le théorème obtenu.

Corrigé

1) Les deux outils. Pour $m \geq 1$ , la formule du binôme avec $a = - 1$ et $b = 1$ donne $\sum_{j = 0}^{m} (j m) (- 1)^{j} = (- 1 + 1)^{m} = 0$ ; pour $m = 0$ , la somme vaut $1$ . La seconde identité est celle du comité et du bureau, exercice 7 b), avec un comité de $k$ personnes et un bureau de $j$ membres.

2) L'inversion. La stratégie : remplacer chaque $f_{k}$ par sa définition, intervertir les deux sommes, et reconnaître un binôme en $(1 - 1)$ . Pour $n$ fixé : $k = 0 \sum n (- 1)^{n - k} (k n) f_{k} = k = 0 \sum n j = 0 \sum k (- 1)^{n - k} (k n) (j k) g_{j} .$ La somme porte sur le triangle $0 \leq j \leq k \leq n$ ; en l'écrivant d'abord selon $j$ , pour $j$ de $0$ à $n$ , puis selon $k$ de $j$ à $n$ — les bornes changent, c'est le point délicat des sommes triangulaires —, et en utilisant la seconde identité du 1) : $j = 0 \sum n g_{j} (j n) k = j \sum n (- 1)^{n - k} (k - j n - j) .$ Posons $i = k - j$ , de $0$ à $m = n - j$ : la somme intérieure est $\sum_{i = 0}^{m} (- 1)^{m - i} (i m) = (1 - 1)^{m}$ par le binôme, nulle pour $m \geq 1$ et égale à $1$ pour $m = 0$ , c'est-à-dire pour $j = n$ . Il ne reste que $g_{n} (n n) = g_{n}$ : la relation triangulaire est inversée.

3) Les surjections. Le classement. Chaque application $ϕ : E \to F$ a une image $ϕ (E)$ , qui est une partie de $F$ ; classons les $p^{n}$ applications selon cette image — les classes sont disjointes et recouvrent tout. Les applications d'image exactement $B$ sont les applications de $E$ dans $B$ qui atteignent tous les éléments de $B$ , c'est-à-dire les surjections de $E$ sur $B$ : il y en a $s (n, ∣ B ∣)$ , ce nombre ne dépendant que du cardinal de $B$ . Il y a $(k p)$ parties $B$ à $k$ éléments, d'où, par le principe d'addition, $p^{n} = k = 0 \sum p (k p) s (n, k),$ la classe $k = 0$ étant vide puisque $E$ n'est pas vide. L'inversion. Cette relation vaut pour tout $p \in N$ , $n$ étant fixé : c'est l'hypothèse du 2) avec $f_{p} = p^{n}$ et $g_{k} = s (n, k)$ . Donc $s (n, p) = k = 0 \sum p (- 1)^{p - k} (k p) k^{n} .$

4) Les contrôles. $p = 2$ : $s (n, 2) = 2^{n} - 2 \times 1^{n} + 0 = 2^{n} - 2$ — toutes les applications sauf les deux constantes. $p = n$ : une surjection entre deux ensembles de même cardinal est une bijection, par le théorème du cours, et il y a $n!$ bijections ; la formule livre donc l'identité $\sum_{k = 0}^{n} (- 1)^{n - k} (k n) k^{n} = n!$ , par exemple $27 - 24 + 3 = 6$ pour $n = 3$ . $p = n - 1$ : dans une surjection de $n$ éléments sur $n - 1$ , les ensembles d'antécédents sont $n - 1$ parties non vides de somme des cardinaux $n$ : exactement l'une a deux éléments, les autres un seul. On choisit la paire d'éléments de même image, $(2 n)$ façons, puis la bijection entre les $n - 1$ blocs et les $n - 1$ éléments d'arrivée, $(n - 1)!$ façons : $s (n, n - 1) = (2 n) (n - 1)!$ . Pour $n = 4$ : $6 \times 6 = 36$ , et la formule donne $81 - 3 \times 16 + 3 \times 1 - 0 = 36$ . $p > n$ : l'image de $E$ a au plus $n < p$ éléments, donc aucune surjection, $s (n, p) = 0$ , et la formule livre $\sum_{k = 0}^{p} (- 1)^{k} (k p) k^{n} = 0$ pour $1 \leq n < p$ : la somme alternée d'ordre $p$ tue les puissances $k^{n}$ d'exposant inférieur à $p$ — l'analogue discret de la dérivée $p$ -ième, qui tue les polynômes de degré inférieur à $p$ .

5) Les dérangements. Le classement. Classons les $n!$ permutations $σ$ de ${1, \dots, n}$ selon leur ensemble de points fixes $F = {i ∣ σ (i) = i}$ . Soit $G$ le complémentaire de $F$ . Pour $i \in G$ , on a $σ (i) \in G$ : si $σ (i) = j$ était dans $F$ , alors $σ (j) = j = σ (i)$ , et l'injectivité donnerait $i = j \in F$ . Donc $σ$ induit une application de $G$ dans $G$ , injective, donc bijective par le théorème du cours, et sans point fixe : un dérangement de $G$ . Réciproquement, un dérangement de $G$ prolongé par l'identité sur $F$ est une permutation dont l'ensemble des points fixes est exactement $F$ . La classe de $F$ compte donc $d_{n - ∣ F ∣}$ éléments, et il y a $(k n)$ parties $F$ à $k$ éléments : $n! = k = 0 \sum n (k n) d_{n - k} = i = 0 \sum n (i n) d_{i},$ en posant $i = n - k$ et par symétrie des coefficients binomiaux. L'inversion, avec $f_{n} = n!$ et $g_{i} = d_{i}$ : $d_{n} = k = 0 \sum n (- 1)^{n - k} (k n) k! = k = 0 \sum n (- 1)^{n - k} \frac{n !}{( n - k )!} = n! j = 0 \sum n \frac{( - 1 ) ^{j}}{j !},$ en posant $j = n - k$ . Les valeurs : $d_{1} = 0$ , $d_{2} = 1$ , $d_{3} = 6 (\frac{1}{2} - \frac{1}{6}) = 2$ , $d_{4} = 12 - 4 + 1 = 9$ , $d_{5} = 60 - 20 + 5 - 1 = 44$ . Contrôle de la relation pour $n = 4$ : $1 + 0 + 6 + 8 + 9 = 24$ ; et pour $n = 3$ , les deux dérangements sont bien les deux permutations circulaires.

6) Un peu plus d'un tiers. Taylor-Lagrange. L'exponentielle est de classe $C^{\infty}$ , toutes ses dérivées valent $exp$ , et sur le segment $[- 1, 0]$ elles sont majorées par $e^{0} = 1$ . L'inégalité de Taylor-Lagrange à l'ordre $n$ , en $a = 0$ et $x = - 1$ , donne $e^{- 1} - j = 0 \sum n \frac{( - 1 ) ^{j}}{j !} \leq \frac{1}{( n + 1 )!}, c’est- a ˋ -dire \frac{d _{n}}{n !} - \frac{1}{e} \leq \frac{1}{( n + 1 )!} .$ Le majorant tend vers $0$ : $\frac{d _{n}}{n !} \to \frac{1}{e} \approx 0, 3679$ . Le point délicat : le majorant de la dérivée doit valoir sur tout le segment $[- 1, 0]$ ; il est atteint en $0$ , pas en $- 1$ .

L'entier le plus proche. En multipliant par $n!$ : $d_{n} - \frac{n !}{e} \leq \frac{1}{n + 1}$ , qui vaut au plus $\frac{1}{3}$ pour $n \geq 2$ . Tout autre entier $m$ vérifie alors $m - \frac{n !}{e} \geq ∣ m - d_{n} ∣ - d_{n} - \frac{n !}{e} \geq 1 - \frac{1}{3} > \frac{1}{2}$ : $d_{n}$ est l'entier le plus proche de $\frac{n !}{e}$ . Pour $n = 1$ , on le vérifie à la main : $d_{1} = 0$ et $\frac{1}{e} \approx 0, 37 < \frac{1}{2}$ . Contrôles : $\frac{5 !}{e} \approx 44, 15$ et $d_{5} = 44$ ; $\frac{7 !}{e} \approx 1854, 11$ et $d_{7} = 1854$ .

L'interprétation. Si l'on rend au hasard $n$ chapeaux à leurs $n$ propriétaires, la proportion des façons de le faire où personne ne retrouve le sien est $\frac{d _{n}}{n !}$ : $0, 5$ pour $n = 2$ , $0, 333$ pour $n = 3$ , $0, 375$ pour $n = 4$ , puis $0, 367$ , $0, 368$ … Contrairement à l'intuition, elle ne tend pas vers $0$ : elle se stabilise à $\frac{1}{e}$ , un peu plus d'un tiers.

Le théorème obtenu — la formule d'inversion de Pascal. Si deux suites vérifient $f_{n} = \sum_{k = 0}^{n} (k n) g_{k}$ pour tout $n$ , alors $g_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (k n) f_{k}$ pour tout $n$ . Elle donne le nombre de surjections $s (n, p) = \sum_{k = 0}^{p} (- 1)^{p - k} (k p) k^{n}$ et la formule des dérangements $d_{n} = n! \sum_{j = 0}^{n} \frac{( - 1 ) ^{j}}{j !}$ , entier le plus proche de $\frac{n !}{e}$ — le problème des rencontres, posé par Montmort en 1708.

Ce que le problème installe. Une relation triangulaire à coefficients binomiaux s'inverse, et le binôme en $(1 - 1)^{m}$ , nul sauf pour $m = 0$ , fait tout le travail. Deux classements — les applications selon leur image, les permutations selon leurs points fixes — fournissent de telles relations, et l'inversion les résout : c'est, sous une forme élémentaire, ce que la formule du crible systématise, sans jamais l'invoquer. Lecture matricielle, pour qui connaît les chapitres 10 et 12 : la matrice triangulaire des coefficients binomiaux est, à la transposition près, celle de $P \mapsto P (X + 1)$ dans la base canonique des polynômes, et son inverse celle de $P \mapsto P (X - 1)$ — l'inversion de Pascal, c'est $(X + 1) - 1 = X$ . Le chapitre 16 reprendra les chapeaux comme la probabilité qu'une permutation aléatoire n'ait aucun point fixe.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.