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

Author

Geoffrey Critzer, Sep 27 2012

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf.: A217093, A005380.

Programs

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]

Formula

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

EULER transform of A005418.