cp's OEIS Frontend

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

%I A084485 #25 Jan 24 2018 01:19:18
%S A084485 1,12,90,522,2595,11673,49014,195828,753813,2819475,10308144,36998118,
%T A084485 130786695,456452493,1575799290,5389290792,18281487081,61569776727,
%U A084485 206040460212,685584843450,2269566343611,7478425876977,24538396875870,80206515476892,261239771497725
%N A084485 Number of 3 X n 0-1 matrices which have n+2 1's and have no zero rows or zero columns.
%C A084485 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.
%H A084485 M. Janjic and B. Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv preprint arXiv:1301.4550, 2013. - From N. J. A. Sloane, Feb 13 2013
%H A084485 M. Janjic, B. Petkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html">A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers</a>, J. Int. Seq. 17 (2014) # 14.3.5
%H A084485 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (15,-93,305,-558,540,-216)
%F A084485 a(n) = n*(4*(3*n-1)*3^n-9*(n-1)*2^n)/24. - _Vladeta Jovovic_, May 28 2003
%F A084485 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
%p A084485 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);
%t A084485 a[n_] := n*(4*(3*n - 1)*3^n - 9*(n - 1)*2^n)/24;
%t A084485 Array[a, 25] (* _Jean-François Alcover_, Nov 10 2017, after _Vladeta Jovovic_ *)
%Y A084485 Cf. A001787.
%Y A084485 Cf. A084486, A055602, A055603.
%K A084485 nonn,easy
%O A084485 1,2
%A A084485 _W. Edwin Clark_, May 27 2003
%E A084485 Comment corrected by _W. Edwin Clark_, Sep 24 2012