login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215978 Number of simple unlabeled graphs on n nodes with connected components that are trees or cycles. 5
1, 1, 2, 4, 8, 14, 28, 52, 104, 206, 429, 903, 1982, 4430, 10206, 23966, 57522, 140236, 347302, 870682, 2207819, 5651437, 14590703, 37948338, 99358533, 261684141, 692906575, 1843601797, 4926919859, 13220064562, 35604359531, 96218568474, 260850911485 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

a(n) = Sum_{k=0..n} A215977(n,k).

a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.95576528565199497471481752412... is Otter's rooted tree constant, and c = 1.085767435235426664262830616636... . - Vaclav Kotesovec, Mar 22 2017

EXAMPLE

a(4) = 8:

.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 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) option remember; `if`(n=0, 1, `if`(i<1, 0,

      add(binomial(g(i)+j-1, j)*p(n-i*j, i-1), j=0..n/i)))

    end:

a:= n-> p(n, n):

seq(a(n), n=0..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_] := p[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[g[i] + j - 1, j]*p[n - i*j, i - 1], {j, 0, n/i}]]];

a[n_] := p[n, n];

Table[a[n], {n, 0, 40}] (* Jean-Fran├žois Alcover, Mar 21 2017, 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 xrange(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 xrange(n + 1)]) - (b(n/2) if n%2==0 else 0))/2

@cacheit

def p(n, i): return 1 if n==0 else 0 if i<1 else sum([binomial(g(i) + j - 1, j)*p(n - i*j, i - 1) for j in xrange(n/i + 1)])

def a(n): return p(n, n)

print map(a, xrange(41)) # Indranil Ghosh, Aug 07 2017

CROSSREFS

Row sum of A215977.

The labeled version is A144164. The inverse Euler transform is A215981.

Sequence in context: A068912 A164176 A217932 * A018086 A004651 A283835

Adjacent sequences:  A215975 A215976 A215977 * A215979 A215980 A215981

KEYWORD

nonn

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 13:12 EDT 2018. Contains 316263 sequences. (Running on oeis4.)