Soit \(\sigma \in S_n\). On appelle orbite de \(\sigma\) toute partie \(X\) de \(\{1,\dots,n\}\) sur laquelle \(\sigma\) induit une permutation circulaire. (Les orbites sont les supports des cycles de \(\sigma\), et les singletons constitués de points fixes)
On note \(N(\sigma)\) le nombre d’orbites de \(\sigma\).
1
Montrer que si \(\tau\) est une transposition, alors \(N(\tau\circ\sigma) = N(\sigma) \pm 1\).
2
Application : Quel est le nombre minimal de transpositions nécéssaires pour obtenir un \(n\)-cycle ?