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...
 A: Here’s a combinatorial argument to show that
$$\sum_{k=1}^n \left[n\atop k\right] a_k = n!2^{n-1}\;,$$
where $\left[n\atop k\right]$ is the number of permutations of $[n]=\{1,\dots,n\}$ having $k$ cycles, and $a_k$ is the number of orderly partitions of those $k$ cycles.
First, $n!2^{n-1}$ is clearly the number of ways of breaking a permutation of $[n]$ ($=\{1,\dots,n\}$) into segments by inserting breakpoints between neighboring elements of the partition; the number of segments may be anywhere from $1$ (no breakpoints) through $n$ ($n-1$ breakpoints).
Now consider such a segmented partition. For example, with $n=9$ we might have $$31\mid6259\mid478\;.\tag{1}$$ Each segment will correspond to an unordered set of cycles. To break a segment into cycles, mark each number in the segment that is larger than all of its predecessors within the segment: $$\underline{3}1\mid\underline{6}25\underline{9}\mid\underline{4}\underline{7}\underline{8}\;.$$ Clearly the first number in each segment will be marked. The substring from a marked number up to but not including the next marked number or the end of the segment is a cycle: $$(\underline{3}1)\mid(\underline{6}25)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ The segmented partition $(1)$ thus corresponds to the $3$-tuple $\left\langle\{(31)\},\{(625),(9)\},\{(4),(7),(8)\}\right\rangle$ of sets of cycles partitioning the $6$ cycles of the permutation $(31)(4)(625)(7)(8)(9)$. This is one of the orderly partitions counted by the term $\left[9\atop 6\right]a_6$ of the sum $\sum_{k=1}^9\left[9\atop k\right]a_k$.
Conversely, if $\langle\{13\},\{(9),(526)\},\{(7),(8),(4)\}\rangle$ is an orderly partition of $[9]$, we can reconstruct the corresponding segmented permutation as follows. First insert the segmentation corresponding to the sets in the partition: $$(13)\mid(9)(526)\mid(7)(8)(4)\;.$$ Within each segment mark each number that is the largest number in its cycle: $$(1\underline{3})\mid(\underline{9})(52\underline{6})\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Rotate each cycle to bring the largest number to the front: $$(\underline{3}1)\mid(\underline{9})(\underline{6}52)\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Within each segment rearrange the cycles in descending order of maximal element: $$(\underline{3}1)\mid(\underline{6}52)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ Finally, erase the markings and the parentheses, leaving only the segmentation: $$31\mid6529\mid478\;.$$
A bit of thought will show that these operations do define in general a bijection between segmented permutations and orderly partitions of the cycles of permutations of $[n]$.

There are a couple of errors in your computations.
$\left\{k\atop i\right\}$ is the number of partitions of $k$ distinguishable objects into $i$ non-empty sets when neither the order within the subset nor the order of the subsets matters. Thus, the number of orderly partitions is $\sum_{i=1}^k\left\{k\atop i\right\}i!$, not $\sum_{i=1}^k\left\{k\atop i\right\}\frac1{i!}$. The desired sum is then 
$$\sum_{k=1}^n\sum_{i=1}^k\left[n\atop k\right]\left\{k\atop i\right\}i!=\sum_{i=1}^ni!\sum_{k=i}^n\left[n\atop k\right]\left\{k\atop i\right\}$$
A: 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.
