\input exos
\fiche{Permutations}

%-----------------------------------------------------------------
\ex Générateurs de $𝓢_n$
Soit $n∈ℕ^*$. Montrer que $𝓢_n$ est engendré par les sous-ensembles suivants :

\qq $A = ⦃(i,i+1) \tq 1⩽i<n⦄$.
\qq $B = ⦃(1,i) \tq 2⩽i⩽n⦄$.
\qq $C = ⦃(1,2),(1,2,…,n)⦄$.

%-----------------------------------------------------------------
\ex Générateurs de $𝓢_n$
Montrer que toute permutation de $𝓢_n$ s'écrit de manière unique :
$σ = c₂^{α₂}∘c₃^{α₃}∘…∘c_n^{α_n}$ où $c_i = (1,2,…,i)$ et $0⩽α_i<i$.

%-----------------------------------------------------------------
\ex $𝓐_n$ est engendré par les 3-cycles
\qq Calculer $(a,b,c)∘(b,c,d)$.
    \reponse{$(a,b)∘(c,d)$.}
\qq Montrer que le sous-groupe alterné $𝓐_n$ est engendré par les 3-cycles
    pour $n⩾3$.

%-----------------------------------------------------------------
\ex $𝓐_n$ est engendré par les 3-cycles
Soit $n∈ℕ$, $n⩾4$.

\qq Soit $i,j∈⟦3,n⟧$, $i≠j$.

    Décomposer en cycles à supports disjoints la permutation :
    $σ=(1,i,2)∘(1,2,j)∘(1,i,2)$.
    \reponse{$(1,2)∘(i,j)$.}

\qq On note $𝓗$ le sous-groupe de $𝓐_n$ engendré par les 3-cycles
    $(1,2,k)$, pour $3⩽k⩽n$.

    \sq Montrer : $∀i,j⩾3$ avec $i≠j$, $𝓗$ contient $(1,2)∘(i,j)$ et
        $(i,j)∘(1,2)$.
    \sq Montrer : $∀j⩾3$, $𝓗$ contient $(1,2)∘(1,j)$ et $(1,2)∘(2,j)$.
    \sq Montrer : $∀i≠j$, $∀k≠ℓ$, $(i,j)∘(k,ℓ)∈𝓗$.
    \sq Montrer que $𝓗=𝓐_n$.

%-----------------------------------------------------------------
\ex Signature en fonction du nombre d'orbites
Soit $σ∈𝓢_n$. On note $c$ le nombre de cycles à supports disjoints
constituant $σ$ et $f$ le nombre de points fixes.
Calculer $ε(σ)$ en fonction de $n$, $c$, et $f$.
\reponse{$ε(σ) = (-1)^{n+c+f}$.}

%-----------------------------------------------------------------
\ex Nombre de transpositions pour engendrer un cycle
Soit $σ∈S_n$. On appelle {\it orbite de $σ$\/} toute partie
$X$ de $⟦1,n⟧$ sur laquelle $σ$ induit une permutation circulaire
(les orbites sont les supports des cycles de $σ$, et les singletons
constitués de points fixes).
On note $N(σ)$ le nombre d'orbites de $σ$.

\qq Montrer que si $τ$ est une transposition, alors $N(τ∘σ) = N(σ)±1$.
\qq Application : quel est le nombre minimal de transpositions nécessaires
    pour obtenir un $n$-cycle ?

%-----------------------------------------------------------------
\ex Calcul de signature
Soit $σ = \mat(1 &2 &3 &⋯ &n    &n+1 &n+2 &⋯ &2n \cr
               1 &3 &5 &⋯ &2n-1 &2   &4   &⋯ &2n )$.
Calculer $ε(σ)$.
\reponse{Compter les inversions ou récurrence : $ε(σ) = (-1)^{n(n-1)/2}$.}

%-----------------------------------------------------------------
\ex Conjugaison
Soient $σ,σ'∈𝓢_n$. On dit que $σ$ et  $σ'$ sont
conjuguées s'il existe $ρ∈𝓢_n$ tel que $σ'= ρ∘σ∘ρ^{-1}$.

\qq Montrer que tout conjugué d'un $k$-cycle est encore un $k$-cycle.
\qq Montrer que $σ$ et  $σ'$ sont conjuguées si et seulement si
    les cycles à supports disjoints de $σ$ et $σ'$ ont deux à deux
    mêmes longueurs.

%-----------------------------------------------------------------
\ex Caractérisation de la signature
Soit $E$ un ensemble fini et $f:𝓢_E→ℂ^*$ un morphisme de groupes.

\qq Si $σ$ est une transposition, que peut-on dire de $f(σ)$ ?
\qq Montrer que deux permutations conjuguées ont même image par $f$.
\qq En déduire que $f$ est la fonction constante $1$, ou bien $f$ est la
    signature.

%-----------------------------------------------------------------
\ex Centre de $𝓢_E$
Soit $E$ un ensemble ayant au moins trois éléments.

\qq Pour $a,b∈E$ distincts et $σ∈𝓢_E$, simplifier $σ∘(a,b)∘σ^{-1}$.
\qq Quelles sont les permutations $σ$ qui commutent avec $(a,b)$ ?
\qq En déduire que le centre de $𝓢_E$ est réduit à $⦃\id_E⦄$.

