Possible combinations of items in a certain number of sets How many ways are there of arranging n elements into k sets given that all elements must be used in each arrangement? No set can be empty and order doesn't matter (i.e. {a, b, c} is the same as {c, b, a}). So for example, say n is 5 and k is three, there would be the following sets:
{a b c d e}

Set 1    Set 2    Set 3
-----    -----    -----
{abc}    {d}      {e}
{ab}     {cd}     {e}
{ab}     {c}      {de}
{a}      {bcd}    {e}
{a}      {bc}     {de}
{a}      {b}      {cde}

etc. The order of the sets does not matter either. So for example, the following are equivalent:
({ab}, {cd}) = ({cd}, {ab})

Another example:
({abc}, {d}, {e}) = ({d}, {e}, {abc})

I'm looking for some sort of formula to calculate this number. I tried to solve it by generating the sets manually and seeing could I come up with a formula. So when n is 3 and k is 2, the number of sets possible:
({ab}, {c}), ({ac}, {b}) and ({cb}, {a}) 

is just 
$$\binom{n}{k} = \binom{3}{2} = 3 $$ 
Increasing n to 4 (with k still as 2) I thought would give 
$$ \binom{n}{k} + \binom{n}{k-1}$$
possible combinations. But I know from just writing out all the possibilities that there are more than that. Any help would be hugely appreciated. Thanks. 
 A: The answer to your question is given by $S(n,k)$, the Stirling numbers of the second kind.
There is no pleasant closed form. However, the Stirling numbers of the second kind satisfy the nice recurrence
$$S(n+1,k)=kS(n,k)+S(n,k-1).$$
A: Let $S(n,k)$ be the number of ways to arrange $n$ objects into $k$ sets where no set is empty and order is not important. Let $\{x_j\}_{j=1}^n$ be the objects.
Compute the number of arrangements where $x_n$ is in a set by itself: that would be the number of ways to arrange the other $n-1$ elements into $k-1$ sets: $S(n-1,k-1)$.
Compute the number of arrangements where $x_n$ is in a set with other elements: that would be the number of ways to arrange the other $n-1$ elements into $k$ sets, times $k$ for whichever of the $k$ sets into which $x_n$ is placed: $k\,S(n-1,k)$.
Thus, we get
$$
S(n,k)=S(n-1,k-1)+kS(n-1,k)\tag{1}
$$
If we also note that $S(n,n)=1$ and $S(n,1)=1$, then we can compute $S(n,k)$ for any $n\ge k\ge1$ using $(1)$.
As André Nicolas mentions, these are the Stirling Numbers of the Second Kind.
