Characters of permutation groups

Question

Let $N$ be a fixed positive integer, and denote by $C(m)$ the number of permutations on an $N$-element set that have exactly $m$ cycles (counting $1$-cycles). Then it is in the literature that the polynomial generating function $$ \sum_{m=0}^N C(m)x^m = x(x+1) \dots (x+N-1), $$ the rising factorial.

I would like a reference (or a proof) for the following. Let $C(m,j)$ be the number of permutations (of the $N$-element set) which have exactly $m$ cycles, $j$ of which are $1$-cycles, that is, the number of permutations with $m$ cycles and $j$ fixed points. Then the following should be true: $$ \sum_{m=0}^N \sum_{j=0}^m C(m,j)(j-1)x^m = (N-1)\cdot (x-1)x(x+1) \dots (x+N-2), $$ that is, $N-1$ times the rising factorial of $x-1$.

I verified this for $N= 3,4,5,6$ by hand, and figured that if it works up to $6$, it probably is true for all $N$ (since $S_4$ and $S_6$ are the screwiest symmetric groups). But this surely must be known.

Motivation. Let $V$ be a $k$-dimensional vector space (over the complexes or the rationals, it doesn't matter), form the $N$-fold tensor product of $V$ with itself, $W = \otimes^N V$, and consider the obvious permutation action of $S_N$ on $W$. This is a very heavily studied object, going back (at least) to Schur. Let $\chi$ denote the character of this representation of $S_N$ (this depends on $k$, of course).

It is not difficult to see that for $g \in S_N$, we have $\chi(g) = k^{c(g)}$ where $c(g)$ is the number of cycles in $g$. Let $\chi_0$ be the trivial character, and let $\chi_s$ be the character of the standard $N-1$-dimensional irreducible representation of $S_N$ ($\chi_s (g) $ is the number of fixed points less $1$, of $g$). Then the first formula entails that $(\chi,\chi_0) = {{k+N-1}\choose N}$, and the second (if true) says that $(\chi,\chi_s) = (N-1) {{k+N-2}\choose N}$.

If $\chi_{-}$ and $\chi_{s-}$ are respectively the irreducible characters obtained by multiplying $\chi_0$ and $\chi_s$ by the sign character (the other linear character, denoted $\chi_{-}$), then we also deduce from the equations above (evaluating at $-x$ and normalizing) that $(\chi,\chi_{-}) = {k \choose N}$ and $(\chi,\chi_{s-}) = (N-1){{k+1} \choose N}$.

I was interested in the class function (on $S_N$), $\psi_k: g \mapsto k^{c(g)}$ for $k$ positive real numbers (rather than just integers; set $x=k$); the question was for which values of $k$ is this a nonnegative real combination of irreducible characters. If the second displayed equation is true, and $k < N-1$, then nonnegativity of $\psi_k$ implies that $k$ is an integer.

Presumably, it is true that for all real $k > N-1$, $\psi_k$ has only nonnegative (and probably positive) coefficients (with respect to the irreducible characters). I verified this for $N = 3,4$ by hand, and then was exhausted. [A very general and easy result, using the Perron theorem for example, is that this is true for all sufficiently large $k$.]

Answer 1

This follows from using generating functions a la Polya. By the cycle index formula, one sees that (using the notation of $C_n(k,j)$ for permutations in $S_n$ with $k$ cycles including $j$ fixed points) $$ \sum_{n=0}^{\infty} \frac{t^n}{n!} \sum_{k,j} C_n(k,j) y^j x^k = \exp\Big( tx y +\sum_{j=2}^{\infty} \frac{x t^j}{j}\Big). \tag{1} $$ Since $\sum_{j=1}^{\infty} t^j/j = -\log (1-t)$, we may write the above as $$ (1-t)^{-x}\exp(tx(y-1)). \tag{2} $$

If we take here $y=1$ and compare coefficients of $t^n$ we obtain the formula you noted: $$ \frac{1}{n!} \sum_{k, j} C_n(k,j) x^k = (-1)^n\binom{-x}{n}= \frac{x(x+1)(x+2)\cdots (x+n-1)}{n!}. \tag{3} $$ Next, differentiating (1) and (2) with respect to $y$ and then setting $y=1$ gives $$ \sum_{n=0}^{\infty} \frac{t^n}{n!} \sum_{k,j} j C_n(k,j) x^k = tx (1-t)^{-x}. $$ Comparing coefficients of $t^n$ here gives $$ \frac{1}{n!} \sum_{k, j} j C_n(k,j) x^k = (-1)^{n-1}x\binom{-x}{n-1}=x\frac{x(x+1)\cdots (x+n-2)}{(n-1)!}. \tag{4} $$ Combining (3) and (4) gives your formula.

Answer 2

For the reasons apparent below I shall use the notation $C_N(m,j)$, not $C(m,j)$. It is sufficient to prove $$ \sum_{m=0}^N\sum_{j=0}^m jC_N(m,j)x^m=Nx\cdot x(x+1)\cdots (x+N-2), $$ as this formula together with your first formula implies what you want to prove. The LHS of this is the same as $$ \sum_{(\sigma,k)\colon \sigma\in S_N \text{ has } m \text{ cycles}, \,\sigma(k)=k }x^m, $$ which, after changing the order of summation and denoting $m'=m-1$, is the same as $$ \sum_{k=1}^N x\sum_{m'=0}^{N-1}\sum_{j=0}^{m'}C_{N-1}(m',j)x^{m'}=\sum_{k=1}^Nx\cdot x(x+1)\cdots(x+N-2), $$ which is equal to $Nx\cdot x(x+1)\cdots(x+N-2)$, as required.