0,3

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

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

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

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

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

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

(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

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

Alois P. Heinz, Sep 12 2008

approved