A215983 Number of simple unlabeled graphs on n nodes with exactly 3 connected components that are trees or cycles.

1, 1, 3, 6, 12, 23, 47, 92, 189, 401, 869, 1949, 4475, 10520, 25183, 61366, 151555, 379164, 958555, 2446746, 6296819, 16326996, 42613240, 111889355, 295372835, 783598713, 2088175182, 5587741350, 15009229137, 40458659246, 109416872688, 296810505298

Offset

3,3

Links

Alois P. Heinz, Table of n, a(n) for n = 3..650

Formula

a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 0.13932434077355395... . - Vaclav Kotesovec, Sep 07 2014

Example

a(5) = 3: .o o-o.  .o o-o.  .o o o.
          .  |/ .  .  |  .  .| |  .
          .o o  .  .o o  .  .o o  .

Maple

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
    end:
g:= proc(n) option remember; local k; `if`(n>2, 1, 0)+ b(n)-
      (add(b(k)*b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2
    end:
p:= proc(n, i, t) option remember; `if`(n<t, 0, `if`(n=t, 1,
      `if`(min(i, t)<1, 0, add(binomial(g(i)+j-1, j)*
       p(n-i*j, i-1, t-j), j=0..min(n/i, t)))))
    end:
a:= n-> p(n, n, 3):
seq(a(n), n=3..40);

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]}]]]];
a[n_] := p[n, n, 3];
a /@ Range[3, 40] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

Crossrefs

Column k=3 of A215977.

The labeled version is A215853.

Sequence in context: A024505 A005256 A097979 * A339107 A319445 A316318

Adjacent sequences: A215980 A215981 A215982 * A215984 A215985 A215986

Keyword

nonn

Author

Alois P. Heinz, Aug 29 2012

Status

approved