OFFSET
0,8
LINKS
EXAMPLE
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:
.1-2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .1-2. .1.2.
.|\.. ../|. ..\|. .|/.. .|... ...|. ../.. ..\.. .|.|. .|.|.
.4.3. .4.3. .4-3. .4-3. .4-3. .4-3. .4-3. .4-3. .4.3. .4-3.
.
.1.2. .1.2. .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1-2.
.|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
.4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
Triangle begins:
1;
1, 0;
1, 1, 0;
1, 3, 3, 1;
1, 6, 15, 20, 3;
1, 10, 45, 120, 150, 12;
MAPLE
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:
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:
T:= proc(n, k) f(n, k)+add(binomial(n, j)*f(n-j, k-j)*c(j, j), j=3..k) end:
seq(seq(T(n, k), k=0..n), n=0..12);
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 12 2008
STATUS
approved