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.

  • $\begingroup$ 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. $\endgroup$ – Linus Hamilton Jul 24 '16 at 19:46
  • $\begingroup$ I edited the question, I'm pretty sure that from the context, beta is positive strictly less than 1. $\endgroup$ – I.K Jul 24 '16 at 19:51
  • $\begingroup$ 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)}$. $\endgroup$ – Brian Hopkins Jul 24 '16 at 19:51
  • $\begingroup$ Yes. I rewrote it. I used $ \beta = \alpha^{-1} $ Then it's the same equality, isn't it? $\endgroup$ – I.K Jul 24 '16 at 19:53
  • 1
    $\begingroup$ 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). $\endgroup$ – Brian Hopkins Jul 24 '16 at 20:11

It seems that the correct formula is actually

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

And this has a quite nice proof over on math.SE here.

  • $\begingroup$ Thank you. I'm going through it by hand for n=1,2,3.. and it does seem that it should be + and not - $\endgroup$ – I.K Jul 24 '16 at 20:15
  • $\begingroup$ Thank you very much! This also clears up some later applications in the paper. This is just the result in Stanley V1 p. 27 (Prop. 1.3.7) $\endgroup$ – I.K Jul 24 '16 at 20:37

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).

  • $\begingroup$ 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! $\endgroup$ – I.K Jul 24 '16 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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