A217194 Number of unlabeled simple graphs with n nodes of 2 colors whose components are path graphs.

1, 2, 6, 16, 42, 106, 267, 656, 1602, 3868, 9270, 22048, 52140, 122580, 286798, 667944, 1549259, 3579738, 8242638, 18917600, 43286909, 98768820, 224768425, 510235760, 1155553468, 2611251662, 5888421059, 13252176464, 29768501556, 66749440076, 149415504274

Offset

0,2

Comments

Here, a path graph is a connected graph with no cycles such that each node has degree at most two.

Links

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

Formula

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

EULER transform of A005418.

Example

a(3) = 16 because we have:
w w w; w w b; w b b; b b b;
w w-w; w w-b; w b-b; b w-w; b w-b; b b-b;
w-w-w; w-w-b; w-b-w; b-w-b; b-b-w; b-b-b, where the 2 colors are black b and white w.

Maple

with(numtheory):
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*(2^(d-1)+
      2^(floor((d+1)/2)-1)), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 27 2012

Mathematica

nn=30; p=Product[1/(1- x^i)^(2^(i-1)+2^(Floor[(i+1)/2]-1)), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x]

Crossrefs

Cf.: A217093, A005380.

Sequence in context: A143123 A102699 A266124 * A304662 A296625 A156664

Adjacent sequences: A217191 A217192 A217193 * A217195 A217196 A217197

Keyword

nonn

Author

Geoffrey Critzer, Sep 27 2012

Status

approved