|
%I #25 Jan 24 2018 01:19:18
%S 1,12,90,522,2595,11673,49014,195828,753813,2819475,10308144,36998118,
%T 130786695,456452493,1575799290,5389290792,18281487081,61569776727,
%U 206040460212,685584843450,2269566343611,7478425876977,24538396875870,80206515476892,261239771497725
%N Number of 3 X n 0-1 matrices which have n+2 1's and have no zero rows or zero columns.
%C 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 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 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 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (15,-93,305,-558,540,-216)
%F a(n) = n*(4*(3*n-1)*3^n-9*(n-1)*2^n)/24. - _Vladeta Jovovic_, May 28 2003
%F 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 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 a[n_] := n*(4*(3*n - 1)*3^n - 9*(n - 1)*2^n)/24;
%t Array[a, 25] (* _Jean-François Alcover_, Nov 10 2017, after _Vladeta Jovovic_ *)
%Y Cf. A001787.
%Y Cf. A084486, A055602, A055603.
%K nonn,easy
%O 1,2
%A _W. Edwin Clark_, May 27 2003
%E Comment corrected by _W. Edwin Clark_, Sep 24 2012
|