%-----------------------------------------------------------------
\ex Commutant d'un $n$-cycle
Soit $σ = (1,2,…,n)∈𝓢_n$. Trouver toutes les permutations
$ρ∈𝓢_n$ commutant avec $σ$ (on cherchera à reconnaître $ρ∘σ∘ρ^{-1}$).
\reponse{Les puissances de $σ$.}

%-----------------------------------------------------------------
\ex Commutant d'un produit de 5-cycles
Dans $𝓢_{10}$, quelles sont les permutations qui commutent avec
$σ = (1,2,3,4,5)∘(6,7,8,9,10)$ ?
\reponse{$τ = (1,2,3,4,5)^x∘ (6,7,8,9,10)^y$,
         ou $τ = (1,6)∘(2,7)∘(3,8)∘(4,9)∘(5,10)∘
                    (1,2,3,4,5)^x∘(6,7,8,9,10)^y$.
         (50 éléments).}

%-----------------------------------------------------------------
\ex Sous-groupe d'indice 2 dans $𝓢_n$
Soit $H$ un sous-groupe de $𝓢_n$ d'ordre $½n!$.
On note $K = 𝓢_n∖H$.

\qq Pour $σ∈H$, montrer que $σH = H$ et $σK = K$.
\qq Soit $σ∈𝓢_n$. Déterminer les ensembles $σH$,
    $σK$, $Hσ$, $Kσ$ suivant que $σ∈H$ ou $σ∈K$.
\qq En déduire que si deux permutations sont conjuguées, alors elles sont
    toutes deux dans $H$ ou toutes deux dans $K$.
\qq Montrer enfin que $H = 𝓐_n$.

%-----------------------------------------------------------------
\ex Puissances d'un $k$-cycle
Soit $σ$ un $k$-cycle de $𝓢_n$ et $p∈ℕ^*$.

\qq Si $p│k$, montrer que $σ^p$ est le produit de $p$ cycles à supports
    disjoints de longueur $k/p$.
\qq Montrer que pour $p∧k = 1$, $σ^p$ est un $k$-cycle
    (utiliser l'égalité de Bézout).
\qq Dans le cas général, étudier la décomposition en cycles de $σ^p$.

%-----------------------------------------------------------------
\ex Ordre maximal
Trouver l'ordre maximal d'une permutation de $𝓢_{10}$.
\reponse{30.}

%-----------------------------------------------------------------
\ex Dénombrement
Combien y a-t-il de permutations de $𝓢_{26}$ comportant
trois points fixes, deux 3-cycles, un 5-cycle, et deux 6-cycles~?
\reponse{$\bin{26}3
  \times \dfrac{2\bin{23}3\times2\bin{20}3}{2!}
  \times 4!\bin{17}5
  \times \dfrac{5!\bin{12}6\times5!\bin{6}6}{2!}
  = 10\,372\,722\,765\,601\,996\,800\,000$.}

%-----------------------------------------------------------------------------
\ex $k↦|f(k)-k|$ est injective, Mines MP 2012

Trouver les $n$ tels qu'il existe une permutation $f$ de $⦃1,…, n⦄$
telle que $k↦|f(k)-k|$ soit injective.
\reponse{$|f(k)-k|$ doit prendre toutes les valeurs comprises entre
$0$ et $n-1$, donc $⅀_{k=1}ⁿ |f(k)-k|=\dfrac{n(n-1)}{2}$. Pour tout $k$,
$|f(k)-k|≡f(k)-k\pmod 2$. Or $⅀_{k=1}ⁿ (f(k)-k)=0$ puisque $f$ est une
permutation de $⦃1,…, n⦄$. On en déduit que $\dfrac{n(n-1)}{2}$ est pair
ou encore $4$ divise $n(n-1)$. Un seul des deux entiers est pair.
La condition nécessaire est donc $4$ divise $n$ ou $4$ divise $n-1$.
\medskip
Ces conditions sont suffisantes comme le montrent les exemples 
suivants, avec $f(p+1)=p+1$~:

$$\vbox{\halign{&\hfil#\hfil\cr
&&1&&&&2&&&&p&&&&p+2&&&&2p-1&&&&2p\cr
&↙&&↖&&↙&&↖…↖&&↙&&↖&&↙&&↖…↖&&↙&&↖&&↙&&↖\cr
4p&&&&4p-1&&&&3p+1&&&&3p&&&&2p+3&&&&2p+2&&&&2p+1\cr
\multispan{25}\hskip5pt\vrule\hrulefill\raise 2pt\hbox{\hskip-2pt$↑$\hskip5pt}\cr}}$$

$$\vbox{\halign{&\hfil#\hfil\cr
&&1&&&&2&&&&p&&&&p+2&&&&2p&&&&2p+1\cr
&↙&&↖&&↙&&↖…↖&&↙&&↖&&↙&&↖…↖&&↙&&↖&&↙&$↑$\cr
4p+1&&&&4p&&&&3p+2&&&&3p+1&&&&2p+3&&&&2p+2&&\vbox to 0pt{\vss\hbox{\vrule height 24pt\hskip 0.5pt}\vss}\cr
\multispan{23}\hskip12pt\vrule height8pt\hrulefill\hskip12pt\cr}}$$
}

%-----------------------------------------------------------------
\bye
