Enumerate partitions of identical objects

Question

I have a problem concerning enumerating partitions of a set of identical objects. I know, now someone is going to talk about Stirling number of second kind, but I'm quite sure this is not the answer.

I will describe the problem with an example. Suppose to have a set of $n$ identical objects. The problem is to enumerate and to generate all the partitions obtained with $k$ subsets, like in the following example.

Let $n=5$, $k=3$. Define $B_i$, with $i=1,\dots,k$ the set of the partition. Hence, I can partition the set of $n$ objects by constructing the following partitions:

• $|B_1|=3$, $|B_2|=1$, $|B_3|=1$.
• $|B_1|=2$, $|B_2|=2$, $|B_3|=1$.

Notice that: $(i)$ must result $B_i\neq \emptyset$; $(ii)$ partitions like, for instance, $|B_1|=1$, $|B_2|=3$, $|B_3|=1$ or $|B_1|=1$, $|B_2|=1$, $|B_3|=3$ must not be considered, since are in practice already considered in the first partition (i.e. $|B_1|=3$, $|B_2|=1$, $|B_3|=1$).

Since objects are all identical, I only express the sets cardinality and I doesn't care about the specific object allocated to a set of the partition.

The problem is particular useful in the formulation of algorithms for assignment problems.

Answer 1

You want the function $P(n,k)$ described after formula $(58)$ of this MathWorld article, giving the number of partitions of $n$ into exactly $k$ parts. This is always the same as the number of partitions of $n$ with largest part $k$. For this function, unlike the intermediate function in the Wikipedia article, $P(5,3)=2$; you’ve exhibited the two partitions of $5$ into $3$ parts, and the two partitions of $5$ with maximum part $3$ are $3+2$ and $3+1+1$. The link has a nice recurrence for $P(n,k)$, formula $(59)$:

$$P(n,k)=P(n-1,k-1)+P(n-k,k)\;,$$

with initial conditions

$$\begin{align*} &P(n,k)=0\quad\text{if}\quad k>n\\ &P(n,n)=1\quad\text{for}\quad n\ge 0\\ &P(n,0)=0\quad\text{for}\quad n\ge 0\;. \end{align*}$$

The recurrence is easily verified. Every partition of $n$ into $k$ parts, at least one of which is $1$, is obtained by adding a $1$ part to a partition of $n-1$ into $k-1$ parts. Every partition of $n$ into $k$ parts, all of which are at least $2$, is obtained from a partition of $n-k$ into $k$ parts by adding $1$ to each part.

Answer 2

Don Knuth gives an algorithm for generating all partitions of $n$ into $k$ parts in Algorithm H on p. $2$ of pre-fascicle 3B of The Art of Computer Programming, which is a draft of Sections 7.2.1.4–5. This is available as a gzipped PostScript file on Knuth's website and as a low-quality PDF elsewhere.

Here's the algorithm (in my words; Knuth gives it in pseudocode):

Denote the parts by $a_1$ to $a_k$. Start out with $n-k+1,1,\dotsc,1$. Generate partitions by moving $1$ from $a_1$ to $a_2$ as long as this doesn't make $a_2$ greater than $a_1$. Then look for the first $j$ with $a_j\lt a_1-1$. If there isn't one, you're done. If there is, increment $a_j$ by $1$, set all parts between $a_1$ and $a_j$ to $a_j$ and choose $a_1$ to make the sum come out right; then go back to generating partitions.