OFFSET
0,4
COMMENTS
The black nodes form a maximal independent vertex set (or a set that is both independent and dominating). For n > 0, a(n) is then the total number of indistinguishable maximal 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, Maximal Independent Vertex Set
EXAMPLE
a(2) = 1 because exactly one node must be colored black.
a(3) = 2 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 both of the ends must be colored black. In total there are 2 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 3, 3 and 2 solutions, so a(5) = 3 + 3 + 2 = 8.
PROG
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=v=w=[]); for(n=1, n, my(t1=EulerT(v), t2=EulerT(u+v)); u=concat([1], EulerT(v+w)); v=concat([0], t2-t1); w=concat([1], t1)); my(g=x*Ser(u+v), gu=x*Ser(u), gw=x*Ser(w)); Vec(1 + g + (subst(g, x, x^2) - subst(gu, x, x^2) - g^2 - 2*gu*gw + gu^2)/2)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 20 2020
STATUS
approved