A217201 Number of simple unlabeled graphs with n nodes of 2 colors whose components are cycles.

1, 0, 0, 4, 6, 8, 23, 42, 83, 166, 324, 622, 1236, 2366, 4595, 8900, 17225, 33212, 64376, 124360, 240819, 466284, 904149, 1753782, 3407225, 6623274, 12892131, 25116456, 48987833, 95633480, 186891367, 365549578, 715661254, 1402246154, 2749778317, 5396266284

Offset

0,4

Links

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

Formula

EULER transform of 0,0,4,6,8,13,30,... A000029.

Maple

with (numtheory):
b:= n-> `if`(n<3, 0, add(phi(d)*2^(n/d)/(2*n), d=divisors(n))+
    `if`(irem(n, 2)=1, 2^((n-1)/2), 2^(n/2-1)+2^(n/2-2))):
a:= proc(n) option remember; local d, j; `if`(n=0, 1,
      add(add(d*b(d), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 27 2012

Mathematica

Needs["Combinatorica`"]
a=Expand[Table[nn=n; CycleIndex[DihedralGroup[nn], s]/.Table[s[i]->2, {i, 1, nn}], {n, 1, 30}]];
nn=30; p=Product[1/(1- x^i)^a[[i]], {i, 3, nn}]; CoefficientList[Series[p, {x, 0, nn}], x]
(* Second program: *)
b[n_] := If[n < 3, 0, Sum[EulerPhi[d]*2^(n/d)/(2*n), {d, Divisors[n]}] +  If[Mod[n, 2] == 1, 2^((n - 1)/2), 2^(n/2 - 1) + 2^(n/2 - 2)]];
a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d*b[d], {d, Divisors[j]}]*a[n - j], {j, 1, n}]/n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 05 2017, after Alois P. Heinz *)

Crossrefs

Cf. A217194, A217093, A005380.

Sequence in context: A019196 A086561 A083790 * A074125 A063719 A272862

Adjacent sequences: A217198 A217199 A217200 * A217202 A217203 A217204

Keyword

nonn

Author

Geoffrey Critzer, Sep 27 2012

Status

approved