login
Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.
6

%I #10 Jan 09 2021 22:12:29

%S 1,2,2,4,10,26,75,234,768,2647,9466,34818,131149,503640,1965552,

%T 7777081,31138051,125961762,514189976,2115922969,8769932062,

%U 36584593158,153510347137,647564907923,2744951303121,11687358605310,49965976656637,214423520420723,923399052307921

%N Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.

%C The black nodes form an independent vertex set. For n > 0, a(n) is then the total number of indistinguishable independent vertex sets summed over distinct unlabeled trees with n nodes.

%H Andrew Howroyd, <a href="/A339830/b339830.txt">Table of n, a(n) for n = 0..500</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%e a(2) = 2 because at most one node can be colored black.

%e a(3) = 4 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 zero, one or both of the ends can be colored black. In total there are 4 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 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.

%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}

%o seq(n)={my(u=v=[1]); for(n=2, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u+v)); u=t); my(g=x*Ser(u+v), gu=x*Ser(u)); Vec(1 + g + (subst(g,x,x^2) - subst(gu,x,x^2) - g^2 + gu^2)/2)}

%Y Cf. A038056 (bicolored trees), A339829, A339831, A339832, A339834, A339837.

%K nonn

%O 0,2

%A _Andrew Howroyd_, Dec 19 2020