A144208 Number of simple graphs on n labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length 3; also row sums of A144207.

1, 1, 1, 2, 17, 221, 3261, 54801, 1049235, 22695027, 548904831, 14701691121, 432342705351, 13856514927207, 480891887472585, 17971038945463101, 719613541474095591, 30743125693699501431, 1395902175504288127695

Offset

0,4

Links

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

Formula

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

a(n) ~ c * n^(n-1), where c = 0.762590842281789937101466... . - Vaclav Kotesovec, Sep 10 2014

Example

a(3) = 2, because there are 2 simple graphs on 3 labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length 3:
.1.2. .1-2.
..... .|/..
.3... .3...

Maple

T:= proc(n, k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then binomial(n-1, 2) *n^(n-3) else T(n-1, k) +add(binomial(n-1, j) * T(j+1, j+1) *T(n-1-j, k-j-1), j=2..k-1) fi end: a:= n-> add(T(n, k), k=0..n): seq(a(n), n=0..23);

Mathematica

T[n_, k_] := T[n, k] = Which[k == 0, 1, k<0 || n<k, 0, k == n, Binomial[n-1, 2] *n^(n-3), True, T[n-1, k] + Sum[Binomial[n-1, j] * T[j+1, j+1] * T[n-1-j, k-j-1], {j, 2, k-1}]]; a[n_] := Sum[T[n, k], {k, 0, n}]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

Crossrefs

Row sums of triangle A144207. A column of A144212. Cf. A053507, A007318.

Sequence in context: A370289 A004029 A114268 * A183711 A058239 A006227

Adjacent sequences: A144205 A144206 A144207 * A144209 A144210 A144211

Keyword

nonn

Author

Alois P. Heinz, Sep 14 2008

Status

approved