The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #11 Jan 09 2021 22:10:29
%S 1,1,1,2,4,8,18,44,111,296,819,2332,6808,20302,61559,189413,590091,
%T 1858187,5906637,18932016,61130413,198697205,649706622,2135958254,
%U 7056831766,23420011178,78048740454,261099605923,876564670090,2952491169904,9975191222798
%N 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.
%C 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.
%H Andrew Howroyd, <a href="/A339837/b339837.txt">Table of n, a(n) for n = 0..500</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%e a(2) = 1 because exactly one node must be colored black.
%e 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.
%e There are 3 trees with 5 nodes:
%e o o
%e | |
%e o---o---o o---o---o---o---o o---o---o
%e | |
%e o o
%e These correspond respectively to 3, 3 and 2 solutions, so a(5) = 3 + 3 + 2 = 8.
%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o 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)}
%Y Cf. A038056 (bicolored trees), A339830 (independent only), A339834 (dominating only), A339838 (rooted), A340021 (graphs).
%K nonn
%O 0,4
%A _Andrew Howroyd_, Dec 20 2020