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

Author

Andrew Howroyd, Dec 19 2020

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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