3
$\begingroup$

I've got a combinatorial question:

Let $n, k\ge 1$ integers and let $S$ be a finite multiset of order $nk$ (counted with multiplicities). I want to count partitions of $S$ into blocks subject to the following conditions:

(1) Each block has got exactly k elements (counted with multiplicities)

(2) The order of the blocks in the partition is irrelevant, i.e. permuting the blocks inside the partition doesn't give rise to a new partition

(3) The order of the elements in a block is relevant, i.e. permuting the elements in a block can give rise to a new block

Example: $S=\{1,2,2,3\}$, $n=k=2$. Then $\{\{1,2\},\{2,3\}\}$ is such a partition and $\{\{2,3\},\{1,2\}\}$ is the same one but $\{\{1,2\},\{3,2\}\}$ is a different one. Counting this way we get six partitions: $\{\{1,2\},\{2,3\}\}, \{\{1,2\},\{3,2\}\}, \{\{1,3\},\{2,2\}\}, \{\{2,1\},\{2,3\}\}, \{\{2,1\}, \{3,2\}\}, \{\{2,2\},\{3,1\}\}$

Is there a name for this kind of partition? Does anybody know a formula for the number of such partitions? Asymptotics? Clearly, if all elements in $S$ are different the searched for formula is $(nk)!/n!$. But what if there are multiple elements?

$\endgroup$
4
  • $\begingroup$ I think counting these amounts to a known hard problem. One way to think about partitions of multisets is with contingency tables whose marginal totals are given. See here for generating the partitions, which links here for the counting problem. $\endgroup$ – hardmath Mar 8 '17 at 14:06
  • 1
    $\begingroup$ Thanks! This seems promising, though the reformulation in terms of contingency tables with given marginal totals doesn't take into account (3) (i.e. $\{2,3\}$ should be a different block than $\{3,2\}$). Any ideas on this? Do you have any recommendations concerning literature? $\endgroup$ – borntomath Mar 9 '17 at 11:03
  • $\begingroup$ Right, the Comment was intended to gauge the difficulty of your Question rather than to give an Answer. I put some references in an Answer to this MathOverflow Question, which deals with both $k$-combinations and $k$-permutations, and I have a nagging thought I collected some further references in response to a Math.SE post. I'll check. $\endgroup$ – hardmath Mar 9 '17 at 12:44
  • $\begingroup$ I believe my nagging recollection was for this earlier Question (and my Comments/Answer there): On counting and generating all $k$-permutations of a multiset. $\endgroup$ – hardmath Mar 10 '17 at 3:08
0
$\begingroup$

The approach noted in the Question of computing $(nk)!/n!$, which is exact if all the items are distinct, in general gives an upper bound on the counting. A modest change in computation gives us a lower bound:

Let the multiplicities of distinct items be $m_1,m_2,\ldots,m_t$, so that: $$ \sum_{i=1}^t m_i = nk $$ Then the desired count will be at least: $$\frac{(nk)!}{m_1!m_2!\ldots m_t! n!} $$

One way to realize this is a lower bound is by choosing an arrangement of all $nk$ items. By the multinomial formula there are $ \binom{nk}{m_1,m_2,\ldots,m_t}=\frac{(nk)!}{m_1!m_2!\ldots m_t!} $ ways, which might be thought of as the "single block" case $n=1$. Now snip the single block into a sequence of $n$ equal sub-blocks. If all the blocks were distinct, then dividing by $n!$ gives the exact corresponding number of arrangements, but since in general there could be identical sub-blocks, this can be an over-reduction. Thus the above is only a lower bound.

In the example provided in the Question this does give us an exact count:

$$ \frac{4!}{1!2!1!2!} = 6 $$

because it is impossible with those multiplicities to get two identical sub-blocks.

This approach can be modified (with additional effort required) to give an exact count. We introduce some terminology to aid in formulation.

Definition Let $\mathscr{S}$ be a multi-set of $k$-permutations drawn from multi-set $A$ whose separate multiplicities add up to the corresponding total multiplicities in $A$. We will say that $\mathscr{S}$ is a $k$-tuple resolution of $A$, but this is just to coin a phrase.

