Barre utilisateur

[ID: 2536] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]

Solution(s)

Solution(s)

Autour du nombre de dérangements
Par Patrice Lassère le 9 novembre 2022 12:22

1. -Soit \(n\geq 1\) et désignons par \(P_k\) l’ensemble des permutations de \(\mathscr S_n\) ayant exactement \(k\) points fixes. \(\{P_0,\dots,P_n\}\) est une partition de \(\mathscr S_n\), par conséquent \(\rm{card}(\mathscr S_n)=n!=\sum_{k=0}^n\rm{card}(P_k)\). Nous allons vérifier que \(\rm{card}(P_k)=C_n^kD_{n-k}\). Visiblement \(D_n=\rm{card}(P_0)\) et \(\rm{card}(P_n)=1=D_0=C_n^n D_0\) ; si \(1\leq k\leq n-1\) un \(k\)-dérangement est complétement déterminé par le choix de ses \(k\) points fixes (soit \(C_n^k\) possibilités) et par le choix de la permutation induite sur les \(n-k\) éléments restants (soit \(D_{n-k}\) possibilités)1 soit \(\rm{card}(P_k)=C_n^kD_{n-k}\), puis \[n!=\sum_{k=0}^nC_n^kD_{k}=\sum_{k=0}^nC_{n-k}^kD_{k}.\]

   -On a \[\begin{aligned} \sum_{k=0}^p (-1)^kC_n^kC_{n-k}^{p-k}&=\sum_{k=0}^p(-1)^k\dfrac{n!(n-k)!}{k!(n-k)!(p-k)!(n-p)!}\\ &=\sum_{k=0}^p(-1)^kC_n^pC_p^k =C_n^p(1-1)^p=\begin{cases} \ 0\quad&\text{si}\quad p\geq 1,\\ \ 1\quad&\text{si}\quad p=0. \end{cases} \end{aligned}\]

   -Des deux formules précédentes \[\begin{aligned} n!\left( \sum_{k=0}^n\dfrac{(-1)^k}{k!}\right)&=\sum_{k=0}^n(-1)^kC_n^k(n-k)!\\ &=\sum_{k=0}^n(-1)^kC_n^k\left( \sum_{l=0}^{n-k}C_{n-k}^lD_{l}\right) \quad\rm{vu} \quad\text{($\star$)}\\ &=\sum_{l=0}^n\left( \sum_{k=0}^{n-l}(-1)^kC_n^kC_{n-k}^l\right)D_l=D_n \quad\rm{vu} \quad\text{($\star$)}\\ \end{aligned}\] en échangeant l’ordre de sommation.

   - Une variante repose sur la formule du crible en remarquant que \(D_n=n!-\rm{card}\bigcup_{k=1}^n U_k\), \(U_k\) désignant les permutations de \(\mathscr S_n\) qui fixent \(k\).

