Involutions d'un ensemble

Une involution de $\{1,\dots,n\}$ est une permutation $\sigma$ telle que $\sigma^2 = \mathrm{id}$. On note $a_n$ leur nombre, avec $a_0 = 1$.

1. Montrer qu'une involution n'est composée que de points fixes et de transpositions.

2. En déduire $a_n = a_{n-1} + (n-1)\,a_{n-2}$ pour $n \geq 2$, et calculer $a_1$ à $a_5$.

3. Donner une formule close pour $a_n$, en dénombrant selon le nombre de transpositions.

4. Vérifier les deux méthodes sur $n = 4$.