OFFSET
0,2
COMMENTS
The black nodes form an independent vertex set. For n > 0, a(n) is then the total number of indistinguishable independent vertex sets summed over distinct unlabeled trees with n nodes.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
Eric Weisstein's World of Mathematics, Independent Vertex Set
EXAMPLE
a(2) = 2 because at most one node can be colored black.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored black then neither of the ends can be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.
There are 3 trees with 5 nodes:
o o
| |
o---o---o o---o---o---o---o o---o---o
| |
o o
These correspond respectively to 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.
PROG
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=v=[1]); for(n=2, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u+v)); u=t); my(g=x*Ser(u+v), gu=x*Ser(u)); Vec(1 + g + (subst(g, x, x^2) - subst(gu, x, x^2) - g^2 + gu^2)/2)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved