14
$\begingroup$

Given $m>1$, what is the number of $2m\times 2m$ matrices, made of $0$ and $1$, such that each row has exactly $m$ ones, and each column has exactly $m$ zeros.

I am not sure if this is a well-known problem.

$\endgroup$
6
  • $\begingroup$ It likely is well known, but I don't know it. I would look at OEIS and works of Ryser. $\endgroup$ Dec 8, 2013 at 23:44
  • $\begingroup$ Could not find any sequence in OEIS. $\endgroup$ Dec 9, 2013 at 0:12
  • 10
    $\begingroup$ It's in OEIS oeis.org/A058527 . Found by computing the first 4 values with generating functions (Mathematica code: Coefficient[SymmetricPolynomial[m, Table[x[i], {i, 1, 2 m}]]^(2 m), Product[x[i]^m, {i, 1, 2 m}]] ) and then searching OEIS. $\endgroup$ Dec 9, 2013 at 0:37
  • 2
    $\begingroup$ The first value at OEIS is for n=0. Practice at OEIS is to include empty and null cases in sequences if there is any prospect someone will believe it exists. It means that the searches "1,2,90,297200" and "2,90,297200" both work, but if the "1" is left off only the second search will work. $\endgroup$ Dec 9, 2013 at 1:07
  • 2
    $\begingroup$ It's useful to know this. 1,2,90 has three matches, easy to dig through by hand. 2,90 has 28, which would be a pain. (Note that 90 is small enough to compute by hand: There are only two orbits up to the $S_4 \times S_4$ action.) $\endgroup$ Dec 9, 2013 at 1:15

1 Answer 1

25
$\begingroup$

An explicit formula for this was published about 30 years ago, but it was wrong. As the matter stands, there is no explicit formula. The values up to m=15 are here. The value for m=16 is known too, let me know if you'd like me to track it down. The asymptotic value appears in this paper. If I'm not mis-translating it is $$ e^{-1/2+o(1)}\frac{\binom{2m}{m}^{4m}}{\binom{4m^2}{2m^2}}, $$ which you could apply Stirling's formula to.

$\endgroup$
2
  • $\begingroup$ By the way, how can we show that for every $m$, the set of such matrices is non-empty. The assymptotic expression above does not say anything about the existence for a particular $m$. $\endgroup$ Dec 23, 2013 at 21:12
  • 1
    $\begingroup$ The expression holds for all $m$ as $m\to\infty$ and so proves the existence. To see there is at least one: put $m$ ones in the first row in any pattern then rotate left by one position for each succeeding row. $\endgroup$ Dec 23, 2013 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.