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

1, 0, 0, 0, 1, 120, 67950, 68938800, 116963796250, 315031400802720, 1289144584143523800, 7722015017013984456000, 65599839591251908982712750, 769237071909157579108571190000, 12163525741347497524178307740904300

Offset

0,6

Comments

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.

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*s-1/2*(s-1)^2) * (n*s)^(n*s+1/2) * (s!)^(-2*n). - Vaclav Kotesovec, Aug 04 2013

References

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.

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 b-file computed by Vladeta Jovovic (and corrected terms 26-31).]

E. R. Canfield and B. D. McKay, Asymptotic enumeration of dense 0-1 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; Local copy [Pdf file only, no active links]

B. D. McKay, 0-1 matrices with constant row and column sums

M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, 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*n-9/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: A065961 A364512 A333043 * A001421 A107446 A184887

Adjacent sequences: A058525 A058526 A058527 * A058529 A058530 A058531

Keyword

nonn

Author

David desJardins, 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