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,2

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Eric Weisstein's World of Mathematics, Independent Vertex Set

Example

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.

Prog

(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)}

Crossrefs

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

Sequence in context: A025244 A132824 A298898 * A078801 A309159 A002420

Adjacent sequences: A339827 A339828 A339829 * A339831 A339832 A339833

Keyword

nonn

Author

Andrew Howroyd, Dec 19 2020

Status

approved