I've seen that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$, where $s(n, p)$ are the signed Stirling Numbers of the First Kind, whose absolute values count the number of permutations in $S_n$ which have $p$ cycles in their cycle decomposition. Of course, this means that $n!=\displaystyle\sum_{p=0}^n \lvert s(n, p)\rvert $. So how do the signs and the $n^p$ come in for the second formula? It strongly resembles something that would come from Burnside's Lemma and the Polya Enumeration Theorem, but I'm not exactly sure how those apply, since there are usually not negative numbers in the sum when you use those Theorems.

  • 1
    $\begingroup$ It might be more insightful to consider showing $(x)_n=\sum_{k=0}^n s(n,k)x^k$. $\endgroup$ – Pedro Tamaroff Apr 18 '14 at 20:04
  • $\begingroup$ I actually got my identity by letting $x=n$. Does the formula not have anything to do with Polya/Burnside, then? $\endgroup$ – Nishant Apr 18 '14 at 20:41
  • 2
    $\begingroup$ I don't see any obvious relation (but that doesn't mean there isn't one). My first instinct is it might be more of an inclusion/exclusion type of deal. $\endgroup$ – Alexander Gruber Apr 18 '14 at 22:55
  • $\begingroup$ I believe it would be difficult to get an argument via burnside's lemma for $(x)_n=\sum_{k=0}^ns(n,k)x^k$. Instead, we have a combinatorial argument for the equivalent $(x+n-1)_n=\sum_{k=0}^nc(n,k)x^k$ (where $c(n,k)$ is the unsigned stirling number of the first kind) . The latter equation can be obtained from the former by replacing $x$ by $-x$ and dividing by $(-1)^n$. math.stackexchange.com/questions/162151/… $\endgroup$ – talegari Apr 20 '14 at 11:54
  • $\begingroup$ You ask how signs and $n^p$s come into play in the second formula, but ... I don't see signs or $n^p$s anywhere in the second formula? $\endgroup$ – blue Jun 23 '14 at 6:57

This observation is correct and we may use the Polya Enumeration Theorem to evaluate these two sums. We have by the definition of the cycle index of the symmetric group $Z(S_n)$ which represents the unlabeled multiset operator $\mathfrak{M}$ that

$$\sum_{p=1}^n \left[n\atop p\right] u^p = n! Z(S_n)(u,u,u,\cdots).$$

Recall the ordinary generating function of $Z(S_n)$ which is

$$G(z) = \sum_{n\ge 0} Z(S_n) z^n = \exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} +\cdots\right).$$

Now the signed Stirling numbers of the first kind are given by $$(-1)^{n+p} \left[n\atop p\right].$$

This gives the generating function $$H(z) = \exp\left(- a_1(-z) - a_2 \frac{(-z)^2}{2} - a_3 \frac{(-z)^3}{3} +\cdots\right) \\ = \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} -\cdots\right).$$

This can be shown to be the OGF of the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}$ and we have

$$H(z) = \sum_{n\ge 0} Z(P_n) z^n.$$

It now follows that $$\sum_{p=1}^n (-1)^{n+p} \left[n\atop p\right] u^p = n! Z(P_n)(u,u,u,\cdots).$$

Therefore the quantity being evaluated is $$n! Z(P_n)(n,n,n,\cdots).$$

This is $$n! [z^n] \exp\left(n\times\left(z-\frac{z^2}{2}+\frac{z^3}{3} -\cdots\right)\right) \\ = n! [z^n] \exp(n\log(1+z)) = n! [z^n] (1+z)^n = n!,$$

as claimed.

Similarly we get for the first sum $$n! Z(S_n)(1,1,1,\cdots)$$

which is $$n! [z^n] \exp\left(z+\frac{z^2}{2}+\frac{z^3}{3}+\cdots\right) \\ = n! [z^n] \exp\left(\log\frac{1}{1-z}\right) = n! [z^n] \frac{1}{1-z} = n!,$$

also as claimed.

This last result is a classic formula that can be used to compute many statistics of random permutations. It represents the labeled species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \cdots).$$


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.