login
A339834
Number of bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.
6
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
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
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved