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!$

Solution 1:

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

Solution 2:

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.

Solution 3:

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