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...

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\}$$
