

A337090


Number of rooted trees of n vertices in which all leaves are at odd depths (distances down from the root).


2



0, 0, 1, 1, 2, 3, 6, 11, 22, 43, 89, 183, 384, 812, 1738, 3742, 8125, 17735, 38941, 85898, 190328, 423320, 944933, 2115941, 4752138, 10701191, 24157460, 54658278, 123930534, 281546031, 640785749, 1460879893, 3335858947, 7628666743, 17470228499, 40060975624
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

For n=0, there are no rooted trees at all, per A000081.
For n>=1, by omitting the root vertex, a(n) is the number of nonempty rooted forests of n1 vertices with all leaves at even depths down from the forest roots.
A337089 counts trees with all leaves at even depths. The forests interpretation here is those even trees assembled to make even forests so that this sequence is shiftup of the Euler transform of A337089. But the usual Euler transform includes an empty forest which is not wanted here, and so 1 in the generating function forms. The sum formula is the usual Euler transform, except its crossproducts reusing term a(1) expect the empty forest there, so +1 because it's not. A337089 is, in its turn, shiftup of the Euler transform of the present sequence so that it's convenient to calculate them together term by term.


LINKS



FORMULA

a(n) = (Sum_{k=1..n1} (a(k) + (1 if k=1)) * Sum_{d divides nk} d*A337089(d)) /(n1), for n>=2.
G.f.: x*(1 + Product_{k>=1} 1/(1x^k)^A337089(k)).
G.f.: x*(1 + exp(Sum_{k>=1} A337089(x^k)/k)).


EXAMPLE

For n=5 vertices, there are a(5) = 3 rooted trees in which all leaves are at odd depths
* * * depth=0, root
// \\ \ 
* * * * * * * depth=1, odd
 
* *
 \
* * * depth=3, odd


PROG

(PARI) See A337089 where the vector "odds" is the present sequence.


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



