

A058528


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


6



1, 0, 0, 0, 1, 120, 67950, 68938800, 116963796250, 315031400802720, 1289144584143523800, 7722015017013984456000, 65599839591251908982712750, 769237071909157579108571190000, 12163525741347497524178307740904300
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Further terms generated by a Mathematica program written by Gordon G. Cash, who thanks B. R. PerezSalvador, Universidad Autonoma Metropolitana Unidad Iztapalapa, Mexico, for providing the algorithm on which this program was based.
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
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*s1/2*(s1)^2) * (n*s)^(n*s+1/2) * (s!)^(2*n).  Vaclav Kotesovec, Aug 04 2013


REFERENCES

B. R. PerezSalvador, S. de los Cobos Silva, M. A. GutierrezAndrade and A. TorresChazaro, A Reduced Formula for Precise Numbers of (0,1) Matrices in a(R,S), Disc. Math., 2002, 256, 361372.


LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..150, [Computed with Maple program by Doron Zeilberger, see link below. This replaces an earlier bfile computed by Vladeta Jovovic (and corrected terms 2631).]
E. R. Canfield and B. D. McKay, Asymptotic enumeration of dense 01 matrices with equal row and column sums
Shalosh B. Ekhad and Doron Zeilberger, In How Many Ways Can n (Straight) Men and n (Straight) Women Get Married, if Each Person Has Exactly k Spouses, Maple package Bipartite.
B. D. McKay, 01 matrices with constant row and column sums
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]
Index entries for sequences related to binary matrices


FORMULA

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
From Vaclav Kotesovec, Aug 04 2013: (Start)
a(n) ~ exp(1/2)*C(n,4)^(2*n)/C(n^2,4*n), (Canfield + McKay, 2004).
a(n) ~ sqrt(Pi)*2^(2*n+3/2)*9^(n)*exp(4*n9/2)*n^(4*n+1/2).
(End)


EXAMPLE

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.


CROSSREFS

Column 4 of A008300. Row sums of A284991.
Sequence in context: A074653 A065961 A333043 * A001421 A107446 A184887
Adjacent sequences: A058525 A058526 A058527 * A058529 A058530 A058531


KEYWORD

nonn


AUTHOR

David desJardins (david(AT)desjardins.org), Dec 22 2000


EXTENSIONS

More terms from Gordon G. Cash (cash.gordon(AT)epa.gov), Oct 22 2002
More terms from Vladeta Jovovic, Nov 12 2006


STATUS

approved



