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.

1, 1, 1, 2, 4, 8, 18, 44, 111, 296, 819, 2332, 6808, 20302, 61559, 189413, 590091, 1858187, 5906637, 18932016, 61130413, 198697205, 649706622, 2135958254, 7056831766, 23420011178, 78048740454, 261099605923, 876564670090, 2952491169904, 9975191222798

Offset

0,4

Comments

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.

Links

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

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Example

a(2) = 1 because exactly one node must be colored black.
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.
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 3, 3 and 2 solutions, so a(5) = 3 + 3 + 2 = 8.

Prog

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

Crossrefs

Cf. A038056 (bicolored trees), A339830 (independent only), A339834 (dominating only), A339838 (rooted), A340021 (graphs).

Sequence in context: A233139 A308246 A114203 * A100132 A176720 A088457

Adjacent sequences: A339834 A339835 A339836 * A339838 A339839 A339840

Keyword

nonn

Author

Andrew Howroyd, Dec 20 2020

Status

approved