A058528 - OEIS

%I #33 Jun 21 2022 19:59:44

%S 1,0,0,0,1,120,67950,68938800,116963796250,315031400802720,

%T 1289144584143523800,7722015017013984456000,

%U 65599839591251908982712750,769237071909157579108571190000,12163525741347497524178307740904300

%N Number of n X n (0,1) matrices with all column and row sums equal to 4.

%C Further terms generated by a Mathematica program written by Gordon G. Cash, who thanks B. R. Perez-Salvador, Universidad Autonoma Metropolitana Unidad Iztapalapa, Mexico, for providing the algorithm on which this program was based.

%C Also number of ways to arrange 4n rooks on an n X n chessboard, with no more than 4 rooks in each row and column. - _Vaclav Kotesovec_, Aug 04 2013

%C Generally (Canfield + McKay, 2004), a(n) ~ exp(-1/2) * binomial(n,s)^(2*n) / binomial(n^2,s*n), or a(n) ~ sqrt(2*Pi) * exp(-n*s-1/2*(s-1)^2) * (n*s)^(n*s+1/2) * (s!)^(-2*n). - _Vaclav Kotesovec_, Aug 04 2013

%D B. R. Perez-Salvador, S. de los Cobos Silva, M. A. Gutierrez-Andrade and A. Torres-Chazaro, A Reduced Formula for Precise Numbers of (0,1) Matrices in a(R,S), Disc. Math., 2002, 256, 361-372.

%H Vaclav Kotesovec, <a href="/A058528/b058528.txt">Table of n, a(n) for n = 0..150</a>, [Computed with Maple program by Doron Zeilberger, see link below. This replaces an earlier b-file computed by Vladeta Jovovic (and corrected terms 26-31).]

%H E. R. Canfield and B. D. McKay, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r29">Asymptotic enumeration of dense 0-1 matrices with equal row and column sums</a>

%H Shalosh B. Ekhad and Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bipartite.html">In How Many Ways Can n (Straight) Men and n (Straight) Women Get Married, if Each Person Has Exactly k Spouses</a>, Maple package Bipartite; <a href="/A058528/a058528.pdf">Local copy</a> [Pdf file only, no active links]

%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/semiregular.html">0-1 matrices with constant row and column sums</a>

%H M. L. Stein and P. R. Stein, <a href="/A001496/a001496.pdf">Enumeration of Stochastic Matrices with Integer Elements</a>, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F a(n) = 24^{-n} sum_{alpha +beta + gamma + mu + u =n}frac{3^{ gamma }(-6)^{beta +u }8^{ mu }(n!)^{2}(4alpha +2 gamma + mu )!(beta +2 gamma )!}{alpha!beta! gamma! mu!u!} sum_{i=0}^{ floor (beta +2 gamma )/2 }frac{1}{24^{alpha - gamma +i}2^{beta +2 gamma -i}i!(beta +2 gamma -2i)!(alpha - gamma +i)!} - _Shanzhen Gao_, Nov 07 2007

%F From _Vaclav Kotesovec_, Aug 04 2013: (Start)

%F a(n) ~ exp(-1/2)*C(n,4)^(2*n)/C(n^2,4*n), (Canfield + McKay, 2004).

%F a(n) ~ sqrt(Pi)*2^(2*n+3/2)*9^(-n)*exp(-4*n-9/2)*n^(4*n+1/2).

%F (End)

%e a(4) = 1 because there is only one possible 4 X 4 (0,1) matrix with all row and column sums equal to 4, the matrix of all 1's. a(5) = 120 = 5! because there are 5X4X3X2X1 ways of placing a zero in each successive column (row) so that it is not in the same row (column) as any previously placed.

%Y Column 4 of A008300. Row sums of A284991.

%K nonn

%O 0,6

%A _David desJardins_, Dec 22 2000

%E More terms from Gordon G. Cash (cash.gordon(AT)epa.gov), Oct 22 2002

%E More terms from _Vladeta Jovovic_, Nov 12 2006