

A339830


Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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
 
ooo ooooo ooo
 
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



KEYWORD

nonn


AUTHOR



STATUS

approved



