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?     
 A: 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. 
A: 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$.
A: 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.
