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

1, 2, 2, 4, 10, 26, 75, 234, 768, 2647, 9466, 34818, 131149, 503640, 1965552, 7777081, 31138051, 125961762, 514189976, 2115922969, 8769932062, 36584593158, 153510347137, 647564907923, 2744951303121, 11687358605310, 49965976656637, 214423520420723, 923399052307921

Offset: 0

Author

Andrew Howroyd, Dec 19 2020

Keywords

• nonn

Comments

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.

Examples

			a(2) = 2 because at most one node can be colored black.
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.
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 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.
		

Links

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

Crossrefs

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

Programs

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
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)}