A001501 Number of n X n 0-1 matrices with all column and row sums equal to 3.
1, 0, 0, 1, 24, 2040, 297200, 68938800, 24046189440, 12025780892160, 8302816499443200, 7673688777463632000, 9254768770160124288000, 14255616537578735986867200, 27537152449960680597739468800, 65662040698002721810659005184000
Offset: 0
Examples
G.f. = 1 + x^3 + 24*x^4 + 2040*x^5 + 297200*x^6 + 68938800*x^7 + ...
References
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,3).
- R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986; see Example 1.1.3, page 2, f(n).
- 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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..185 (first 51 terms from T. D. Noe)
- R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
- 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]
- Bo-Ying Wang, Fuzhen Zhang, On the precise number of (0,1)-matrices in A(R,S), Discrete Math. 187 (1998), no. 1-3, 211--220. MR1630720 (99f:05010). - From _N. J. A. Sloane_, Jun 07 2012
- Index entries for sequences related to binary matrices
Programs
-
Maple
a:= n-> n!^2/6^n *add(add((-1)^b *2^a *3^b *(3*n-3*a-2*b)!/ (a! *b! *(n-a-b)!^2 *6^(n-a-b)), b=0..n-a), a=0..n): seq(a(n), n=0..20); # Alois P. Heinz, Mar 20 2011 # second Maple program: a:= proc(n) option remember; `if`(n<4, (n-1)*(n-2)/2, n*(n-1)*(9*(3*n^2-5*n+4)*a(n-1)+(3*n-6)*(3*n+1)* (n-1)*a(n-2)+(9*n^2-30*n+13)*(n-1)*(n-2)^2*a(n-3) -(3*n-2)*(n-1)*(n-2)^2*(n-3)^2*a(n-4))/(36*n-60)) end: seq(a(n), n=0..20); # Alois P. Heinz, Mar 13 2017 -
Mathematica
Table[6^(-n) Total[Map[(-1)^#[[2]] n!^2 (#[[2]] + 3 #[[3]])! 2^#[[1]] 3^#[[2]]/(#[[1]]! #[[2]]! #[[3]]!^2 6^#[[3]]) &, Compositions[n, 3]]], {n, 0, 20}] (* Geoffrey Critzer, Mar 19 2011 *) a[n_] := n!^2*Sum[2^(2k-n)*3^(k-n)*(3(n-k))!*HypergeometricPFQ[{k-n, k-n}, {3(k-n)/2, 1/2 + 3(k-n)/2}, -9/2]/(k! (n-k )!^2), {k, 0, n}]/6^n; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 07 2018 *) -
PARI
{a(n) = local(k); if( n<0, 0, n!^2 * sum(j=0, n, sum(i=0, n-j, if(1, k=n-i-j; (j + 3*k)! / (3^i * 36^k * i! * k!^2))) / (j! * (-2)^j)))}; /* Michael Somos, May 28 2002 */
Formula
a(n) = n!^2/6^n * Sum_{a=0..n} Sum_{b=0..n-a} (-1)^b * 2^a * 3^b * (3*n-3*a-2*b)! / (a! * b! * (n-a-b)!^2 * 6^(n-a-b)). - Shanzhen Gao, Feb 19 2010
D-finite with recurrence: 12*(3*n-5)*a(n) = 9*n*(3*n^2-5*n+4)*(n-1)*a(n-1) + 3*(n-2)*n*(3*n+1)*(n-1)^2*a(n-2) + (n-2)^2*n*(9*n^2-30*n+13)*(n-1)^2*a(n-3) - (n-3)^2*(n-2)^2*n*(3*n-2)*(n-1)^2*a(n-4). - Vaclav Kotesovec, Aug 03 2013
a(n) ~ sqrt(6*Pi) * (3/4)^n * n^(3*n+1/2) / exp(3*n+2). - Vaclav Kotesovec, Aug 03 2013
Extensions
Additional comments from Michael Somos, May 28 2002
Comments