Let $a_n$ is the number of orderly divisions of set $\left\{ 1,2,...,n \right\}$ (which means that the sequence of blocks is important, but not the order of elements in blocks). Prove that: $\displaystyle \sum_{k}\left[n\atop k\right]a_k=n!2^{n-1}$ for $n\ge 1$.
Is it possible to prove this by induction on $n$? I think combinatorial interpretation will be easier way, but I don't know how to do that.
On
I failed to see a direct combinatorial interpretation, but (IMHO) I found a combinatorially satisfying derivation nevertheless (induction seemed unnatural to me). First, my conventions:
The number of ways to partition $[k]=\{1,2,\cdots,k\}$ into $\ell$ cells, the cells collectively ordered but not internally, is given by $\ell!\left\{k\atop \ell\right\}$ via inspection. Summing over $\ell$ yields
$$a_k=\sum_{\ell=1}^k \ell! \left\{k\atop\ell\right\}. \tag{1}$$
Plugging this into the left-hand side of the given formula and rearranging yields
$$F=\sum_{k=0}^n \left[n\atop k\right]a_k=\sum_{k=0}^n \left[n\atop k\right] \left(\sum_{\ell=1}^k \ell!\left\{k\atop\ell\right\}\right)=\sum_{\ell=1}^n \ell!\left(\color{Purple}{\sum_{k=\ell}^n\left[n\atop k\right]\left\{k\atop\ell\right\}}\right) \tag{2}$$
We seek a combinatorial interpretation of the sum in purple. The 1st kind of Stirling numbers counts permutations in $S_n$ with $k$ disjoint cycles ($\pi=\tau_1\cdots\tau_k$), and after multiplying by the 2nd kind of Stirling number we are counting "refinements" of these permutations into $\ell$ subsets, each subset containing at least one of $\pi$'s cycles. For example, for $\pi=(12)(34)(56)(789)$ one of these collections of three subsets containing its cycles would be $\{(12),(789)\},\{(34)\},\{(56)\}$.
Notice that sets of disjoint cycles are in bijection with the products of those cycles, so we can instead interpret this as counting the number of collections of $\ell$ singleton sets of disjoint permutations, the total number of items the permutations acting on being $n$. Equivalently, for each set partition $\Gamma$ of the set $[n]=\{1,2,\cdots,n\}$ into $\ell$ disjoint subsets, we count the number of permutation collections
$$\{\sigma_\gamma\in S_{\gamma}:\gamma\in\Gamma\}, \tag{$*$}$$
where each $\gamma$ is a cell of the partition $\Gamma$ and $S_\gamma$ is its permutation group, and then summing over all the $\ell$-part set partitions $\Gamma$ of $[n]$. But for $\Gamma$ fixed, recall that permutations of a set $\gamma$ are in bijection with ways of ordering the elements of $\gamma$; ultimately we are counting the number of ways to partition $[n]$ into $\ell$ internally ordered sets, the Lah numbers! Therefore we obtain
$$F=\sum_{\ell=1}^n\ell! \color{Purple}{L(n,\ell)}.$$
This is the final stretch, and it is not difficult. For each partitioning of $[n]$ into $\ell$ internally ordered subsets (counted by the Lah numbers), we can multiply by $\ell!$ to further count the number of partitions of $[n]$ into $\ell$ subsets ordered both internally and externally. This is equivalent to ordering sequentially the elements of $[n]$ and placing precisely $\ell-1$ bars $|$ in between them to separate them into blocks (there are precisely $n-1$ implicit spaces between the numbers to put the bars).
Of course, there are $n!$ sequential arrangements and independently there are $2^{n-1}$ subsets of the set of all spaces between the numbers to place the bars. Thus, $F=n!\,2^{n-1}$.
I managed to find a more direct combinatorial argument. $n!\,2^{n-1}$ is the number of ways to choose a permutation $\pi$ of $[n]$ and insert bars in any subset of the spaces between the elements of the permutation. In other words, it counts the strings of the form $$\pi_1\mid\pi_2\mid\dots\mid\pi_k\tag{1}$$ such that $\pi=\pi_1\dots\pi_k$ and $|\pi_i|>0$ for $i=1,\dots,k$.
Let $\sigma=\pi_1\mid\pi_2\mid\dots\mid\pi_k$ by such a string, and consider a $\pi_i=a_1a_2\dots a_m$, say. Break $\pi_i$ into segments in the following way. The first segment begins with $a_1$. If $a_1=\max\{a_j:j=1,\dots m\}$, there is only one segment, $\pi_i$. Otherwise, the second segment begins with the first $a_j$ larger than $a_1$. Continue in this fashion: $a_j$ begins a new segment iff $a_j>a_\ell$ for all $\ell<j$. Now reinterpret each of these segments as a cycle, $\pi_i$ as an unordered set $A_i$ of disjoint cycles, and $\sigma$ as a sequence $\langle A_1,\dots,A_k\rangle$ of $k$ unordered sets of cycles that collectively exhaust $[n]$. Let $S$ be the set of such $\langle A_1,\dots,A_k\rangle$; clearly from each $\langle A_1,\dots,A_k\rangle\in S$ we can reconstruct the corresponding $\pi$ of form $(1)$, so $|S|=n!\,2^{n-1}$.
For $1\le\ell\le n$ let $S_\ell$ be the set of $\langle A_1,\dots,A_k\rangle\in S$ such that $A_1\cup\dots\cup A_k$ contains $\ell$ cycles. $\left[n\atop \ell\right]$ is the number of ways to partition $[n]$ into $\ell$ parts and assign a cyclic order to each part, so it is simply the number of sets $\{\sigma_1,\dots,\sigma_\ell\}$, where the $\sigma_i$ are disjoint cycles whose union is $[n]$. Then $a_\ell$ is the number of orderly divisions $\langle A_1,\dots,A_k\rangle$ of $\{\sigma_1,\dots,\sigma_\ell\}$. Thus, $\left[n\atop\ell\right]a_\ell$ is the number of ways to break $[n]$ into $\ell$ cycles, partition the set of cycles, and order the partition, i.e., $\left[n\atop\ell\right]a_\ell=|S_\ell|$. Since $S=\bigcup\limits_{\ell=1}^nS_\ell$, and the $S_\ell$ are pairwise disjoint, it follows that $$n!\,2^{n-1}=\sum_{\ell=1}^n\left[n\atop\ell\right]a_\ell\;,$$ as desired.