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

1, 1, 3, 5, 10, 17, 33, 62, 127, 267, 587, 1326, 3085, 7326, 17731, 43585, 108563, 273544, 696113, 1787042, 4623125, 12043071, 31565842, 83200763, 220413272, 586625403, 1567930743, 4207181144, 11329835687, 30613313339, 82975300030, 225552632043, 614787508640

Offset

2,3

Links

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

Formula

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

Example

a(5) = 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  .

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, 2):
seq(a(n), n=2..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, 2] // FullSimplify; Table[a[n], {n, 2, 40}] // Flatten (* Jean-François Alcover, Dec 04 2014, translated from Maple *)

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 a(n): return p(n, n, 2)
print([a(n) for n in range(2, 41)]) # Indranil Ghosh, Aug 07 2017

Crossrefs

Column k=2 of A215977.

The labeled version is A215852.

Sequence in context: A054166 A265317 A054157 * A026621 A366108 A096395

Adjacent sequences: A215979 A215980 A215981 * A215983 A215984 A215985

Keyword

nonn

Author

Alois P. Heinz, Aug 29 2012

Status

approved