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.

1, 1, 2, 8, 45, 338, 3304, 40485, 602075, 10576466, 214622874, 4941785261, 127282939615, 3625467047196, 113140481638088, 3838679644895477, 140681280613912089, 5538276165405744140, 233086092164091031114, 10443453353262112373541, 496313160155209940833001

Offset

0,3

Links

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

Index entries for sequences related to trees

Formula

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

a(n) ~ c * n^(n-2), where c = 1.66789780037... . - Vaclav Kotesovec, Sep 08 2014

Example

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):
.1.2. .1-2. .1.2. .1.2. .1-2. .1.2. .1-2. .1-2.
..... ..... ../.. .|... ../.. .|/.. .|... .|/..
.3... .3... .3... .3... .3... .3... .3... .3...

Maple

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:
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:
T:= proc(n, k) f(n, k)+add(binomial(n, j)*f(n-j, k-j)*c(j, j), j=3..k) end:
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..25);

Mathematica

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 *)

Prog

(Python)
from sympy.core.cache import cacheit
from sympy import binomial, prod
@cacheit
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))
@cacheit
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
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))
def a(n): return sum(T(n, k) for k in range(n + 1))
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 07 2017

Crossrefs

Row sums of triangles A144163, A215861.

The unlabeled version is A215978.

Cf. A138464, A144161, A007318, A000142.

Sequence in context: A358436 A009345 A084553 * A003091 A119501 A183277

Adjacent sequences: A144161 A144162 A144163 * A144165 A144166 A144167

Keyword

nonn

Author

Alois P. Heinz, Sep 12 2008

Status

approved