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).

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

Author

Mareike Fischer, Jun 09 2021

Keywords

• nonn

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.

Crossrefs

Cf. A001190, A085748.

Programs

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]]]]

Formula

a(n) = A001190(n/2) if n even, otherwise a(n) = A085748((n-1)/2).