OFFSET
1,5
COMMENTS
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.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..5000
S. J. Kersting and M. Fischer, Measuring tree balance using symmetry nodes - a new balance index and its extremal properties, arXiv:2105.00719 [q-bio.PE], 2021.
MAPLE
b:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
(t-> t*(1-t)/2)(b(n/2)))+add(b(i)*b(n-i), i=1..n/2))
end:
g:= proc(n) option remember; `if`(n<1, 1,
add(g(n-i)*b(i), i=1..n))
end:
a:= n-> `if`(n::even, b(n/2), g((n-1)/2)):
seq(a(n), n=1..52); # Alois P. Heinz, Jun 09 2021
MATHEMATICA
(* WE generates the Wedderburn Etherington Numbers, OEIS sequence A001190 *)
WE[n_] := Module[{i},
If[n == 1, Return[1],
If[Mod[n, 2] == 0,
Return[
WE[n/2]*(WE[n/2] + 1)/2 + Sum[WE[i]*WE[n - i], {i, 1, n/2 - 1}]],
Return[Sum[WE[i]*WE[n - i], {i, 1, Floor[n/2]}]]
]
]
];
(* b is just a support function *)
b[n_] := b[n] =
If[n < 2, n,
If[OddQ[n], 0, Function[t, t*(1 - t)/2][b[n/2]]] +
Sum[b[i]*b[n - i], {i, 1, n/2}]];
(* c generates the elements of OEIS sequence A085748 *)
c[n_] := c[n] = If[n < 1, 1, Sum[c[n - i]*b[i], {i, 1, n}]];
(* a generates the number of rooted binary trees with maximal number of cherries *)
a[n_] := Module[{},
If[EvenQ[n], Return[WE[n/2]], Return[c[(n - 1)/2]]]]
CROSSREFS
KEYWORD
nonn
AUTHOR
Mareike Fischer, Jun 09 2021
STATUS
approved