login
Number of rooted unlabeled ordered (plane) trees with 2n leaves such that i) every internal node has an even number of children and ii) every path from the root to a leaf is the same length.
1

%I #11 Feb 26 2022 13:46:39

%S 0,1,2,3,6,13,29,65,147,337,785,1857,4452,10789,26365,64833,160167,

%T 397025,986593,2456193,6123726,15286021,38198573,95555937,239294222,

%U 599914489,1505750425,3783967201,9521244242,23988787485,60520345765,152889244033,386752047956

%N Number of rooted unlabeled ordered (plane) trees with 2n leaves such that i) every internal node has an even number of children and ii) every path from the root to a leaf is the same length.

%H Alois P. Heinz, <a href="/A219226/b219226.txt">Table of n, a(n) for n = 0..2401</a>

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 91

%F O.g.f. satisfies A(x) = x + A(x^2/(1-x^2)).

%p a:= proc(n) option remember; add(`if`(k=0, 1,

%p `if`(k::odd, a((k+1)/2)*binomial(n-1, k), 0)), k=0..n-1)

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Feb 26 2022

%t nn=60;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x-f[x^2/(1-x^2)],{x,0,nn}],x];a[0]=0;Table[a[n],{n,0,nn,2}]/.sol

%Y Cf. A014535, A027826.

%K nonn,eigen

%O 0,3

%A _Geoffrey Critzer_, Nov 15 2012