Sum of Stirling numbers of both kinds Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not.
My task:

Prove, that$$\sum_{k=1}^n \left[n\atop k\right] a_k = n!2^{n-1}$$

The only thing I got so far is:
$$a_k = \sum_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$$
I tried to change the order of this sum $\sum\limits_{k=1}^n \left[n\atop k\right]\sum\limits_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$
and got something like that: $\sum\limits_{k=1}^n \frac{1}{k!}\sum\limits_{i=k}^{n} \left[n\atop i\right]\left\{i\atop k\right\}$

My next idea was combinatorial proof, but either I cannot think of one, or I made some crucial mistake above, which makes my efforts pretty useless.


Can anyone guide me how to do this task?
I'd also be most thankful for correcting my mistakes - I'd rather make them here than on my exam sheet...

Start  by observing  that the  species of  orderly partitions  has the
specification 
$$\mathfrak{S}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$
This gives the bivariate generating function
$$G(z, u) = \frac{1}{1-u(\exp(z)-1)}.$$
Hence the generating function of the $a_n$ is
$$G(z) = G(z, 1) =
\frac{1}{2-\exp(z)}
= \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$
Substituting this into the sum yields
$$\sum_{k=1}^n
\left[n\atop k\right]
k! [z^k]
\frac{1}{2} \frac{1}{1-\exp(z)/2}.$$

Call this sum $P_n$
and introduce the exponential generating function
$$P(z) = \sum_{n\ge 1} P_n \frac{z^n}{n!}.$$

We have for the sum that
$$\sum_{k=1}^n
\left[n\atop k\right]
k! [z^k]
\frac{1}{2} \frac{1}{1-\exp(z)/2}
= \frac{1}{2} \sum_{k=1}^n
\left[n\atop k\right]
k! [z^k] \sum_{q\ge 0} \frac{\exp(qz)}{2^q}
\\= \frac{1}{2} \sum_{k=1}^n
\left[n\atop k\right]
\sum_{q\ge 1} \frac{q^k}{2^q}.$$
This gives for $P(z)$ that
$$P(z) = \frac{1}{2}\sum_{n\ge 1}
\frac{z^n}{n!} \sum_{k=1}^n
\left[n\atop k\right]
\sum_{q\ge 1} \frac{q^k}{2^q}
= \frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} 
\frac{q^k}{2^q}
\sum_{n\ge k}
\left[n\atop k\right] \frac{z^n}{n!}.$$
Recall that the species for Stirling numbers of the first kind is
given by
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z})).$$
This gives the bivariate generating function
$$H(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Substituting this into $P(z)$ yields
$$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} 
\frac{q^k}{2^q}
\sum_{n\ge k}
\frac{z^n}{n!} n! [z^n] [u^k] 
\exp\left(u\log\frac{1}{1-z}\right)
\\ =\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} 
\frac{q^k}{2^q}
\sum_{n\ge k}
z^n [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Now the innermost sum annihilates the coefficient extractor so we get
$$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} 
\frac{q^k}{2^q}
\frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k
=  \frac{1}{2} \sum_{q\ge 1} 
\frac{1}{2^q} 
\left(-1 + \exp\left(q\log\frac{1}{1-z}\right)\right)
\\ = -\frac{1}{2}
+ \frac{1}{2} \sum_{q\ge 1} 
\frac{1}{2^q} \left(\frac{1}{1-z}\right)^q
= -\frac{1}{2}
+ \frac{1}{2} \frac{1/2/(1-z)}{1-1/2/(1-z)} 
\\ = -\frac{1}{2}
+ \frac{1}{2} \frac{1}{2(1-z)-1}
= -\frac{1}{2}
+ \frac{1}{2} \frac{1}{1-2z}.$$
The conclusion is that
$$P_n = n! [z^n] P(z) = n! [z^n]  \frac{1}{2} \frac{1}{1-2z} = 
n! \times \frac{1}{2} \times 2^n
= 2^{n-1} n!$$
as claimed.

Another computation that refererences Wilf's generatingfunctionology.
Remark, somewhat later. The annihilated coefficient extractor is not strictly necessary here, we may also recognize the EGF by inspection.
