Lemma:Let be the number of ordered partitions of a set of n elements in k sets. - or the number of ways in which you can distribute n balls into k boxes -

Then

Proof

Let's compute the coefficient of of the RHS.

Since it follows that our coefficient is:

Now: and each term is the number of ordered permutations in which you can have elements in box number 1, ... -permutations with repetition -

So the coefficient is actually

Next note that -the LHS is the stirling number of the second kind, or, the number of partitions of a set of n elements into k sets (here we do not care about the order) -

Hence: and summing over k :

Since: we are done