The number of pairings between multisets - MathOverflow 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 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 Answer by Richard Stanley for The number of pairings between multisets 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>