4
$\begingroup$

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.

  • 0
    No need to apologize. I was simply pointing out why it might be advantageous to you and those who answer your questions to wait a while. Thanks for the question :-)2012-07-10

2 Answers 2

2

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

  • 0
    Thanks, that's exactly what I was looking for.2012-07-09
2

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.