For each $k$-resolution $\mathscr{S}$ of $A$, we associate with it $\sigma_\mathscr{S}$ an integer partition of $n$ given by counting the multiplicities of the $k$-permutations belonging to $\mathscr{S}$. If all the $k$-permutations in $\mathscr{S}$ are distinct, then $\sigma_\mathscr{S}$ is simply the sum-of-ones $1+1+\ldots+1=n$. Otherwise the partition $\sigma_\mathscr{S}$ will have some part greater than $1$.

Let $\Sigma = \sigma_\mathscr{S}$ be a random integer partition of $n$ defined by randomly sampling $\mathscr{S}$ as outlined in the above, splitting a random permutation of $A$ into a sequence of $k$-permutations, which are then collected into the multi-set $\mathscr{S}$.

Let $\mu(\sigma) = \frac{n!}{p_1!p_2!\ldots p_s!} = \binom{n}{p_1,p_2,\ldots,p_s}$ be the multinomial coefficient corresponding to integer partition $\sigma$ of $n$ with $s$ parts:

$$ p_1 + p_2 + \ldots + p_s = n $$

If $\mathbf{P_n}$ is the set of all integer partitions of $n$, the probability distribution of $\Sigma$ determined by the above sampling produces probability values $p_\sigma = \Pr(\Sigma=\sigma)$ for each $\sigma \in \mathbf{P_n}$.

The exact count of distinct $k$-resolutions of $A$ is then:

$$ \frac{(nk)!}{m_1!m_2!\ldots m_t!} \sum_{\sigma \in \mathbf{P_n} } \frac{p_\sigma}{\mu(\sigma)} $$

The difficulty in computing the probabilities $p_\sigma$ depends on the multiplicities $m_i$ of items in $A$. When $k$ is large and a high fraction of the items belong to the classes of items with small multiplicities, then the probability $p_\sigma$ will be concentrated on the sum-of-ones integer partition $\sigma$. Then our lower bound above will be correspondingly close to the actual value.

References

I'm unable as yet to give a citation that considers the OP's exact problem. It concerns "partitioning" a multiset, not into sets or multisets, but into equal length $k$-permutations (aka $k$-tuples). The latter topic has been discussed here and is fairly standard in combinatorial terminology.

Lacking a more specific reference I will point out a pair of book length (or longer) treatments. One of these is also mentioned in previous posts:

Stanley, Richard P. Enumerative Combinatorics, (Cambridge University Press, 1997/1999): two volumes

MacMahon, Percy A. Combinatory Analysis, (AMS Chelsea Publishing, 2001): two volumes bound as one book

The latter is a reprint of volumes by MacMahon originally published in 1915 and 1916. This material was also covered in a 1978 work edited by George Andrews:

Andrews, George E. (editor) Percy Alexander MacMahon: Collected papers, Volume I, Combinatorics (Mathematicians of Our Time Series, The MIT Press, Cambridge, Massachusetts, 1978)

Andrews' book seems now out of print, but I suspect it is a very desirable way to appreciate MacMahon's work, esp. on partitions of multisets. A 1980 review by John Riordan in Bull. AMS is available online by Project Euclid. The Internet Archive also has images of MacMahon's original volumes.

$\endgroup$
3
  • $\begingroup$ I'd appreciate a sample set of parameters for a realistic version of your problems, so that I can better illustrate the tightness of bounds. @borntomath $\endgroup$ – hardmath Mar 10 '17 at 16:07
  • $\begingroup$ Wow! Thanks a lot! I have to work through this stuff. At the moment it seems to me, that I need this in full generality, hence at the moment I cannot make further restrictions $\endgroup$ – borntomath Mar 14 '17 at 9:49
  • $\begingroup$ If you read down the Answer, you will find an expression "in full generality". I'm not sure if you noticed that. $\endgroup$ – hardmath Mar 18 '17 at 16:42

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.