cp's OEIS Frontend

A144164 Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163, A215861.

%I A144164 #32 Jun 09 2020 15:00:06
%S A144164 1,1,2,8,45,338,3304,40485,602075,10576466,214622874,4941785261,
%T A144164 127282939615,3625467047196,113140481638088,3838679644895477,
%U A144164 140681280613912089,5538276165405744140,233086092164091031114,10443453353262112373541,496313160155209940833001
%N A144164 Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163, A215861.
%H A144164 Alois P. Heinz, <a href="/A144164/b144164.txt">Table of n, a(n) for n = 0..140</a>
%H A144164 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A144164 a(n) = Sum_{k=0..n} A144163(n,k).
%F A144164 a(n) ~ c * n^(n-2), where c = 1.66789780037... . - _Vaclav Kotesovec_, Sep 08 2014
%e A144164 a(3) = 8, because there are 8 simple graphs on 3 labeled nodes, where each maximally connected subgraph is either a tree or a cycle, with edge-counts 0(1), 1(3), 2(3), 3(1):
%e A144164 .1.2. .1-2. .1.2. .1.2. .1-2. .1.2. .1-2. .1-2.
%e A144164 ..... ..... ../.. .|... ../.. .|/.. .|... .|/..
%e A144164 .3... .3... .3... .3... .3... .3... .3... .3...
%p A144164 f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
%p A144164 c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n<k then 0 else c(n-1,k) +add(mul(n-i, i=1..j) *c(n-1-j, k-j-1), j=2..k)/2 fi end:
%p A144164 T:= proc(n,k) f(n,k)+add(binomial(n,j)*f(n-j,k-j)*c(j,j), j=3..k) end:
%p A144164 a:= n-> add(T(n,k), k=0..n):
%p A144164 seq(a(n), n=0..25);
%t A144164 f[n_, k_] := f[n, k] = Module[{j}, Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]]; c[n_, k_] := c[n, k] = Module[{i, j}, If[k == 0, 1, If[k<0 || n<k, 0, c[n-1, k]+Sum[Product[n-i, {i, 1, j}]*c[n-1-j, k-j-1], {j, 2,k}]/2]]]; T[n_, k_] := f[n, k]+Sum[Binomial[n, j]*f[n-j, k-j]*c[j, j], {j, 3, k}]; a[n_] := Sum[T[n, k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Mar 05 2014, after _Alois P. Heinz_ *)
%o A144164 (Python)
%o A144164 from sympy.core.cache import cacheit
%o A144164 from sympy import binomial, prod
%o A144164 @cacheit
%o A144164 def f(n, k): return 1 if k==0 else 0 if k<0 or n<=k else n**(n - 2) if k == n - 1 else sum(binomial(n - 1, j)*f(j + 1, j)*f(n - 1 - j, k - j) for j in range(k + 1))
%o A144164 @cacheit
%o A144164 def c(n, k): return 1 if k==0 else 0 if k<0 or n<k else c(n - 1, k) + sum(prod(n - i for i in range(1, j + 1)) * c(n - 1 - j, k - j - 1) for j in range(2, k + 1))//2
%o A144164 def T(n, k): return f(n, k) + sum(binomial(n, j)*f(n - j, k - j)*c(j, j) for j in range(3, k + 1))
%o A144164 def a(n): return sum(T(n, k) for k in range(n + 1))
%o A144164 print([a(n) for n in range(31)]) # _Indranil Ghosh_, Aug 07 2017
%Y A144164 Row sums of triangles A144163, A215861.
%Y A144164 The unlabeled version is A215978.
%Y A144164 Cf. A138464, A144161, A007318, A000142.
%K A144164 nonn
%O A144164 0,3
%A A144164 _Alois P. Heinz_, Sep 12 2008