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.
Best Answer
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).$$