A217067 Number of unlabeled graphs on n nodes whose components are cycles or complete graphs.

1, 1, 2, 3, 6, 9, 15, 22, 35, 51, 77, 110, 162, 228, 326, 454, 637, 875, 1208, 1641, 2235, 3006, 4044, 5388, 7177, 9481, 12510, 16399, 21463, 27932, 36287, 46911, 60531, 77776, 99733, 127415, 162457, 206444, 261821, 331063, 417801, 525828, 660536, 827684

Offset

0,3

Comments

Also number of partitions of n, with one kind of 1, 2 and 3 and two kinds of 4, 5, 6, ... .

Number of n-vertex graphs that do not contain a triangle or claw as induced subgraph (there is one connected triangle-free claw-free graph with 1 to 3 vertices each, and two for n >= 4 vertices (P_n and C_n)). - Falk Hüffner, Jan 11 2016

Links

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

N. J. A. Sloane, Transforms

Formula

G.f.: (1-x)(1-x^2)(1-x^3) Product_{i>=1} 1/(1-x^i)^2.

EULER transform of 1, 1, 1, 2, 2, 2, ... .

Maple

a:= proc(n) a(n):= `if`(n=0, 1, add(add(d*`if`(d<4, 1, 2), d=numtheory[divisors(j)) *a(n-j), j=1..n)/n) end: seq(a(n), n=0..50); # Alois P. Heinz, Sep 26 2012

Mathematica

nn=40; a=x/(1-2x); p=Product[1/(1- x^i)^2, {i, 1, nn}]; CoefficientList[Series[p(1-x)(1-x^2)(1-x^3), {x, 0, nn}], x]

Prog

(PARI) list(lim)=Vec((1-x)*(1-x^2)*(1-x^3)*prod(i=1, lim\=1, 1/(1-x^i)^2, O(x^lim++)+1)) \\ Charles R Greathouse IV, Sep 26 2012

Crossrefs

Cf. A000715.

Sequence in context: A308995 A326470 A326595 * A014214 A094993 A365071

Adjacent sequences: A217064 A217065 A217066 * A217068 A217069 A217070

Keyword

nonn

Author

Geoffrey Critzer, Sep 26 2012

Status

approved