cp's OEIS Frontend

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.

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