cp's OEIS Frontend

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

%I A215978 #31 Apr 26 2021 08:52:45
%S A215978 1,1,2,4,8,14,28,52,104,206,429,903,1982,4430,10206,23966,57522,
%T A215978 140236,347302,870682,2207819,5651437,14590703,37948338,99358533,
%U A215978 261684141,692906575,1843601797,4926919859,13220064562,35604359531,96218568474,260850911485
%N A215978 Number of simple unlabeled graphs on n nodes with connected components that are trees or cycles.
%H A215978 Alois P. Heinz, <a href="/A215978/b215978.txt">Table of n, a(n) for n = 0..1000</a>
%F A215978 a(n) = Sum_{k=0..n} A215977(n,k).
%F A215978 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
%e A215978 a(4) = 8:
%e A215978 .o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o-o.  .o o.
%e A215978 .| |.  .|  .  .|\ .  .|/ .  .|  .  .   .  .   .  .   .
%e A215978 .o-o.  .o-o.  .o o.  .o o.  .o o.  .o-o.  .o o.  .o o.
%p A215978 with(numtheory):
%p A215978 b:= proc(n) option remember; local d, j; `if`(n<=1, n,
%p A215978       (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
%p A215978     end:
%p A215978 g:= proc(n) option remember; local k; `if`(n>2, 1, 0)+ b(n)-
%p A215978       (add(b(k)*b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2
%p A215978     end:
%p A215978 p:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A215978       add(binomial(g(i)+j-1,j)*p(n-i*j, i-1), j=0..n/i)))
%p A215978     end:
%p A215978 a:= n-> p(n, n):
%p A215978 seq(a(n), n=0..40);
%t A215978 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)];
%t A215978 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;
%t A215978 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}]]];
%t A215978 a[n_] := p[n, n];
%t A215978 Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Mar 21 2017, translated from Maple *)
%o A215978 (Python)
%o A215978 from sympy.core.cache import cacheit
%o A215978 from sympy import binomial, divisors
%o A215978 @cacheit
%o A215978 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)
%o A215978 @cacheit
%o A215978 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
%o A215978 @cacheit
%o A215978 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 range(n//i + 1)])
%o A215978 def a(n): return p(n, n)
%o A215978 print([a(n) for n in range(41)]) # _Indranil Ghosh_, Aug 07 2017
%Y A215978 Row sum of A215977.
%Y A215978 The labeled version is A144164. The inverse Euler transform is A215981.
%K A215978 nonn
%O A215978 0,3
%A A215978 _Alois P. Heinz_, Aug 29 2012