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

Author

Alois P. Heinz, Sep 12 2008

Keywords

• nonn

Examples

			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...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..140
• Index entries for sequences related to trees

Crossrefs

Row sums of triangles A144163, A215861.

The unlabeled version is A215978.

Cf. A138464, A144161, A007318, A000142.

Programs

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 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 || nJean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

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 nIndranil Ghosh, Aug 07 2017

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