login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144210 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 4; also row sums of A144209. 3
1, 1, 1, 1, 4, 76, 1486, 29506, 628531, 14633011, 373486051, 10423892971, 316702467496, 10422938835196, 369779598658786, 14078057663869606, 572776958092098166, 24810200300393961286, 1140218754844983978646 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

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

FORMULA

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

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

EXAMPLE

a(4) = 4, because there are 4 simple graphs on 4 labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length 4:

.1.2. .1-2. .1-2. .1.2.

..... .|.|. ..X.. .|X|.

.3.4. .3-4. .3-4. .3.4.

MAPLE

T:= proc(n, k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then 3*binomial(n-1, 3)*n^(n-4) else T(n-1, k) +add(binomial(n-1, j) * T(j+1, j+1) *T(n-1-j, k-j-1), j=3..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, 3*Binomial[n-1, 3]*n^(n-4), True, T[n-1, k] + Sum[Binomial[n-1, j]*T[j+1, j+1]*T[n-1-j, k-j-1], {j, 3, k-1}]]; a[n_] := Sum[T[n, k], {k, 0, n}]; Table[a[n], {n, 0, 23}] (* Jean-Fran├žois Alcover, Dec 02 2014, translated from Maple *)

CROSSREFS

A column of A144212. Cf. A144209.

Sequence in context: A114453 A093184 A214814 * A220793 A220958 A187542

Adjacent sequences:  A144207 A144208 A144209 * A144211 A144212 A144213

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 14 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 22:20 EDT 2019. Contains 327252 sequences. (Running on oeis4.)