\(E\) est un ensemble de cardinal \(n\), \(S_n\) le nombre de permutations de \(E\) sans point fixe.

  1. Montrer que \(n!=\sum_{k=0}^n \binom{n}{k} S_k\).

  2. On pose \(f : ]-1,1[ \rightarrow \mathbb{R}, x \mapsto \sum_{n=0}^\infty \dfrac{S_n}{n!}x^n\).

    1. Montrer que \(f\) est bien définie.

    2. Montrer que \(f(x)=\dfrac{e^{-x}}{1-x}\cdotp\)

    3. En déduire que \(S_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}\cdotp\)

    4. Montrer enfin que \(S_n=E(\dfrac{n!}{e}+\dfrac{1}{2})\) pour \(n\geq 1\).


Barre utilisateur

[ID: 3625] [Date de publication: 13 mars 2024 22:21] [Catégorie(s): Equations différentielles ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Michel Quercia ]




Solution(s)

Solution(s)

Dérangements, Mines 2015
Par Michel Quercia le 13 mars 2024 22:21
  1. On classe les permutations selon \(k\) leur nombre de points fixes. Il y a \(\binom{n}{k}\) façons de choisir les points fixes puis pour chaque choix, \(S_{n-k}\) façons de construire une permutation ayant \(k\) points fixes donnés. Il y a donc \(\binom{n}{k}S_{n-k}= \binom{n}{n-k}S_{n-k}\) permutations ayant exactement \(k\) points fixes. On en déduit les relations \(n!= \sum_{k=0}^n \binom{n}{n-k}S_{n-k}=\sum_{k=0}^n\binom{n}{k}S_k\).

    1. Pour tout \(n\), \(S_n\leq n!\), donc le rayon de convergence de la série entière \(\sum_{n=0}^\infty \dfrac{S_n}{n!}x^n\) est \(\geq 1\).

    2. Le produit de Cauchy donne \(f(x)e^x=\sum_{n=0}^\infty (\sum_{k=0}^n \dfrac{S_k}{k!(n-k)!})x^n =\sum_{n=0}^\infty x^n=\dfrac{1}{1-x}\cdotp\)

    3. Pour tout \(|x|<1\), \(f(x)=\dfrac{e^{-x}}{1-x}= \sum_{n=0}^\infty \dfrac{(-1)^n}{n!} \sum_{n=0}^\infty x^n=\sum_{n=0}^\infty (\sum_{k=0}^n \dfrac{(-1)^k}{k!})x^n\). Par unicité du développement en série entière on a, pour tout \(n\), \(S_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}\cdotp\)

    4. On a \(S_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}= \dfrac{n!}{e}+n!\sum_{k=n+1}^\infty (-1)^{k+1}\dfrac{1}{k!}\),

      donc \(\dfrac{n!}{e}+\dfrac{1}{2}= S_n+ \dfrac{1}{2}+\sum_{k=n+1}^\infty (-1)^{k+1}\dfrac{n!}{k!}\). Or \(|\sum_{k=n+1}^\infty (-1)^{k+1}\dfrac{n!}{k!}|\leq \dfrac{1}{n+1}\cdotp\) On en déduit, pour \(n\geq 2\), que \(0\leq \dfrac{1}{2}+\sum_{k=n+1}^\infty (-1)^{k+1}\dfrac{n!}{k!}<1\) et donc que \(S_n=E(\dfrac{n!}{e}+\dfrac{1}{2})\). On vérifie que \(S_{0} =S_{1}=0\) et que la formule est vraie pour tout \(n\).


Documents à télécharger