A084485 Number of 3 X n 0-1 matrices which have n+2 1's and have no zero rows or zero columns.

1, 12, 90, 522, 2595, 11673, 49014, 195828, 753813, 2819475, 10308144, 36998118, 130786695, 456452493, 1575799290, 5389290792, 18281487081, 61569776727, 206040460212, 685584843450, 2269566343611, 7478425876977, 24538396875870, 80206515476892, 261239771497725

Offset: 1

Author

W. Edwin Clark, May 27 2003

Keywords

• nonn
• easy

Comments

This is the number of spanning subgraphs of the complete bipartite graph K(3,n) with n + 2 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
• M. Janjic, B. Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5
• Index entries for linear recurrences with constant coefficients, signature (15,-93,305,-558,540,-216)

Crossrefs

Cf. A001787.

Cf. A084486, A055602, A055603.

Programs

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, 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 A := Matrix([L[i], L[j], L[k]]); if num1s(A, 3, n)=n+2 and (not has(Matrix([1, 1, 1]).A, 0)) then S := S+1; end if; od; od; od; S; end proc: seq (a(n), n=1..5);

Mathematica

a[n_] := n*(4*(3*n - 1)*3^n - 9*(n - 1)*2^n)/24;
Array[a, 25] (* Jean-François Alcover, Nov 10 2017, after Vladeta Jovovic *)

Formula

a(n) = n*(4*(3*n-1)*3^n-9*(n-1)*2^n)/24. - Vladeta Jovovic, May 28 2003

G.f.: x*(1-3*x+3*x^2-17*x^3+33*x^4)/((3*x-1)^3*(2*x-1)^3). - Alois P. Heinz, Sep 24 2012

Extensions

Comment corrected by W. Edwin Clark, Sep 24 2012