The OEIS is supported by the many generous donors to the OEIS Foundation.

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
`