Exercice 17

Idée. Une partie stable par $\sigma$ doit contenir, avec chacun de ses éléments, toute son orbite : les parties stables sont les réunions d'orbites, et l'on choisit librement quelles orbites on réunit.

Rappelons (chapitre 17, démonstration du théorème 1) que les orbites de $\sigma$ sont les classes de la relation « il existe $k \in \mathbb{Z}$ tel que $j = \sigma^{k}(i)$ », et qu'elles forment une partition de $\llbracket 1\,,n \rrbracket$ ; on note $\mathcal{O}_{1}$, …, $\mathcal{O}_{\omega}$ ces orbites, avec $\omega = \omega(\sigma)$.

$\triangleright$ Une réunion d'orbites est stable. Pour une orbite $\mathcal{O}_{j}$ et $x \in \mathcal{O}_{j}$, l'élément $\sigma(x)$ est dans la même orbite : $\sigma(\mathcal{O}_{j}) \subset \mathcal{O}_{j}$. Comme $\sigma$ est injective, $\sigma(\mathcal{O}_{j})$ a autant d'éléments que $\mathcal{O}_{j}$, et l'inclusion est une égalité (proposition 1 (ii)). Pour une réunion $A = \bigcup_{j \in J} \mathcal{O}_{j}$, on obtient $\sigma(A) = \bigcup_{j \in J} \sigma(\mathcal{O}_{j}) = A$ (chapitre 2, proposition 2 (i)).

$\triangleright$ Une partie stable est une réunion d'orbites. Soit $A$ telle que $\sigma(A) = A$. Alors $\sigma^{-1}(A) = A$, et, par récurrence, $\sigma^{k}(A) = A$ pour tout $k \in \mathbb{Z}$. Pour $x \in A$, l'orbite de $x$, formée des $\sigma^{k}(x)$, est donc contenue dans $A$. Ainsi $A$ est la réunion des orbites de ses éléments.

$\triangleright$ Dénombrement. L'application $J \mapsto \bigcup_{j \in J} \mathcal{O}_{j}$, de $\mathcal{P}\big(\llbracket 1\,,\omega \rrbracket\big)$ dans l'ensemble des parties stables, est surjective par l'étape précédente, et injective parce que les orbites sont non vides et deux à deux disjointes : on retrouve $J$ comme l'ensemble des $j$ tels que $\mathcal{O}_{j} \subset A$. Par la proposition 3, $$\boxed{\Big|\big\{A \subset \llbracket 1\,,n \rrbracket \mid \sigma(A) = A\big\}\Big| = 2^{\omega(\sigma)}}$$ Pour l'identité, $\omega = n$ et toutes les $2^{n}$ parties sont stables ; pour un $n$-cycle, $\omega = 1$ et seules $\varnothing$ et $\llbracket 1\,,n \rrbracket$ le sont. Pour la permutation $\sigma = (1\,3\,5)(2\,6)$ de $\mathfrak{S}_{6}$, exemple du chapitre 17, les orbites sont $\{1, 3, 5\}$, $\{2, 6\}$ et $\{4\}$, et il y a $2^{3} = 8$ parties stables. Une énumération confirme le résultat pour toutes les permutations de $\mathfrak{S}_{n}$, $n \leqslant 5$.

Piège. L'erreur la plus répandue est de confondre « $\sigma(A) = A$ » et « $\sigma(x) = x$ pour tout $x \in A$ » : la seconde condition fait de $A$ une partie de l'ensemble des points fixes, et il y en aurait $2^{n - |\mathrm{Supp}(\sigma)|}$. Une partie stable peut être déplacée point par point tout en restant globalement invariante.