# The number of pairings between multisets

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.

• What do you mean by "pairing"? – Qiaochu Yuan Jun 9 '11 at 17:26
• 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? – rlo Jun 9 '11 at 17:56

## 1 Answer

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.

• 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. – rlo Jun 9 '11 at 21:12