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$.]


2 Answers 2


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.

  • 1
    $\begingroup$ I would have called (1) the exponential formula :) $\endgroup$ Commented Jan 15, 2016 at 2:08
  • $\begingroup$ @GjergjiZaimi: You're probably right. I just didn't know what to call it! But Polya + cycle index covers the bases. $\endgroup$
    – Lucia
    Commented Jan 15, 2016 at 2:10

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.

  • 1
    $\begingroup$ One can give a more combinatorial version of this proof. To evaluate $\sum_{(\sigma,k)}x^m$, first choose $k$ in $N$ ways, giving a factor $Nx$. Then choose a permutation on the remaining $N-1$ letters, giving a factor $x(x+1)\cdots (x+N-2)$. $\endgroup$ Commented Jan 15, 2016 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.