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.



The number of pairings between multisets
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.


