Involutions de $\mathfrak{S}_n$

mathematoc · December 2018

Bonjour

Je cherche à calculer le cardinal $I_n$ de l’ensemble $\{\sigma \in \mathfrak{S}_n | \sigma^2=id\}$ pour tout entier naturel $n$ non nul.J’ai sous la main une solution d’Arnaudiès.
Mais j’ai deux problèmes :
1) On détermine $I_n$ directement dans la première question par dénombrement. Mais je ne comprends pas dans le raisonnement d’où vient le $2^p$? (dans lequel des « trois » objets intervient-il?).
2) Pour la seconde question, on demande de montrer que $I_{n+1}=I_n+n I_{n-1}$ sans la question précédente.
J’ai l’impression qu’il faut vérifier que $\sigma^2(n+1)=n+1$, cela est facile mais cela est-il trivial??
Merci beaucoup. 82588

aléa · December 2018

On fabrique une surjection de $\mathfrak{S}_{2p}$ dans l'ensemble des involutions de $\{1,\dots,2p\}$ sans point fixe; à cette surjection on applique le lemme des bergers, ce qui explique la division par $ p!2^p$ (ordre d'écriture des cycles, ordre des éléments dans chaque cycle).

mathematoc · December 2018

Ok merci alea pour le lemme des bergers! Sinon pour la deuxième question? Dois-je vérifier que $\sigma^2(n+1)=n+1$ où est-ce une trivialité(je ne vois pas dans ce cas...)?

mathematoc · December 2018

J'ai essayé de formaliser l'explication d'alea. Soit $n$ un entier naturel non nul et $p$ un entier compris entre $0$ et $n/2$.
Comptons le nombre d'involutions d'une $2p-partie$ de $\{1,2,..,n\}$. Une telle partie est évidemment en bijection avec $\{1,2,...,2p\}$.
Soit $s$ l'application :
$\begin{array}{ccccc}
s & : & \mathfrak{S}_{2p} & \to & I_{\{1,..,2p\}} \\
& & \sigma & \mapsto & s(\sigma) \\
\end{array}$
de $\mathfrak{S}_{2p}$ dans les involutions de $\{1,..,2p\}$ qui, à tout $\sigma \in \mathfrak{S}_{2p}$ associe le produit des $p$ transpositions :
$(\sigma(1),\sigma(2))(\sigma(3),\sigma(4))...(\sigma(2p-1),\sigma(2p))$.
Puisque toute involution s'écrit comme produit de transpositions disjointes, $s$ est surjective.
Alors, $\mathfrak{S}_{2p} / \mathcal{R}$ est en bijection avec $I_{\{1,..,2p\}}$ où $\mathcal{R}$ est la relation d'équivalence :
$\sigma \mathcal{R} \sigma' \Longleftrightarrow s(\sigma)=s(\sigma')$.
Or :
$\cdot$On ne change pas une involution de $\{1,..,2p\}$ si on permute les transpositions puisqu'elles sont disjointes. Il y a $(p)!$ façons de le faire.
$\cdot$On ne change pas une involution de $\{1,..,2p\}$ si on permute le support d'un facteur quelconque. Il y a $2^p$ façons de permuter le produit.
Il y a donc $2^p \cdot p!$ éléments par classe d'équivalence et $I_{\{1,..,2p\}}$ compte donc $\frac{(2p)!}{2^p \cdot p!}$ éléments.
De plus, il y a ${n}\choose{2p}$ $2p-$parties dans $\{1,2,..,n\}$, donc il y a ${n}\choose{2p}$$ \cdot \frac{(2p)!}{2^p \cdot p!}$ involutions constituées de $p$ transpositions disjointes, ceci pour chaque $p$ entier compris entre $0$ et $n/2$.
Finalement, il y a $\sum_{p=0}^{n/2}$${n}\choose{2p}$$ \cdot \frac{(2p)!}{2^p \cdot p!}$ involutions dans $\mathfrak{S}_{n}$.
Est-ce correct?Merci beaucoup.