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!$
 A: 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.
A: 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}.$$
A: 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).
