7
$\begingroup$

The Stirling number of the second kind $S(n,k)$, where

$S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$

Gives the number of unique unlabeled, unordered partitions of $n$ elements into $k$ partitions. I am interested in determining a procedure for enumerating all of these partitions. What I have had in mind is to start with a vector

$v=\left[\begin{array}{l}i_1\\i_2\\{\vdots}\\i_n\end{array}\right]$

And then generate a set of "partition vectors'', each with $n$ elements, having a form (for $k=2$) of $[x_1~x_2~\cdots~x_n]$, where each $x_i$ is (following some suitable algorithm) chosen from $\left\{0~1\right\}$.

I didn't know whether this question was more appropriate for Math or Stackoverflow, so I asked it here since this site allows pretty formatting of equations.

edit:

Thanks in part to comments by @Henry I've made some progress in the special cases where $k=2$ and also for $k=3$ (where $n$ is not divisible by $3$).

For $k=2$, an alternative to the first equation is:

$\sum\limits_{i=1}^{[[\frac{n}{2}]]}\frac{1}{\eta\,!}\left(\begin{array}{c}n\\n-i\end{array}\right)$

where $\eta$ is equal to the number of partitions having the same number of members.

To implement the $k=2$ case for any arbitrary value of $n$, start with a vector $v_{\circ}$ of length $n$ filled with zeroes, and another vector, $v_\alpha$, with values $1,2,\cdots,n$, in that order. Generate the set $A$ of possible combinations of $n-i$ elements chosen from $v_\alpha$. The members of $A$ are used to identify the indices of elements of successive copies of $v_{\circ}$ whose values should be changed to ones.

At this point, the number of vectors generated will exceed $S(n,2)$, because a partition like $[0~1~1~0]$, which is equivalent to $[1~0~0~1]$, is generated twice. In the solutions containing two equal-sized partitions, the redundant ones can be taken out by deleting all of the sets where $n-i = i$ which have a $0$ prior to any $1$.

For $k=3$, start by listing the $N$ possible combinations of three partition sizes. So for $n=7$, there is:

$\begin{array}{lrrr} \phi_1&5&1&1\\ \phi_2&4&2&1\\ \phi_3&3&3&1\\ \phi_4&3&2&2\\ \end{array}$

The total number of possible partitions is:

$\frac{1}{2!}\left(\begin{array}{c}7\\5\end{array}\right)\left(\begin{array}{c}2\\1\end{array}\right) + \left(\begin{array}{c}7\\4\end{array}\right)\left(\begin{array}{c}3\\2\end{array}\right)+ \frac{1}{2!}\left(\begin{array}{c}7\\3\end{array}\right)\left(\begin{array}{c}4\\3\end{array}\right)+ \frac{1}{2!}\left(\begin{array}{c}7\\3\end{array}\right)\left(\begin{array}{c}4\\2\end{array}\right)$

To enumerate the partitions corresponding to each of these terms, set up a general schema:

$\begin{array}{lrrr} \phi_i&a&b&c\end{array}$

for contributing $\frac{1}{\eta\,!}\left(\begin{array}{c}n\\a\end{array}\right)\left(\begin{array}{c}b+c\\b\end{array}\right)$ possible partitions. (Note that this could be simplified to $\frac{1}{\eta\,!}\cdot\frac{n!}{a!b!c!}$, but this would not facilitate the computational procedure.)

where $a+b+c=n$. Start again with a vector $v_\circ$ containing $n$ zeroes, and a vector $v_\alpha$ containing $1,2,\cdots,n$. As before, generate the set A of possible combinations of $a$ elements chosen from $v_\alpha$, and use these values to specify indices in successive copies of $v_\circ$ whose values should be changed to 1.

Each of the copies of $v_\circ$ now contains $a$ ones and $b+c$ zeroes.

At this point, one will require the use of a function $W(v,j)$, which returns the index pertaining to the $j^{th}$ zero in vector $v$. Now make a vector $v_\alpha^\prime$ containing $1,2,\cdots,b+c$. Generate a set $A^\prime$ of possible combinations of $b$ elements chosen from $v_\alpha^\prime$, and use these values to specify values of $j$ which are fed into $W$, which specifies the indices in copies of copies of $v_\circ$ whose values should be changed to $2$.

To remove redundant partitions, delete every copy of $v_\circ$ containing a $0$ which precedes all $2$'s, if $b=c$, and delete every copy of $v_\circ$ containing a $2$ which precedes all $1$'s, if $a=b$.

2 Answers 2

4

An algorithm for generating all partitions of $n$ elements into $k$ sets is given in Volume 4A of Knuth's The Art of Computer Programming (which was apparently finally published last year; I didn't know that). The subsection is available on his website as fascicle 3b; the algorithm is on page $27$.

  • 1
    There's an implementation of this algorithm in Python here: https://codereview.stackexchange.com/a/1944/298622017-06-07
0

Your method for $k=2$ will produce too many, first because they may all have the same value ($2$ cases) and second because each partition will be repeated twice (swapping $0$s and $1$s). So while you produce $2^n$ cases, in fact $S(n,2)=\frac{2^n-2}{2}=2^{n-1}-1$.

If you were simply looking to produce all the partitions of your $n$ elements you could take the iterative approach of generating all the partitions of the first $n-1$ elements and then for each partition adding the $n$th element to one of the existing parts or as a new extra part. So in practice, you start with the first element which must be in a new part. Then you either add the second element, either to the first part or as a new part. And so on.

Since you want all the partitions of your $n$ elements with exactly $k$ parts, you can ignore any partition of $n-j$ in the iterative process which has strictly fewer than $k-j$ parts or more than $k$ parts.