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.

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

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.

| cite | improve this answer | |
  • $\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 '11 at 21:12

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.