login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)