Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
if someone has already done it, all the better. thanks! –  jlovegren Oct 28 '12 at 23:44
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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