# Why is $\sum_{p \in S_n} 2^{c(p)}$ equal to $(n+1)!$?

It is obvious that $$\sum_{p \in S_n} 1=n!$$ because it is just counting how many permutations there are of $$n$$ symbols.

But I have also observed that $$\sum_{p \in S_n} 2^{c(p)}=(n+1)!$$, where $$c(p)$$ is the number of cycles of $$p$$.

What is the combinatorial interpretation of this identity?

An example. In $$S_3$$ we have one permutation with 3 cycles, three permutations with 2 cycles and two with 1 cycle. Then $$1\times 2^3+3\times 2^2+2\times 2^1=24=4!$$

• What do you mean by the number of cycles of $p$? – Rob Arthan Jan 31 '20 at 21:02
• @RobArthan When a permutation acts on the set $\{1,...,n\}$ it will have invariant subsets where its action is transitive. These are the cycles. – thedude Jan 31 '20 at 21:03
• Take any permutation in $S_n$. Try to create a permutation in $S_{n+1}$. You need to add $n+1$. You want a scheme of adding $n+1$ so that it is a distinct permutation. For each cycle, you either include $n+1$ or you don't (possibly merging cycles). My guess would be that there is a scheme where this produces a distinct element of $S_{n+1}$. – InterstellarProbe Jan 31 '20 at 21:06
• This answer generalises your result. – Milten Jan 31 '20 at 21:10
• This also has a probabilistic interpretation - if $\sigma$ is a random permutation in $S_n$, then $E(2^{c(\sigma)}) = n+1$ – Michael Lugo Jan 31 '20 at 21:52

The sum in question counts the number of pairs $$(f, p)$$ where $$f$$ is a function from $$\{1, 2, \dots, n\}$$ to $$\{1, 2\}$$, and $$p \in S_n$$ such that $$f \circ p = f$$. I don't know if there is an easy way to see that this is equal to $$(n + 1)!$$, but here is an approach:

First let's verify that the sum does actually count what I say that it does. Suppose that we have already chosen the permutation $$p$$. A function $$f$$ satisfies the conditions above if and only if for each cycle of $$p$$, we have that $$f$$ maps every element of that cycle to the same element of $$\{1, 2\}$$. We can thus determine $$f$$ by choosing the image of each cycle, and there are two options for the image of each cycle, giving us $$2^{c(p)}$$ functions in total.

Let's now instead determine the sum by counting the pairs $$(f, p)$$ such that there are $$k$$ elements of $$\{1, 2, \dots, n\}$$ that are mapped to $$1$$ under $$f$$. There are $$\binom{n}{k}$$ ways to choose which $$k$$ elements these are. There are then $$k!$$ ways to choose how $$p$$ permutes these $$k$$ elements, and $$(n - k)!$$ ways to choose how $$p$$ permutes the remaining elements. This gives us $$\binom{n}{k} k! (n - k)! = n!$$ ways to choose the pair $$(f, p)$$. Noting that $$k$$ can take any value from $$0$$ to $$n$$, this gives us $$(n + 1) n! = (n + 1)!$$ pairs in total.

• I hadn't heard of Polya's Enumeration Theorem before, but now that I have, I think that this may be essentially the same solution as @Milten's. – Dylan Jan 31 '20 at 22:03
• For your last paragraph, suppose that $f^{-1}(1)=\{x_1,x_2,\ldots,x_k\}$ and $f^{-1}(2)=\{y_1,y_2,\ldots,y_l\}$ with $x_1<x_2<\ldots<x_k$ and $y_1<y_2<\ldots<y_l$. There is a $1$-$1$ correspondence between the pairs $(f,p)$ and the permutations of $(0,1,2,\ldots,n)$ by taking $$(f,p)\mapsto \big(p(x_1),p(x_2),\ldots,p(x_k),0,p(y_1),p(y_2),\ldots,p(y_l)\big).$$ This is an alternative way to show that there are $(n+1)!$ pairs $(f,p)$. – Batominovski Jan 31 '20 at 22:36
• If I am not mistaken, your proof also shows that $$\sum_{p\in S_n} r^{c(p)}=\frac{(n+r-1)!}{(r-1)!}$$ for all non-negative integer $r$. Hence, it follows that $$\sum_{p\in S_n} x^{c(p)} =x(x+1)(x+2)\cdots (x+n-1)$$ as a polynomial identity. – Batominovski Jan 31 '20 at 22:47
• @Dylan Indeed it seems we had pretty much the same idea. I think you basically proved Pólya's theorem in your answer. I would say yours is probably cleaner as a combinatorial proof though :) – Milten Feb 1 '20 at 9:16

It can be seen as an application of Pólya's enumeration theorem.

Let us take $$n$$ beads and colour each of them black or white. We consider two colourings equivalent, if there are the same number of black and white beads. That is, if some permutation $$\sigma\in S_n$$ takes one of the colourings to the other. It is clear that there are then $$n+1$$ distinct colourings (since there can be $$0,1,\ldots, n$$ black beads). Pólya's theorem then says that: $$n+1 = \frac{1}{|S_n|}\sum_{\sigma\in S_n}2^{c(\sigma)} = \frac{1}{n!}\sum_{\sigma\in S_n}2^{c(\sigma)}$$ The $$2$$ in the formula is the number of colours.

I guess this is somewhere between a combinatorial interpretation and just a proof... Depends on your attitude towards Pólya's theorem I guess.

EDIT: Let me just include the immediate generalisation. If we have $$m$$ colours, then there are $$\binom{n+m-1}{n}$$ different colourings (by stars and bars). So: $$\sum_{\sigma\in S_n}m^{c(\sigma)} = n!\binom{n+m-1}{n} = \frac{(n+m-1)!}{(m-1)!} = m(m+1)\cdots(n+m-1)$$ This only works for $$m\in\mathbb N$$ of course. But as WE Tutorial School points out in a comment, this shows that the left and right hand sides are equal as polynomials in $$m$$, so the identity is proved for any value of $$m$$ (even complex and whatnot).

The combinatorial class of permutations with the number of cycles marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}( \mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=2}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

This gives the EGF

$$G(z, u) = \exp\left(uz+u\frac{z^2}{2} + u\frac{z^3}{3}+\cdots\right) \\ = \exp\left(u\log\frac{1}{1-z}\right).$$

A permutation on $$n$$ elements and having $$k$$ cycles is represented by $$u^k \frac{z^n}{n!}.$$ For the sum we set $$u=2$$ and obtain

$$H(z) = \exp\left(2\log\frac{1}{1-z}\right) = \frac{1}{(1-z)^2}.$$

We then get for the answer

$$n! [z^n] H(z) = n! [z^n] \frac{1}{(1-z)^2} = n! {n+1\choose 1} = (n+1)!.$$

This is the claim.

Addendum. With two being replaced by $$m$$ we obtain

$$n! [z^n] H(z) = n! [z^n] \frac{1}{(1-z)^m} = n! \times {n+m-1\choose m-1} = n! \times {n+m-1\choose n}.$$

• I apologise for using comments in this unintended way, but: I just wanted to tell you that this answer inspired me to begin reading Analytic Combinatorics by Flajolet & Sedgewick. I am now 200 pages deep and I love it. I had never heard of these methods before, so thank you :) – Milten Sep 3 '20 at 9:05