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.
$\begingroup$
$\endgroup$
6
asked Dec 8, 2013 at 23:21
Mohammad Farajzadeh-TehraniMohammad Farajzadeh-Tehrani
6,9401 gold badge34 silver badges69 bronze badges
-
$\begingroup$ It likely is well known, but I don't know it. I would look at OEIS and works of Ryser. $\endgroup$– The Masked AvengerCommented Dec 8, 2013 at 23:44
-
$\begingroup$ Could not find any sequence in OEIS. $\endgroup$– Mohammad Farajzadeh-TehraniCommented 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$– David E SpeyerCommented 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$– Brendan McKayCommented 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$– David E SpeyerCommented Dec 9, 2013 at 1:15
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Dec 9, 2013 at 1:04
-
$\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$ Commented 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$ Commented Dec 23, 2013 at 21:29