cp's OEIS Frontend

A144163 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 is either a tree or a cycle.

%I A144163 #25 Sep 10 2018 10:12:54
%S A144163 1,1,0,1,1,0,1,3,3,1,1,6,15,20,3,1,10,45,120,150,12,1,15,105,455,1185,
%T A144163 1473,70,1,21,210,1330,5565,14469,18424,465,1,28,378,3276,19635,81060,
%U A144163 213990,280200,3507,1,36,630,7140,57393,334656,1385076,3732300,5029218,30016
%N A144163 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 is either a tree or a cycle.
%H A144163 Alois P. Heinz, <a href="/A144163/b144163.txt">Rows n = 0..140, flattened</a>
%H A144163 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A144163 T(n,k) = A138464(n,k) + Sum_{j=3..k} C(n,j) A138464(n-j,k-j) A144161 (j,j).
%e A144163 T(4,3) = 20, because there are 20 simple graphs on 4 labeled nodes with 3 edges, where each maximally connected subgraph is either a tree or a cycle, 16 of these graphs consist of a single tree with 4 nodes and 4 consist of a cycle with 3 and a tree with 1 node:
%e A144163   .1-2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .1-2. .1.2.
%e A144163   .|\.. ../|. ..\|. .|/.. .|... ...|. ../.. ..\.. .|.|. .|.|.
%e A144163   .4.3. .4.3. .4-3. .4-3. .4-3. .4-3. .4-3. .4-3. .4.3. .4-3.
%e A144163   .
%e A144163   .1.2. .1.2. .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1-2.
%e A144163   .|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
%e A144163   .4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
%e A144163 Triangle begins:
%e A144163   1;
%e A144163   1,  0;
%e A144163   1,  1,  0;
%e A144163   1,  3,  3,   1;
%e A144163   1,  6, 15,  20,   3;
%e A144163   1, 10, 45, 120, 150, 12;
%p A144163 f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
%p A144163 c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n<k then 0 else c(n-1,k) +add(mul(n-i, i=1..j) *c(n-1-j, k-j-1), j=2..k)/2 fi end:
%p A144163 T:= proc(n,k) f(n,k)+add(binomial(n,j)*f(n-j,k-j)*c(j,j), j=3..k) end:
%p A144163 seq(seq(T(n,k), k=0..n), n=0..12);
%t A144163 f[n_, k_] := f[n, k] = Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]; c[n_, k_] := c[n, k] = Which[k == 0, 1 , k<0 || n<k, 0, True, c[n-1, k] + Sum[Product[n-i, {i, 1, j}]*c[n-1-j, k-j-1], {j, 2, k}]/2]; T[n_, k_] := f[n, k] + Sum[Binomial[n, j]*f[n-j, k-j]*c[j, j], {j, 3, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Jan 21 2014, translated from _Alois P. Heinz_'s Maple code *)
%Y A144163 Columns k=0-3 give: A000012, A000217, A050534, A093566.
%Y A144163 Main diagonal gives A001205.
%Y A144163 Row sums give A144164.
%Y A144163 Cf. A138464, A144161, A007318, A000142.
%K A144163 nonn,tabl
%O A144163 0,8
%A A144163 _Alois P. Heinz_, Sep 12 2008