Une écriture des permutations
Bonjour,
Je cherche à démontrer que toute permutation dans $\mathfrak{S}_n$ s'écrit de façon unique de la façon suivante $$\sigma=(1,x_1)(2,x_2)\cdots(n,x_n)$$ où pour chaque $k\in\{1,\ldots,n\}, x_k\in\{1,\ldots,k\}$, ayant évidemment convenu que la transposition $(k,x_k)$ est l'identité si $x_k=k$. Je tente ma chance :
On procède par récurrence sur la longueur de la permutation. Pour $n=1,2$, c'est immédiat (notamment, on a bien unicité)
Si c'est vrai pour $n-1$ (et peut être pour les longueurs inférieures, j'ignore pour l'instant s'il faut procéder à une récurrence forte ou non), prenons $\sigma\in\mathfrak{S}_n$.
Si $\sigma(n)=n$ alors $\sigma$ induit par restriction une permutation de $\{1,\ldots,n-1\}$ et on vérifie par récurrence que le tour est joué avec $x_n=n$.
Sinon $\sigma(n)<n$, et j'ignore un peu comment poursuivre...
Pourriez-vous m'éclairer ?
Je cherche à démontrer que toute permutation dans $\mathfrak{S}_n$ s'écrit de façon unique de la façon suivante $$\sigma=(1,x_1)(2,x_2)\cdots(n,x_n)$$ où pour chaque $k\in\{1,\ldots,n\}, x_k\in\{1,\ldots,k\}$, ayant évidemment convenu que la transposition $(k,x_k)$ est l'identité si $x_k=k$. Je tente ma chance :
On procède par récurrence sur la longueur de la permutation. Pour $n=1,2$, c'est immédiat (notamment, on a bien unicité)
Si c'est vrai pour $n-1$ (et peut être pour les longueurs inférieures, j'ignore pour l'instant s'il faut procéder à une récurrence forte ou non), prenons $\sigma\in\mathfrak{S}_n$.
Si $\sigma(n)=n$ alors $\sigma$ induit par restriction une permutation de $\{1,\ldots,n-1\}$ et on vérifie par récurrence que le tour est joué avec $x_n=n$.
Sinon $\sigma(n)<n$, et j'ignore un peu comment poursuivre...
Pourriez-vous m'éclairer ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Comment faut-il choisir \(x_n\) pour que \(n\) soit invariant par \(\sigma\circ(n,x_n)\) ?
Réponse : prendre $x_n=\sigma^{-1}(n)$
Reprenons... si $\sigma(n)<n$ (ou pas d'ailleurs, pas besoin de cette dichotomie finalement) alors $n$ fixe $\tau=\sigma\circ(n,\sigma^{-1}(n))$ et alors $\tau$ induit par restriction une permutation $\tilde{\tau}$ de $\{1,\ldots,n-1\}$ à laquelle on applique l'hypothèse de récurrence :$$\tilde{\tau}=(1,x_1)\ldots(n-1,x_{n-1})$$ avec les $x_k$ comme il faut. Ainsi, on a :
$$\sigma=(1,x_1)\ldots(n-1,x_{n-1})(n,x_n)$$ où $x_n=\sigma^{-1}(n)$, et c'est bon.
L'unicité de l'écriture s'établit-elle aussi par récurrence ?
Merci !