most recent 30 from http://mathoverflow.net 2013-06-20T06:37:08Z http://mathoverflow.net/feeds/question/67359 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67359/the-number-of-pairings-between-multisets rlo 2011-06-09T17:17:13Z 2011-06-09T18:40:05Z

<p>Given two multisets $A$ and $B$ of the same finite cardinality $n$, how many ways are there of pairing the two sets together?</p> <p>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.</p> <p>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.</p> <p>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.</p>

http://mathoverflow.net/questions/67359/the-number-of-pairings-between-multisets/67365#67365 Richard Stanley 2011-06-09T18:40:05Z 2011-06-09T18:40:05Z

<p>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 <em>Enumerative Combinatorics</em>, vol. 2. See for instance Corollary 7.12.3.</p>