cp's OEIS Frontend

A144209 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph consists of a single node or has a unique cycle of length 4.

%I A144209 #17 Mar 12 2015 05:06:53
%S A144209 1,1,0,1,0,0,1,0,0,0,1,0,0,0,3,1,0,0,0,15,60,1,0,0,0,45,360,1080,1,0,
%T A144209 0,0,105,1260,7560,20580,1,0,0,0,210,3360,30240,164640,430080,1,0,0,0,
%U A144209 378,7560,90720,740880,3873240,9920232,1,0,0,0,630,15120,226800,2469600,19367460,99406440,252000000
%N A144209 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph consists of a single node or has a unique cycle of length 4.
%H A144209 Alois P. Heinz, <a href="/A144209/b144209.txt">Rows n = 0..140, flattened</a>
%F A144209 T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = 3*C(n-1,3)*n^(n-4) if k=n, else T(n,k) = T(n-1,k) + Sum_{j=3..k-1} C(n-1,j) T(j+1,j+1) T(n-1-j,k-j-1).
%e A144209 T(5,4) = 15 = 5*3, because there are 5 possibilities for a single node and T(4,4) = 3:
%e A144209 .1-2. .1-2. .1.2.
%e A144209 .|.|. ..X.. .|X|.
%e A144209 .3-4. .3-4. .3.4.
%e A144209 Triangle begins:
%e A144209 1;
%e A144209 1, 0;
%e A144209 1, 0, 0;
%e A144209 1, 0, 0, 0;
%e A144209 1, 0, 0, 0,  3;
%e A144209 1, 0, 0, 0, 15, 60;
%p A144209 T:= proc(n,k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then 3*binomial(n-1,3)*n^(n-4) else T(n-1,k) +add(binomial(n-1,j) * T(j+1,j+1) *T(n-1-j,k-j-1), j=3..k-1) fi end: seq(seq(T(n, k), k=0..n), n=0..11);
%t A144209 T[n_, k_] := T[n, k] = Which[k == 0, 1, k < 0 || n < k, 0, k == n, 3*Binomial[n-1, 3]*n^(n-4), True, T[n-1, k] + Sum[Binomial[n-1, j]*T[j+1, j+1]*T[n-1-j, k-j-1], {j, 3, k-1}]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 29 2014, translated from Maple *)
%Y A144209 Columns 0, 1+2+3, 4 give: A000012, A000004, A050534.
%Y A144209 Main diagonal gives A065889.
%Y A144209 Row sums give A144210.
%Y A144209 Cf. A007318.
%K A144209 nonn,tabl
%O A144209 0,15
%A A144209 _Alois P. Heinz_, Sep 14 2008