cp's OEIS Frontend

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

%I A344613 #39 Jun 10 2021 15:03:02
%S A344613 1,1,1,1,2,1,4,2,9,3,20,6,46,11,106,23,248,46,582,98,1376,207,3264,
%T A344613 451,7777,983,18581,2179,44526,4850,106936,10905,257379,24631,620577,
%U A344613 56011,1498788,127912,3625026,293547,8779271,676157,21287278,1563372,51671864,3626149,125550018
%N 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).
%C A344613 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 A344613 Alois P. Heinz, <a href="/A344613/b344613.txt">Table of n, a(n) for n = 1..5000</a>
%H A344613 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 A344613 a(n) = A001190(n/2) if n even, otherwise a(n) = A085748((n-1)/2).
%p A344613 b:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
%p A344613       (t-> t*(1-t)/2)(b(n/2)))+add(b(i)*b(n-i), i=1..n/2))
%p A344613     end:
%p A344613 g:= proc(n) option remember; `if`(n<1, 1,
%p A344613       add(g(n-i)*b(i), i=1..n))
%p A344613     end:
%p A344613 a:= n-> `if`(n::even, b(n/2), g((n-1)/2)):
%p A344613 seq(a(n), n=1..52);  # _Alois P. Heinz_, Jun 09 2021
%t A344613 (* WE generates the Wedderburn Etherington Numbers, OEIS sequence A001190 *)
%t A344613 WE[n_] := Module[{i},
%t A344613    If[n == 1, Return[1],
%t A344613     If[Mod[n, 2] == 0,
%t A344613      Return[
%t A344613       WE[n/2]*(WE[n/2] + 1)/2 + Sum[WE[i]*WE[n - i], {i, 1, n/2 - 1}]],
%t A344613      Return[Sum[WE[i]*WE[n - i], {i, 1, Floor[n/2]}]]
%t A344613      ]
%t A344613     ]
%t A344613    ];
%t A344613 (* b is just a support function *)
%t A344613 b[n_] := b[n] =
%t A344613    If[n < 2, n,
%t A344613     If[OddQ[n], 0, Function[t, t*(1 - t)/2][b[n/2]]] +
%t A344613      Sum[b[i]*b[n - i], {i, 1, n/2}]];
%t A344613 (* c generates the elements of OEIS sequence A085748 *)
%t A344613 c[n_] := c[n] = If[n < 1, 1, Sum[c[n - i]*b[i], {i, 1, n}]];
%t A344613 (* a generates the number of rooted binary trees with maximal number of cherries *)
%t A344613 a[n_] := Module[{},
%t A344613   If[EvenQ[n], Return[WE[n/2]], Return[c[(n - 1)/2]]]]
%Y A344613 Cf. A001190, A085748.
%K A344613 nonn
%O A344613 1,5
%A A344613 _Mareike Fischer_, Jun 09 2021