A337090 - OEIS

%I #15 Nov 24 2024 14:00:18

%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