login
A215977
Number T(n,k) of simple unlabeled graphs on n nodes with exactly k connected components that are trees or cycles; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
13
1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 3, 3, 1, 1, 0, 4, 5, 3, 1, 1, 0, 7, 10, 6, 3, 1, 1, 0, 12, 17, 12, 6, 3, 1, 1, 0, 24, 33, 23, 13, 6, 3, 1, 1, 0, 48, 62, 47, 25, 13, 6, 3, 1, 1, 0, 107, 127, 92, 53, 26, 13, 6, 3, 1, 1, 0, 236, 267, 189, 106, 55, 26, 13, 6, 3, 1, 1
OFFSET
0,8
LINKS
EXAMPLE
T(4,1) = 3: .o-o. .o-o. .o-o.
.| |. .| . .|\ .
.o-o. .o-o. .o o.
.
T(4,2) = 3: .o-o. .o-o. .o-o.
.|/ . .| . . .
.o o. .o o. .o-o.
.
T(5,1) = 4: .o-o-o. .o-o-o. .o-o-o. .o-o-o.
.| / . .| . .| | . . /| .
.o-o . .o-o . .o o . .o o .
.
T(5,2) = 5: .o-o o. .o-o o. .o-o o. .o o-o. .o o-o.
.| | . .| . .|\ . .|\ . .| .
.o-o . .o-o . .o o . .o-o . .o-o .
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 1, 1;
0, 3, 3, 1, 1;
0, 4, 5, 3, 1, 1;
0, 7, 10, 6, 3, 1, 1;
0, 12, 17, 12, 6, 3, 1, 1;
...
MATHEMATICA
b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)];
g[n_] := g[n] = If[n>2, 1, 0]+b[n]-(Sum [b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2;
p[n_, i_, t_] := p[n, i, t] = If[n<t, 0, If[n == t, 1, If[Min[i, t]<1, 0, Sum[Binomial[g[i]+j-1, j]*p[n-i*j, i-1, t-j], {j, 0, Min[n/i, t]}]]]];
T[n_, k_] := p[n, n, k] // FullSimplify;
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 04 2014, after Alois P. Heinz *)
PROG
(Python)
from sympy.core.cache import cacheit
from sympy import binomial, divisors
@cacheit
def b(n): return n if n<2 else sum([sum([d*b(d) for d in divisors(j)])*b(n - j) for j in range(1, n)])//(n - 1)
@cacheit
def g(n): return (1 if n>2 else 0) + b(n) - (sum(b(k)*b(n - k) for k in range(n + 1)) - (b(n//2) if n%2==0 else 0))//2
@cacheit
def p(n, i, t): return 0 if n<t else 1 if n==t else 0 if min(i, t)<1 else sum(binomial(g(i) + j - 1, j)*p(n - i*j, i - 1, t - j) for j in range(min(n//i, t) + 1))
def T(n, k): return p(n, n, k)
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 07 2017
CROSSREFS
Row sums give: A215978.
Limiting sequence of reversed rows gives: A215979.
The labeled version of this triangle is A215861.
Sequence in context: A085815 A088234 A228717 * A357646 A185813 A300756
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Aug 29 2012
STATUS
approved