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.

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

Alois P. Heinz, Rows n = 0..140, flattened

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

Columns k=0-10 give: A000007, A215981, A215982, A215983, A215984, A215985, A215986, A215987, A215988, A215989, A215980.

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

Adjacent sequences: A215974 A215975 A215976 * A215978 A215979 A215980

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 29 2012

Status

approved