2. -La somme est calculée dans la question précédente. Comme \(0\leq D_k\leq k!\) le rayon de convergence \(R\) de la série entière \(D(z)\) est supérieur ou égal à \(1\). En écrivant (\(\star\)) pour tout \(n\in\mathbb N\) sous la forme \[1=\sum_{k=0}^n\dfrac{D_k}{k!}\dfrac{1}{(n-k)!}\] on reconnait y le coefficient de \(z^n\) dans le produit de Cauchy des séries entière \(\sum_k\frac{D_k}{k!}z^k\) et \(\sum_k \frac{z^k}{k!}\) de rayon de convergence au moins \(1\). Ainsi, pour tout \(z\in D(0,1)\) \[D'z e^z=\left( \sum_{k\geq 0}\dfrac{D_k}{k!}z^k\right) \left(\sum_{k\geq 0}\dfrac{z^k}{k!} \right)=\sum_{k\geq 0}z^k=\dfrac{1}{1-z}\] soit \[D(z)=\sum_{k\geq 0}\dfrac{D_k}{k!}z^k =\dfrac{e^{-z}}{1-z},\qquad \forall\,z\in D(0,1).\] Il ne reste plus qu’à déterminer les coefficients du développement en série entière à l’origine de \(z\mapsto \frac{e^{-z}}{1-z}\) pour obtenir \(D_k\). Après un produit de Cauchy des deux séries \(\sum_k \frac{(-1)^k}{k!}z^k\) et \(\sum_k z^k\) on trouve bien \[\dfrac{D_n}{n!} \left( = \sum_{k=0}^n a_k b_{n-k} \right) =\sum_{k=0}^n \dfrac{(-1)^k}{k!}\times 1 = \sum_{k=0}^n \dfrac{(-1)^k}{k!}.\]

   -Nous avons \[\dfrac{1}{e}=\sum_{p=0}^\infty \dfrac{(-1)^l}{l!}=\dfrac{D_k}{k!}+\sum_{l\geq k+1}\dfrac{(-1)^k}{k!}:=\dfrac{D_k}{k!}+R_k,\] soit \[\dfrac{k!}{e}+\dfrac{1}{2}=D_k+\dfrac{1}{2}+k!R_k.\] La série \(\sum_l\frac{(-1)^l}{l!}\) vérifiant le critère des séries alternées, la majoration de son reste \[\vert R_k\vert\leq \dfrac{1}{(k+1)!}\] assure pour pour \(k\geq 1\) : \[\vert k!R_k\vert < \frac{1}{k+1}\leq \frac{1}{2}\] qui nous donne finalement \[D_k=\rm{E}\left( \dfrac{k!}{e}+\dfrac{1}{2}\right).\]

3. Désignons par \(\mathscr D_n\) les dérangements de \(\mathscr S_n\) ; si \(\sigma\in\mathscr D_{n+1}\) : \(\sigma(n+1)\in\mathscr S_n\) et si \(F_k:=\{\sigma\in\mathscr D_{n+1}\ :\ \sigma(n+1)=k\}\) nous avons la partition \(\mathscr D_{n+1}=\bigcup_{k=1}^n F_k\). Montrons que \(\rm{card}(F_k)=D_n+D_{n+1}\). Pour cela on considère la partition \(F_k=G_k\cup H_k\) où \(G_k=\{\sigma\in F_k\ :\ \sigma(k)=n+1\}\) et \(H_k=F_k\setminus G_k\). Un élément de \(G_k\) est parfaitement déterminé par sa restriction à \(\{1,2,\dots,k-1,k+1,\dots,n\}\) et cette restriction devant être un dérangement nous avons \(\rm{card}(G_k)=D_{n-1}\) ; pour le second terme \(\sigma\in H_k\ \Rightarrow\ \sigma^{-1}(n+1)\neq k\) si bien que la correspondance \[H_k\ni\sigma\quad\longmapsto\quad \tilde{\sigma}\in\mathscr D_n\quad \text{où}\quad \tilde{\sigma}(i)=\begin{cases}\sigma(i)\quad&\text{si}\quad i\neq\sigma^{-1}(n+1)\\ k \quad&\text{si}\quad i=\sigma^{-1}(n+1). \end{cases}\] réalise une bijection et par conséquent \(\rm{card}(H_k)=D_n\). Finalement, nous avons bien \(D_{n+1}=n(D_n+D_{n-1})\) pour tout \(n\geq 2\).

   -La formule \(D_n=nD_{n-1}+(-1)^{n+1}\) se déduit de le précédente par une récurrence élémentaire (elle est vraie pour \(n=2\) car \(D_1=0\) et \(D_2=1\)). En divisant cette formule par \(n!\) il vient pour tout \(n\geq 2\) : \[\dfrac{D_k}{k!}=\dfrac{D_{k-1}}{(k-1)!}+\dfrac{(-1)^k}{k!}\] et en sommant cette dernière pour \(2\leq k\leq n\) on retrouve \((\bigstar)\).

---

1. Remarquer que \(D_1\) est toujours égal à zéro et qu’effectivement \(P_{n-1}\) est vide : une permutation ne peut avoir \(n-1\) points fixes !↩︎