login
A084486
Number of 4 X n 0-1 matrices which have n+3 1's and have no zero rows or zero columns.
1
1, 32, 522, 5776, 50600, 380424, 2570932, 16073600, 94748400, 533515240, 2896652396, 15268777440, 78544641448, 395875164104, 1960998472260, 9570684204544, 46112171619296, 219682468794600, 1036237335593500
OFFSET
1,2
COMMENTS
This is the number of spanning subgraphs of the complete bipartite graph K(4,n) which have n+3 edges and no isolated vertices. If the subgraphs are also connected then they are spanning trees. The number of spanning trees in K(m,n) is known. See A001787.
LINKS
M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550, 2013. - From N. J. A. Sloane, Feb 13 2013
FORMULA
n/48*((27*4^n-32*3^n+6*2^n)*n^2+(-9*4^n+32*3^n-18*2^n)*n+(-6*4^n+12*2^n)). - Vladeta Jovovic, May 28 2003
G.f.: x * (1 -4*x -40*x^2 +44*x^3 +2885*x^4 -19624*x^5 +59014*x^6 -97728*x^7 +98064*x^8 -67200*x^9 +28800*x^10) / ((3*x-1)^4*(2*x-1)^4*(4*x-1)^4). - Alois P. Heinz, Sep 24 2012
MAPLE
with(LinearAlgebra): num1s := (M, m, n)->add(ListTools[Flatten](convert(M, listlist))[j], j=1..m*n): binrows := n->[seq(convert(i+2^n, base, 2)[1..n], i=1..2^n-1)]; a := proc(n) local A, L, i, j, k, el, S, M: S := 0: L := binrows(n): for i from 1 to 2^n-1 do for j from 1 to 2^n-1 do for k from 1 to 2^n-1 do for el from 1 to 2^n-1 do A := Matrix([L[i], L[j], L[k], L[el]]); if num1s(A, 4, n)=n+3 and (not has(Matrix([1, 1, 1, 1]).A, 0)) then S := S+1; end if; od; od; od; od; S; end proc: seq (a(n), n=1..2);
MATHEMATICA
a[n_] := n/48*((27*4^n - 32*3^n + 6*2^n)*n^2 + (-9*4^n + 32*3^n - 18*2^n)*n + (-6*4^n + 12*2^n));
Array[a, 20] (* Jean-François Alcover, Nov 10 2017, after Vladeta Jovovic *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
W. Edwin Clark, May 27 2003
EXTENSIONS
Comment corrected by W. Edwin Clark, Sep 24 2012
STATUS
approved