login
A339837
Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.
5
1, 1, 1, 2, 4, 8, 18, 44, 111, 296, 819, 2332, 6808, 20302, 61559, 189413, 590091, 1858187, 5906637, 18932016, 61130413, 198697205, 649706622, 2135958254, 7056831766, 23420011178, 78048740454, 261099605923, 876564670090, 2952491169904, 9975191222798
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
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
Cf. A038056 (bicolored trees), A339830 (independent only), A339834 (dominating only), A339838 (rooted), A340021 (graphs).
Sequence in context: A233139 A308246 A114203 * A100132 A176720 A088457
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 20 2020
STATUS
approved