Ordered set partitions 
Let $a_n$ be a number of ordered partitions of the set $\left\{1,\ldots,n\right\}$, which means that order of elements in block is not relevant, but order of blocks does matter. (so $a_n = \sum_k\left\{n\atop k\right\}k!$, if I'm not mistaken). Prove recurrence relation:
  $$a_0=1; \ a_n=\sum_{i=0}^{n-1}{n\choose i} a_i$$

I don't know if I'm tired or it is just difficult. I tried with combinatorial interpretation but nothing came to my mind, so I tried with formula $a_n = \sum_k\left\{n\atop k\right\}k!$ but his also led me to nowhere. Can anybody help?
 A: I would like  to point out that there is  another recurrence for these
numbers that has an interesting combinatorial interpretation.
Note  that ordered  set partitions  where we set the number of partitions of  zero elements to one correspond to the species
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SEQ}(\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
This immediately yields the generating function
$$G(z) = \frac{1}{1-(\exp(z)-1)} = \frac{1}{2-\exp(z)}
= \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$
This gives the sequence
$$1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563,\ldots$$
which is OEIS A000670.
Now differentiate this to obtain
$$G'(z) = -\frac{1}{2} \frac{1}{(1-\exp(z)/2)^2} 
\left(-\frac{\exp(z)}{2}\right) = G(z) \frac{\exp(z)/2}{1-\exp(z)/2}.$$
Extracting  coefficients  here  (this  is  a  product  of  exponential
generating functions) we obtain the alternate recurrence
$$a_{n+1} = \sum_{k=0}^n {n\choose k} a_k
(n-k)! [z^{n-k}] \frac{\exp(z)/2}{1-\exp(z)/2}.$$
Interestingly  the  second factor  in  the sum  turns  out  to have  a
combinatorial interpretation. It gives the following sequence
$$1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126,\ldots$$
which is OEIS A000629.
This second sequence counts  necklaces (oriented cycles) of partitions
of $n+1$ labelled elements.  Doing the coefficient extraction we have the
following combinatorial formula:
$$a_{n+1} = \sum_{k=0}^n {n\choose k} a_k
\sum_{q\ge 1} \frac{q^{n-k}}{2^q}.$$
Note that we  can give an intuitive meaning to this  formula.  It is a
classification of ordered set partitions according to the total number
of elements to  the left of the partition  containing the element with
the label $n+1$.  We chose these $k$ elements  from $n$ elements total
excluding the  one labeled $n+1$ and  make them into  a set partition,
which is counted  by $a_k.$ We combine this  partition with a necklace
of partitions  on $n-k+1$ elements, which we take apart  after the set
containing the largest element and join it to the set partition of the
first  $k$  elements with  re-labeling  so  that  the largest  element
becomes  $n+1.$  This  is   clearly  a  bijection  (just  reverse  the
construction). Note that  this would not  have worked  with an ordered
partition  as the  second  piece as it would not permit control of the
position of the $n+1$ element.

**Concluding  remark.**   Note  that  the  species   of  necklaces  of
partitions if given by $$\textsc{CYC}(\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
This yields the generating function
$$H(z) = \log\frac{1}{1-z}\circ (\exp(z)-1)
= \log\frac{1}{2-\exp(z)}$$
This counts these necklaces on $n$ elements.
Differentiate
$$H'(z) = (-\log(2-\exp(z)))'
= -\frac{1}{2-\exp(z)} (-\exp(z)) \\= \frac{\exp(z)}{2-\exp(z)}
= \frac{\exp(z)/2}{1-\exp(z)/2}$$
to obtain the generating function for necklaces of partitions on $n+1$
elements, which we recognize from above.
A: I suppose you cominatorial interpretation is - if I want to divide n-elements then I first choose $n-i > 0$ elements that will be put in the first block and then I divide the rest of them in $a_i$ ways which yields the desired formula. 
also note that ${n\choose i}$ = ${n \choose {n-i}}$
