# Combinatorial identity involving number of cycles (of any length) in a permutation

I am going through Phil Hanlon's paper and on page 127, right after the first paragraph, "It is well known that.." which boils down to the following identity:

$$\prod_{i=0}^{n-1}(\beta-i) = \sum_{\sigma \in S_n}\beta^{c(\sigma)}$$

where $c(\sigma)$ is the number of cycles (of any length) in a permutation.

I suspect this is not a difficult thing to prove, but I have not been able to find any literature that deals directly with this identity. Any help?

From the context, I think $\beta$ is positive and strictly less than 1.

• Are you missing a sign somewhere? If $\beta=1$ then the LHS is zero but the RHS is $n!$. EDIT: for a fixed $n$, both sides are polynomials in $\beta$, so if they are equal for $0<\beta<1$ then they are equal for $\beta=1$ too. – Linus Hamilton Jul 24 '16 at 19:46
• I edited the question, I'm pretty sure that from the context, beta is positive strictly less than 1. – I.K Jul 24 '16 at 19:51
• Looking at the paper, I think it's $\sum_{i=0}^{n-1} (1-i\alpha) = \prod_{\sigma \in S_n} \alpha^{n-c(\sigma)}$. – Brian Hopkins Jul 24 '16 at 19:51
• Yes. I rewrote it. I used $\beta = \alpha^{-1}$ Then it's the same equality, isn't it? – I.K Jul 24 '16 at 19:53
• I wonder if Hanlon is missing a $\text{sgn}(\sigma)$ term in the summation. Working out the $S_3$ example he has running through the article gives $2\alpha^2 - 3 \alpha + 1$ for the product but $2\alpha^2 + 3\alpha + 1$ for the sum (which is $\beta^3-3\beta^2+2\beta$ vs. $\beta^3 + 3\beta^2 + 2\beta$ in your formulation). – Brian Hopkins Jul 24 '16 at 20:11

$$\prod_{i=0}^{n-1}(\beta+i) = \sum_{\sigma \in S_n}\beta^{c(\sigma)}$$
Since I can't see immediately how Hanlon uses the equation, I guess the question is which "typo" was made. Linus's equation is correct, but I also think $$\prod_{i=0}^{n-1} (\beta - i) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \beta^{c(\sigma)}$$ is true (and probably follows easily from Stanley's third proof referenced on the math.SE problem).
• I see that now. From the context, it's clear he means the usual: $$\prod_{i=0}^{n-1}(\beta+i) = \sum_{\sigma \in S_n}\beta^{c(\sigma)}$$ as Linus noted. Thanks everyone for the quick help! – I.K Jul 24 '16 at 20:44