Involutions et séries entières

(cet exercice est issu de l’oral Centrale Psi 2015)
Soit {X} un ensemble fini.
On dit que {f\colon X \rightarrow X} est une involution de {X} si {f\circ f = \text{Id}}.
Pour {n\in\mathbb{N}}, on note {I_{n}} le nombre d’involutions de {[\![1,n]\!]} avec {I_{0}=1}.

1. Calculer {I_{1},I_{2},I_{3}}. Montrer que : {\forall\, n\in\,\mathbb{N}^*,\;I_{n+1}=I_{n}+nI_{n-1}}.
2. Montrer que la série entière {S\colon x\mapsto\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_{n}}{n!}x^{n}} possède un rayon {R > 0}.
3. Calculer {(1 + x)S(x)} et en déduire {S(x)} et {I_{n}}.

Pour simplifier la rédaction on pose {X=X_n=\{1,2,\ldots,n\}}.

  1. On a {I_1=1}, {I_2=2} et {I_3=4} (les involutions de {X_3} sont {\text{Id}} et les trois transpositions).

    Soit à former l’une (notons la {\sigma}) des {I_{n+1}} involutions de {X_{n+1}}.

    • Premier cas : {\sigma(n+1)=n+1}.
      Il reste alors à définir la restriction {\sigma'} de {\sigma} à {X_{n}}.
      Mais {\sigma'} doit être une involution de {X_{n}}, ce qui laisse {I_{n}} possibilités.
    • Deuxième cas : {\sigma(n+1)=k\lt n+1} (donc {\sigma} échange {k} et {n+1}).
      Il y a {n} façons de choisir cet entier {k}.
      Cette entier k étant choisi, la restriction de {\sigma} à {Y_{n-1}=X_{n+1}\setminus\{k,n+1\}} doit être une des {I_{n-1}} involutions de {Y_{n-1}}.

    Ce dénombrement conduit donc à la relation: {\forall\, n\ge 1,\;I_{n+1}=I_{n}+nI_{n-1}}.

  2. Les involutions de {X_n} en sont des bijections particulières. On a donc toujours {I_n\le n!}.
    Le rayon de convergence {R} de la série entière {\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_{n}}{n!}x^{n}} vérifie donc {R\ge 1}.
  3. Sur {]-R,R\,[}, et grâce à {S'(x)=\displaystyle\sum_{n=1}^{+\infty}\dfrac{I_{n}}{(n-1)!}x^{n-1}=\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_{n+1}}{n!}x^{n}}, on a :
    \begin{array}{rl}(1+x)S(x)&=(1+x)\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_{n}}{n!}x^{n}=\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_{n}}{n!}x^{n}+\displaystyle\sum_{n=1}^{+\infty}\dfrac{I_{n-1}}{(n-1)!}x^{n}\\\\&=1+\displaystyle\sum_{n=1}^{+\infty}\dfrac{I_n+nI_{n-1}}{n!}x^{n}=1+\displaystyle\sum_{n=1}^{+\infty}\dfrac{I_{n+1}}{n!}x^{n}=S'(x)\end{array}

    La fonction {x\mapsto S(x)} est donc la solution de {y'=(1+x)y} telle que {S(0)=1}.

    Ainsi : {S(x)=\exp\Bigl(x+\dfrac{x^2}{2}\Bigr)=\displaystyle\sum_{j=0}^{+\infty}\dfrac{x^j}{j!}\;\displaystyle\sum_{k=0}^{+\infty}\dfrac{x^{2k}}{2^k k!}=\displaystyle\sum_{n=0}^{+\infty}\dfrac{I_n}{n!}x^n}.

    On en déduit : {I_n=\displaystyle\sum_{j+2k=n}\dfrac{n!}{2^k j!k!}=\displaystyle\sum_{k=0}^{n/2}\dfrac{n!}{2^k (n-2k)!\,k!}}.