login
A344613
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).
2
1, 1, 1, 1, 2, 1, 4, 2, 9, 3, 20, 6, 46, 11, 106, 23, 248, 46, 582, 98, 1376, 207, 3264, 451, 7777, 983, 18581, 2179, 44526, 4850, 106936, 10905, 257379, 24631, 620577, 56011, 1498788, 127912, 3625026, 293547, 8779271, 676157, 21287278, 1563372, 51671864, 3626149, 125550018
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
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.
FORMULA
a(n) = A001190(n/2) if n even, otherwise a(n) = A085748((n-1)/2).
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
Sequence in context: A076736 A182906 A193359 * A106489 A132280 A345734
KEYWORD
nonn
AUTHOR
Mareike Fischer, Jun 09 2021
STATUS
approved