The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)

Is there an algorithm to generate all the possible combinations?

  • 1
    $\begingroup$ You can derive such an algorithm directly from the recurrence for these numbers. $\endgroup$
    – D.W.
    Mar 5 '17 at 13:58

Concretely, let us count the number of ways to partition $[n]$ into $k$ non-empty ordered subsets, which are themselves ordered by increasing order of the first element. For example, a valid partition of 10 into 5 sets is $$ \{1,4,5\},\{2,3,6\},\{7\},\{8,10\},\{9\}. $$ Note that $1<2<7<8<9$.

The base cases $k=0,k=1,k=n$ are easy, so suppose $2 \leq k < n$. A partition of $[n]$ into $k$ ordered subsets can be obtained in two ways:

  1. Taking a partition of $[n-1]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.

  2. Taking a partition of $[n-1]$ into $k$ ordered subsets, and adding $n$ to the 1st subset, the 2nd subset, ..., the $k$th subset.

By recursively generating all partitions of $[n-1]$ into $k-1$ or $k$ ordered subsets, you can thus generate all partitions of $[n]$ into $k$ ordered subsets.

As D.W. mentions, this is just the recurrence for the Stirling numbers.


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.