A339834 Number of bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.

1, 1, 2, 4, 11, 29, 91, 299, 1057, 3884, 14883, 58508, 235771, 967790, 4037807, 17074475, 73058753, 315803342, 1377445726, 6056134719, 26817483095, 119516734167, 535751271345, 2414304071965, 10932421750492, 49723583969029, 227079111492652, 1040939109111200, 4788357522831785

Offset

0,3

Comments

The black nodes form a dominating set. For n > 0, a(n) is then the total number of indistinguishable dominating 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, Dominating Set

Example

a(2) = 2 because at most one node can be colored white.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored white then both of the ends must be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.

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(u+v+w)); v=concat([0], t2-t1); w=concat([1], t1)); my(g=x*Ser(u+v), guw=x^2*Ser(u)*Ser(w)); Vec(1 + g + (subst(g, x, x^2) - g^2 - 2*guw)/2)}

Crossrefs

Cf. A038056 (bicolored trees), A339830, A339833, A339835 (rooted), A339836, A339837.

Sequence in context: A052869 A316768 A052831 * A148146 A148147 A298269

Adjacent sequences: A339831 A339832 A339833 * A339835 A339836 A339837

Keyword

nonn

Author

Andrew Howroyd, Dec 19 2020

Status

approved