Finding the amount partitions of a multiset

Solution 1:

Let $A$ be a multiset containing $n$ distinct integers having multiplicities $0 \lt r_i \le m, i=1,\ldots,n$. We are asked to count how many ways $A$ can be partitioned into $m$ ordinary sets $C_j \subseteq A, j=1,\ldots,m$.

We assume that ordering of these cells $C_j$ is of no consequence in our counting, repeated (equal) cells are allowed, and no cell is the empty set $C_j \neq \emptyset$.

These $C_j$ can be identified with columns of an $n\times m$ binary matrix $M$ whose rows contain a $1$ or $0$ according the the presence or absence, resp., of the $i$th integer in the $j$th set $C_j$. The multiplicity $r_i$ of the $i$th integer is the $i$th row sum, and indifference as to ordering of cells is imposed by putting the columns in lexicographic order. Finally the absence of an empty set among cells amounts to $M$ having no columns of all zeros.

The number of such matrices can be computed by a procedure similar to the one for counting binary matrices with prescribed row sums and unique columns, using a product of integer "transition" matrices that express the building of the matrix one row at a time, but instead of guaranteeing that all columns are distinct when the final row is added, we have to guarantee all columns are nonzero at that point. This turns out to be a somewhat easier condition.

We then count the number of distinct outcomes by forming:

$$ P(m) = [1, 0, \ldots ,0] ( \prod_{i=1}^n T_i ) [1, \ldots ,1, 1]^T $$

where $T_i$ is an integer matrix, depending only on $m$ and $r_i$, whose entries count the ways of transitioning from the stage where $M$ has its first $i-1$ rows filled in to the next, where $M$ has its first $i$ rows filled in, subject to the restriction on row sums and lexicographic ordering of columns.

NB: The count $P(m)$ includes possible matrices with zero columns (corresponding to using empty sets in the "partition"), but we can exclude these from the count by taking $P(m) - P(m-1)$.

The initial state for $M$ is empty rows, in which all columns $C_j$ are "equivalent" (being empty). At each stage we must account for all possible states that can arise to the extent that adding the next row can be done (filling $r_i$ entries) in accordance with lexicographic ordering.

To represent states we use a partition of the integer $m$:

$$ m = s_1 + s_2 + \ldots + s_k, s_1 \ge s_2 \ldots s_k $$

which describe how many identical columns there are grouped among the $m$ columns so far in the construction.

When entries are introduced in the $i$th row the partition of the integer $m$ may be refined (broken down into smaller summands) or stay the same, but we can never go backward. Columns that were previously different cannot become identical by introducing more entries. Thus the matrix of transition counts is upper triangular.

To compute the transition counts one can take a partition of integer $m=s_1+\ldots+s_k$ and generate all the possible weak compositions of row sum $r$ that are dominated by the given partition:

$$ r = t_1 + \ldots + t_k, 0 \le t_d \le s_d $$

Since $r_i \le m$, it's always possible to find room to put the prescribed ones somewhere in the $i$th row and thus find a partition of $r_i$ satisfying the above. Note also that for weak compositions, order of summands matters and summands are allowed to be zero.

For each such weak composition, the partition of integer $m$ is modified accordingly as some groups of identical columns stay intact and some become split into two new groups as the columns acquires a mixture of both one and zero entries on the $i$th row.

Next we revisit some smallish examples where $m = n = 2e$ and each row sum $r_i = e$, for $e = 2,3$.