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

%I #22 Oct 04 2017 08:58:08

%S 1,1,2,3,6,9,15,22,35,51,77,110,162,228,326,454,637,875,1208,1641,

%T 2235,3006,4044,5388,7177,9481,12510,16399,21463,27932,36287,46911,

%U 60531,77776,99733,127415,162457,206444,261821,331063,417801,525828,660536,827684

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

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

%C 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

%H Alois P. Heinz, <a href="/A217067/b217067.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

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

%F EULER transform of 1, 1, 1, 2, 2, 2, ... .

%p 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

%t 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]

%o (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

%Y Cf. A000715.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Sep 26 2012