A337090 - OEIS

A337090

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

%I #11 Oct 31 2020 02:55:32

%S 0,0,1,1,2,3,6,11,22,43,89,183,384,812,1738,3742,8125,17735,38941,

%T 85898,190328,423320,944933,2115941,4752138,10701191,24157460,

%U 54658278,123930534,281546031,640785749,1460879893,3335858947,7628666743,17470228499,40060975624

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

%C For n=0, there are no rooted trees at all, per A000081.

%C For n>=1, by omitting the root vertex, a(n) is the number of nonempty rooted forests of n-1 vertices with all leaves at even depths down from the forest roots.

%C 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 shift-up 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 cross-products re-using term a(1) expect the empty forest there, so +1 because it's not. A337089 is, in its turn, shift-up of the Euler transform of the present sequence so that it's convenient to calculate them together term by term.

%H Kevin Ryde, <a href="/A337090/b337090.txt">Table of n, a(n) for n = 0..600</a>

%F a(n) = (Sum_{k=1..n-1} (a(k) + (1 if k=1)) * Sum_{d divides n-k} d*A337089(d)) /(n-1), for n>=2.

%F G.f.: x*(-1 + Product_{k>=1} 1/(1-x^k)^A337089(k)).

%F G.f.: x*(-1 + exp(Sum_{k>=1} A337089(x^k)/k)).

%e For n=5 vertices, there are a(5) = 3 rooted trees in which all leaves are at odd depths

%e * * * depth=0, root

%e // \\ |\ |

%e * * * * * * * depth=1, odd

%e | |

%e * *

%e | |\

%e * * * depth=3, odd

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

%Y Cf. A337089.

%K nonn

%O 0,5

%A _Kevin Ryde_, Aug 15 2020