login
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 has at most one cycle.
5

%I #25 Feb 02 2024 19:22:59

%S 1,1,0,1,1,0,1,3,3,1,1,6,15,20,15,1,10,45,120,210,222,1,15,105,455,

%T 1365,2913,3670,1,21,210,1330,5985,20139,49294,68820,1,28,378,3276,

%U 20475,97860,362670,976560,1456875,1,36,630,7140,58905,376236,1914276,7663500,22089870,34506640

%N 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 has at most one cycle.

%H Alois P. Heinz, <a href="/A144228/b144228.txt">Table of n, a(n) for n = 0..140, flattened</a>

%F T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = Sum_{j=0..k} C(n-1,j) (A000272(j+1) T(n-j-1,k-j) + A057500(j+1) T(n-j-1,k-j-1)).

%F E.g.f.: exp(B(x,y)), where B(x,y) = Sum(Sum(A062734(n,k)*y^k*x^n/n!, k=0..n), n=1..infinity) = -1/2*log(1+LambertW(-x*y))+1/2*LambertW(-x*y) -1/4*LambertW(-x*y)^2-1/y *(LambertW(-x*y)+1/2 *LambertW(-x*y)^2). - _Vladeta Jovovic_, Sep 16 2008

%e T(4,4) = 15, because there are 15 simple graphs on 4 labeled nodes with 4 edges where each maximally connected subgraph has at most one cycle:

%e 1-2 1-2 1-2 1-2 1-2 1-2 1 2 1 2 1-2 1 2 1 2 1-2 1-2 1-2 1 2

%e |/| |X |/ |\| X| \| |/| X| /| |\| |X |\ | | X |X|

%e 4 3 4 3 4-3 4 3 4 3 4-3 4-3 4-3 4-3 4-3 4-3 4-3 4-3 4-3 4 3

%e Triangle begins:

%e 1;

%e 1, 0;

%e 1, 1, 0;

%e 1, 3, 3, 1;

%e 1, 6, 15, 20, 15;

%e 1, 10, 45, 120, 210, 222;

%e ...

%p cy:= proc(n) option remember; local t; binomial(n-1, 2) *add((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<k then 0 else add(binomial(n-1, j) *((j+1)^(j-1) *T(n-j-1, k-j) +cy(j+1) *T(n-j-1, k-j-1)), j=0..k) fi end: seq(seq(T(n, k), k=0..n), n=0..11);

%t t[_, 0] = 1; t[n_, k_] /; (k<0 || n<k) = 0; t[n_, k_] := t[n, k] = Sum[Binomial[n-1, j]*(t[n-j-1, k-j]*(j+1)^(j-1) + 1/2*j!*Sum[1/((j+1)^m*(j-m+1)!), {m, 3, j+1}]*t[n-j-1, k-j-1]*(j+1)^(j+1)), {j, 0, k}]; Flatten[Table[t[n, k], {n, 0, 11}, {k, 0, n}]] (* _Jean-François Alcover_, Jan 15 2014, after Maple *)

%Y Columns k=0-3 give: A000012, A000217, A050534, A093566.

%Y Main diagonal gives A137916.

%Y Row sums give: A133686.

%Y T(2n,n) gives A369828.

%Y Cf. A000272, A057500, A007318, A000142, A129271.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Sep 15 2008