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

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

Cf. A001190, A085748.

Sequence in context: A076736 A182906 A193359 * A106489 A132280 A345734

Adjacent sequences: A344610 A344611 A344612 * A344614 A344615 A344616

Keyword

nonn

Author

Mareike Fischer, Jun 09 2021

Status

approved