3
$\begingroup$

Given two multisets $A$ and $B$ of the same finite cardinality $n$, how many ways are there of pairing the two sets together?

If both sets consist of distinct elements, the answer is $n!$: there are $n$ ways to pair the first element of $A$ with something from $B$, $n-1$ for the second element, etc. If one of the sets has distinct elements and the other is allowed to have repeated elements, again the answer is well-understood. If $A$ has distinct elements and the elements of $B$ have multiplicities $b_1,\dots,b_s$ with $b_1+\dots+b_s=n$, then the number of pairings is $n!/b_1!\dots b_s!$. What's not obvious to me is what happens when both sets are allowed to have repeated elements.

As a simple example, suppose $A=\{1,2,3\}$ and $B=\{a,a,b\}$. Either per the above formula or by simple counting, one sees that there are 3 pairings - $[1a,2a,3b],[1a,2b,3a]$, and $[1b,2a,3a]$. However, if $A=\{1,1,2\}$ and $B=\{a,a,b\}$, then there are only 2 pairings - $[1a,1a,2b]$ and $[1a,1b,2a]$. This example is noteworthy in that it shows that the number of pairings doesn't have to divide $n!/b_1!\dots b_s!$. In particular, if $a_1,\dots,a_r$ are the multiplicities of the elements of $A$, the number of pairings is not $n!/a_1!\dots a_r! b_1! \dots b_s!$, a quantity which does not even have to be an integer.

For my purposes, I'd like to have a way to write this in terms of fairly simple combinatorial objects (multinomial coefficients, Bell or Stirling numbers, etc.), but I'm not convinced this is possible, at least without resorting to a heinous sum. In fact, I only care about the parity of this count, so even a characterization of the $a_i$ and $b_i$ which make this even or odd would be of use to me. The only restriction I have on $A$ and $B$ is that at least one $b_i$, say, must be 1, but I'm not sure how to take advantage of that here.

$\endgroup$
2
  • $\begingroup$ What do you mean by "pairing"? $\endgroup$ Jun 9, 2011 at 17:26
  • $\begingroup$ Sorry, that is perhaps unclear. I included the examples to try to clear things up, but I guess I was unsuccessful. I mean a pairing to be a way to associate to each element of A a unique element of B. Perhaps one-to-one correspondence would be better? $\endgroup$
    – rlo
    Jun 9, 2011 at 17:56

1 Answer 1

12
$\begingroup$

If the multiplicities of the elements of the first multiset are $a_1,a_2,\dots$ and of the second $b_1,b_2,\dots$, then you are asking for the number of matrices $A=(A_{ij})_{i,j\geq 1}$ of nonnegative integers with row-sum vector $(a_1,a_2,\dots)$ and column-sum vector $(b_1,b_2,\dots)$. These are very well-studied numbers, but in general there is no simple formula. Their computation is in fact #P-complete. One reference is Chapter 7 of Enumerative Combinatorics, vol. 2. See for instance Corollary 7.12.3.

$\endgroup$
1
  • $\begingroup$ Thanks, I was sure this had to be well-studied. It's unfortunate that there's no particularly nice formula, but I'll make do. $\endgroup$
    – rlo
    Jun 9, 2011 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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