Exercice 63

Idée. On note $P_{n} = \sum_{\sigma \in \mathfrak{S}_{n}} X^{\omega(\sigma)}$, et l'on relie $\mathfrak{S}_{n}$ à $\mathfrak{S}_{n - 1}$ en retirant l'élément $n$ de son cycle. Si $n$ est fixe, on perd une orbite ; sinon, le nombre d'orbites ne change pas, et il y a $n - 1$ façons de réinsérer $n$. Cela donne $P_{n} = (X + n - 1)P_{n - 1}$.

Soit $n \geqslant 2$ et $\sigma \in \mathfrak{S}_{n}$.

• Si $\sigma(n) = n$, la restriction $\sigma'$ de $\sigma$ à $[\![1\,;n - 1]\!]$ est une permutation, et $\omega(\sigma) = \omega(\sigma') + 1$, l'orbite $\{n\}$ disparaissant. Réciproquement, toute $\sigma' \in \mathfrak{S}_{n - 1}$ se prolonge de façon unique en une telle $\sigma$.

• Si $\sigma(n) \neq n$, on pose $i = \sigma^{-1}(n) \in [\![1\,;n - 1]\!]$, et l'on définit $\sigma'$ sur $[\![1\,;n - 1]\!]$ par $\sigma'(i) = \sigma(n)$ et $\sigma'(k) = \sigma(k)$ pour $k \neq i$. Comme $\sigma$ envoie $[\![1\,;n - 1]\!] \setminus \{i\}$ sur $[\![1\,;n]\!] \setminus \{n, \sigma(n)\}$, la fonction $\sigma'$ est une permutation de $[\![1\,;n - 1]\!]$. On a simplement retiré $n$ de son cycle $(\dots\ i\ n\ \sigma(n)\ \dots)$, qui devient $(\dots\ i\ \sigma(n)\ \dots)$, réduit au point fixe $i$ si c'était une transposition : $\omega(\sigma') = \omega(\sigma)$. Réciproquement, le couple $(\sigma', i) \in \mathfrak{S}_{n - 1} \times [\![1\,;n - 1]\!]$ détermine $\sigma$, par $\sigma(i) = n$, $\sigma(n) = \sigma'(i)$, et $\sigma(k) = \sigma'(k)$ pour les autres $k$.

On a ainsi une bijection entre $\mathfrak{S}_{n}$ et la réunion disjointe de $\mathfrak{S}_{n - 1}$ (premier cas) et de $\mathfrak{S}_{n - 1} \times [\![1\,;n - 1]\!]$ (second cas). En regroupant les termes de $P_{n}$ selon ces deux cas, $$P_{n} = \sum_{\sigma' \in \mathfrak{S}_{n - 1}} X^{\omega(\sigma') + 1} + \sum_{i = 1}^{n - 1}\ \sum_{\sigma' \in \mathfrak{S}_{n - 1}} X^{\omega(\sigma')} = XP_{n - 1} + (n - 1)P_{n - 1}.$$ Comme $P_{1} = X$, une récurrence immédiate donne la factorisation, déjà en facteurs de degré $1$. $$\boxed{\sum_{\sigma \in \mathfrak{S}_{n}} X^{\omega(\sigma)} = X(X + 1)(X + 2)\cdots(X + n - 1)}$$ Pour $n = 3$, on retrouve $X^{3} + 3X^{2} + 2X$ : l'identité, trois transpositions, deux $3$-cycles ✓. Un calcul exhaustif confirme la formule jusqu'à $n = 6$.

À retenir. En $X = 1$, on retrouve $\operatorname{card}\mathfrak{S}_{n} = n!$ (proposition 1). En $X = -1$, la proposition 5 (iii), qui donne $(-1)^{\omega(\sigma)} = (-1)^{n}\varepsilon(\sigma)$, fournit $\sum_{\sigma}\varepsilon(\sigma) = (-1)^{n}P_{n}(-1) = 0$ pour $n \geqslant 2$ : il y a autant de permutations paires que d'impaires.