|
%I #39 Jun 10 2021 15:03:02
%S 1,1,1,1,2,1,4,2,9,3,20,6,46,11,106,23,248,46,582,98,1376,207,3264,
%T 451,7777,983,18581,2179,44526,4850,106936,10905,257379,24631,620577,
%U 56011,1498788,127912,3625026,293547,8779271,676157,21287278,1563372,51671864,3626149,125550018
%N Number of rooted binary trees (in which all inner nodes have precisely two children) with n leaves and with maximal number of cherries (i.e., maximal number of pendant subtrees with two leaves).
%C This sequence describes the number of rooted binary trees with n leaves with maximal cherry tree balance index or, equivalently, with minimal modified cherry tree balance index.
%H Alois P. Heinz, <a href="/A344613/b344613.txt">Table of n, a(n) for n = 1..5000</a>
%H S. J. Kersting and M. Fischer, <a href="https://arxiv.org/abs/2105.00719">Measuring tree balance using symmetry nodes - a new balance index and its extremal properties</a>, arXiv:2105.00719 [q-bio.PE], 2021.
%F a(n) = A001190(n/2) if n even, otherwise a(n) = A085748((n-1)/2).
%p b:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
%p (t-> t*(1-t)/2)(b(n/2)))+add(b(i)*b(n-i), i=1..n/2))
%p end:
%p g:= proc(n) option remember; `if`(n<1, 1,
%p add(g(n-i)*b(i), i=1..n))
%p end:
%p a:= n-> `if`(n::even, b(n/2), g((n-1)/2)):
%p seq(a(n), n=1..52); # _Alois P. Heinz_, Jun 09 2021
%t (* WE generates the Wedderburn Etherington Numbers, OEIS sequence A001190 *)
%t WE[n_] := Module[{i},
%t If[n == 1, Return[1],
%t If[Mod[n, 2] == 0,
%t Return[
%t WE[n/2]*(WE[n/2] + 1)/2 + Sum[WE[i]*WE[n - i], {i, 1, n/2 - 1}]],
%t Return[Sum[WE[i]*WE[n - i], {i, 1, Floor[n/2]}]]
%t ]
%t ]
%t ];
%t (* b is just a support function *)
%t b[n_] := b[n] =
%t If[n < 2, n,
%t If[OddQ[n], 0, Function[t, t*(1 - t)/2][b[n/2]]] +
%t Sum[b[i]*b[n - i], {i, 1, n/2}]];
%t (* c generates the elements of OEIS sequence A085748 *)
%t c[n_] := c[n] = If[n < 1, 1, Sum[c[n - i]*b[i], {i, 1, n}]];
%t (* a generates the number of rooted binary trees with maximal number of cherries *)
%t a[n_] := Module[{},
%t If[EvenQ[n], Return[WE[n/2]], Return[c[(n - 1)/2]]]]
%Y Cf. A001190, A085748.
%K nonn
%O 1,5
%A _Mareike Fischer_, Jun 09 2021
|
