Writing $P_n=\sum_{\sigma \in \mathfrak{S}_n} X^{c_n(\sigma)}$ as irreducible factors in $\mathbb{Q}[X]$.

Question

Let $\sigma \in \mathfrak{S}_n$, denote $\alpha_n(\sigma)$ the number of cycles in the decomposition of product of disjoint cycles.

Let $$P_n=\sum_{\sigma \in \mathfrak{S}_n} X^{c_n(\sigma)}.$$

The question is to factorize $P_n$ as irreducible factors in $\mathbb{Q}[X]$.

I am stuck on this problem. The problem is a little dry without any intermediate steps. Can someone provide some steps to solve this exercise? Thanks.

Answer 1

This is one of a large class of problems that can be solved very quickly by specializing the cycle index formula for the symmetric group. Let $x_1, x_2, \ldots $ be commuting variables and let $x^\sigma = x_1^{c_1} x_2^{c_2} \ldots $ where $c_i$ is the number of cycles of length $i$ in the permutation $\sigma$. The cycle index formula states that

$$\sum_{n=0}^\infty \frac{1}{n!} \bigl( \sum_{\sigma \in S_n} x^\sigma \bigr) z^n = \exp (x_1z) \exp \bigl( \frac{x_2z^2}{2} \bigr) \ldots \exp\bigl( \frac{x_iz^i}{i} \bigr) \ldots .$$

Specialize by setting $x_i = X$ for all $i$ to get

$$\sum_{n=0}^\infty \frac{1}{n!} P_n(X) z^n = \exp(X(z+z^2/2 + \cdots )) = \exp(-X\log(1-z)) = (1-z)^{-X}. $$

(This is the generating function for Stirling Numbers of the first kind.) By the Binomial Theorem we have $(1-z)^{-X} = \sum_{n=0}^\infty \binom{-X}{n} (-1)^n z^n$. Comparing coefficients of $z^n$ gives

$$P_n(X) = n! \binom{-X}{n}(-1)^n = n! \binom{X+n-1}{n} = (X+n-1)\ldots (X+1)X $$

as already seen in the earlier answer by user8268.

Answer 2

Notice that $$P_{n+1}(X)=(X+n)P_n(X).$$ The term $XP_n(X)$ comes from the elements $\sigma\in\mathfrak S_{n+1}$ such that $\sigma(n+1)=n+1$; such a permutation corresponds to a permutation in $\mathfrak S_n$, but has one more cycle (of length one). The term $nP_n(X)$ comes from those elements of $\mathfrak S_{n+1}$ that do move $n+1$: if $\tau\in\mathfrak S_{n}$ and $k\in\{1,2,\dots,n\}$ then we can define $\sigma\in\mathfrak S_{n+1}$ via "splicing $n+1$ after $k$": $\sigma(k)=n+1$, $\sigma(n+1)=\tau(k)$, $\sigma(m)=\tau(m)$ for $m\neq k,n+1$. The number of cycles of $\sigma$ and $\tau$ is the same.

As $P_1(X)=X$, we get $$P_n(X)=X(X+1)(X+2)\dots(X+n-1).$$