mathématiques (PCSI) · Chapitre 14 · Exercice de TD

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

Dénombrement · D. Problèmes et doubles comptages · niveau 3 (difficile)

É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é de la question 1

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.

Question 2 : comment l'IA t'aide

Élève

En remplaçant $f_{k}$ , j'obtiens $\sum_{k = 0}^{n} \sum_{j = 0}^{k} (- 1)^{n - k} (k n) (j k) g_{j}$ . Pour isoler $g_{j}$ , j'ai interverti en $\sum_{j = 0}^{n} \sum_{k = 0}^{j}$ , mais rien ne se simplifie.

Ton interversion décrit un autre domaine que celui de départ. Représente l'ensemble des couples $(j, k)$ sur lesquels porte la somme : à $j$ fixé, quelles valeurs $k$ parcourt-il ?

Élève

Le domaine est $0 \leq j \leq k \leq n$ , donc à $j$ fixé, $k$ va de $j$ à $n$ . Mais dans la somme intérieure, $(k n) (j k)$ dépend de $k$ par ses deux facteurs.

Le 1) te fournit une autre écriture de ce produit : en l'utilisant, que peux-tu sortir de la somme sur $k$ , et quel changement d'indice fait apparaître une somme que tu sais calculer ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →