login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Eric Weisstein's World of Mathematics, Independent Vertex Set
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
| |
o---o---o o---o---o---o---o o---o---o
| |
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
Cf. A038056 (bicolored trees), A339829, A339831, A339832, A339834, A339837.
Sequence in context: A025244 A132824 A298898 * A078801 A309159 A002420
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:13 EDT 2024. Contains 371265 sequences. (Running on oeis4.)