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.

$\endgroup$
3
  • 3
    $\begingroup$ I am not trying to steal André's acceptance, but when an answer is accepted quickly, it often has the effect of reducing the number of people who visit your question, as they might think there is nothing left to do. You may miss out on other answers, more votes for your question, and those who have answered your question might also miss out on votes from visitors that might have come. $\endgroup$ – robjohn♦ Jul 9 '12 at 17:03
  • $\begingroup$ That's fair enough. I thought, without actually reading it anywhere, that the etiquette would be to accept answers as soon as you were happy they were correct. I won't do that in future. Apologies. $\endgroup$ – Fist Jul 10 '12 at 8:17
  • $\begingroup$ 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 :-) $\endgroup$ – robjohn♦ Jul 10 '12 at 11:19
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, that's exactly what I was looking for. $\endgroup$ – Fist Jul 9 '12 at 16:14
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.