# Is there a combinatorial explanation for the identity: $\sum_{k=1}^n c(n,k)2^k = (n+1)!$

Let $c(n,k)$ be the unsigned Stirling numbers of the first kind, i.e., the number of $n$-permutations with exactly $k$ cycles. Apparently, $$\sum_{k=1}^n c(n,k)2^k = (n+1)!$$

I want to prove the equality.

I am most interested in a combinatorial explanation.

The exponential generating function for the RHS is $\frac1{(1-x)^2}$. Is there a way to derive the e.g.f. for the LHS symbolically?

By way of enrichment here is a proof using generating functions. Suppose we seek to evaluate $$\sum_{k=1}^n \left[n\atop k\right] 2^k.$$

The species of decompositions of permutations into cycles marked by the number of cycles is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z})).$$ This gives the generating function $$G(z, u) = \exp\left(u\left(\log\frac{1}{1-z}\right)\right)$$ which immediately yields $$\left[n\atop k\right] = n! [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

This gives for the sum $$n! [z^n] \sum_{k=1}^n 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

The term at $k=0$ does not contribute so we may include it to get $$n! [z^n] \sum_{k=0}^n 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Furthermore $\log\frac{1}{1-z}$ starts at $z$ and $\left(\log\frac{1}{1-z}\right)^k$ starts at $z^k$ so we may extend the sum to infinity, getting $$n! [z^n] \sum_{k=0}^\infty 2^k \times \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

This is $$n! [z^n] \exp\left(2\log\frac{1}{1-z}\right) = n! [z^n] \frac{1}{(1-z)^2}.$$ This finally yields $$n! {n+1\choose n} = (n+1)!$$

Addendum. The proof by @QuiaochuYuan is remarkably elegant. Suppose you are distributing $Q$ colors into $n$ slots (initially creating $Q^n$ possible configurations) and want to count orbits under the action of the symmetric group $S_n$ (all $n!$ permutations) on the slots. By Burnside you need to average the number of colorings fixed by a given permutation $\sigma$ over all $n!$ permutations. But a permutation with $k$ cycles fixes $Q^k$ colorings (color must be constant on a cycle). Therefore the number of colorings is given by

$$\frac{1}{n!} \sum_{k=1}^n \left[n\atop k\right] Q^k.$$

On the other hand lining up the colors according to some order we have by stars-and-bars that there are $${n+Q-1\choose Q-1}$$ colorings, thus completing the proof.

The more general result is that

$$\sum_{k=1}^n c(n, k) x^k = x(x + 1) \dots (x + n - 1).$$

Your result follows straightforwardly by substituting $x = 2$. This identity has the following cute proof: dividing both sides by $n!$ we get

$${x + n - 1 \choose n} = \frac{1}{n!} \sum_{k=1}^n c(n, k) x^k.$$

The LHS is the number of multisets of size $n$ on a set of size $x$. This is the number of orbits of the action of the symmetric group $S_n$ on the set of functions from a set $[n]$ of size $n$ to a set $[x]$ of size $x$, and accordingly the number of orbits can be counted using Burnside's lemma. If $\sigma$ is a permutation with $k$ cycles, then the number of fixed points of $\sigma$ acting on functions $[n] \to [x]$ is $x^k$, and the conclusion follows.

You can also prove this identity by induction on $n$.

For more general results along these lines see this blog post and this one.

• Very nice work. (+1). – Marko Riedel Mar 12 '15 at 22:25
• For kicks, here's a sketch of the proof by induction. Think of permutations as total orders, and so think of building permutations in $S_n$ from permutations in $S_{n-1}$ by inserting $n$ somewhere in a total order of $\{ 1, 2, \dots n-1 \}$. Exactly one way of doing this puts $n$ in its own cycle; the other $n - 1$ ways put $n$ in some other cycle. So the generating function for $S_{n-1}$ is $(x + n - 1)$ times the generating function for $S_n$. – Qiaochu Yuan Mar 12 '15 at 22:28
• This appears to be true. We ask how we can join $n+1$ to a permutation of $[n]$ decomposed into cycles. It could either be a fixed point (giving a new cycle and hence a multplier of $x$) or it could be inserted somewhere on the existing cycles in one of $n$ available slots / midpoints of an edge, giving the multiplier $n.$ The result follows. – Marko Riedel Mar 12 '15 at 22:45

Here is a tedious but extremely elementary combinatorial argument for the more general result.

Let $\pi$ be a permutation of $[n]$ having $k$ cycles. The standard representation of $\pi$ is

$$(a_{11}a_{12}\ldots a_{1m_1})(a_{21}a_{22}\ldots a_{2m_2})\ldots(a_{k1}a_{k2}\ldots a_{km_k})\;,\tag{1}$$

where $a_{i1}>a_{ij}$ for $i=1,\ldots k$ and $j=2\ldots,m_i$, and $a_{11}<a_{21}<\ldots a_{k1}$. In other words, each cycle is listed with its largest element first, and the cycles are listed in increasing order of their largest elements. One-element cycles are not suppressed. The map that sends $\pi$ to the permutation whose one-line representation is $(1)$ without the parentheses is a bijection.

Now we’ll count the permutations $\pi$ with $k$ cycles as in $(1)$. Clearly $a_{k1}=n$, but we have a free choice for $a_{11},a_{21},\ldots,a_{k-1,1}$. Once they’re chosen, in how many ways can we fill out $(1)$? We can ignore the parentheses, and of course we have to put $a_{11}$ in the first slot. We now place the $a_{11}-1$ elements of $[n]$ that are less than $a_{11}$; they can go anywhere in $(1)$ after $a_{11}$ so they can be placed in $(n-1)(n-2)\ldots(n-a_{11}+1)$ different ways. Once they’ve been placed, $a_{21}$ must go in the first free slot. That leaves $n-a_{11}-1$ open slots in $(1)$, and the $a_{21}-a_{11}-1$ elements of $[n]$ that are larger than $a_{11}$ and smaller than $a_{21}$ can go in any of them. Thus, they can be placed in

$$(n-a_{11}-1)(n-a_{11}-2)\ldots(n-a_{21}+1)$$

different ways, after which $a_{31}$ must be placed in the first available slot.

In general, once we’ve made the forced placement of $a_{i1}$, the $a_{i1}-a_{i-1,1}-1$ elements of $[n]$ lying strictly between $a_{i-1,1}$ and $a_{i1}$ can be placed in

$$(n-a_{i-1,1}-1)(n-a_{i-1,1}-2)\ldots(n-a_{i1}+1)$$

different ways. Thus, if we set $a_{01}=0$, the number of permutations with these values of $a_{11},\ldots,a_{k1}$ is

$$\prod_{i=0}^{k-1}(n-a_{i-1,1}-1)(n-a_{i-1,1}-2)\ldots(n-a_{i1}+1)=\frac{(n-1)!}{\prod_{i=1}^{k-1}(n-a_{k1})}\;.\tag{2}$$

As we run over all possible choices for the leading elements $a_{11},\ldots,a_{k1}$, the denominator in $(2)$ runs over all $(k-1)$-fold products of distinct elements of $[n-1]$, so $(2)$ itself runs over all $(n-k)$-fold products of distinct elements of $[n-1]$, and $n\brack k$ is therefore the sum of all such products.

However, that sum is clearly also the coefficient of $x^k$ in the product

$$x^{\overline n}=\prod_{i=0}^{n-1}(x+i)=x(x+1)(x+2)\ldots(x+n-1)\;,$$

so in general we have the identity

$$x^{\overline n}=\sum_{k=0}^n{n\brack k}x^k\;,$$

and the desired identity follows by setting $x=2$.