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.

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

Author

Andrew Howroyd, Dec 20 2020

Keywords

• nonn

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.

Examples

			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.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Crossrefs

Cf. A038056 (bicolored trees), A339830 (independent only), A339834 (dominating only), A339838 (rooted), A340021 (graphs).

Programs

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)}