A307689 The number of rooted binary trees on n leaves with minimal Colless index.

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 4, 3, 3, 1, 1, 1, 4, 6, 10, 16, 21, 13, 11, 13, 21, 16, 10, 6, 4, 1, 1, 1, 5, 10, 20, 50, 82, 73, 66, 184, 411, 548, 351, 455, 326, 144, 67, 144, 326, 455, 351, 548, 411, 184, 66, 73, 82, 50, 20, 10, 5, 1, 1

Offset

1,6

Comments

a(n) is the number of maximally balanced binary rooted trees with n leaves according to the Colless imbalance index. It is bounded above by sequence A299037.

Links

Mareike Fischer, Table of n, a(n) for n = 1..512

Tomás M. Coronado and Francesc Rosselló, The minimum value of the Colless index arXiv:1903.11670 [q-bio.PE], 2019.

Mareike Fischer, Lina Herbst, and Kristina Wicke, Extremal properties of the Colless tree balance index for rooted binary trees, arXiv:1904.09771 [math.CO], 2019.

Tree Balance, Colless index

Formula

a(1)=1; a(n) = Sum_{(n_a,n_b): n_a+n_b=n, n_a > n_b, (n_a,n_b) in QB(n)}} ( a(n_a)* a(n_b)) +f(n), where f(n)=0 if n is odd} and f(n)= binomial(a(n/2)+1,2) if n is even; and where QB(n)={(n_a,n_b): n_a+n_b=n and such that there exists a tree T on n leaves with minimal Colless index and with leaf partitioning (n_a,n_b)} }.

Example

There are 13 trees with minimal Colless index and 23 leaves, i.e. a(23)=13.

Mathematica

(*QB[n] is just a support function -- the function that actually generates the sequence of the numbers of trees with minimal Colless index and n leaves is given by minCbasedonQB; see below*)
QB[n_] := Module[{k, n0, bin, l, m = {}, i, length, qb = {}, j},
  If[OddQ[n], k = 0,
   k = FactorInteger[n][[1]][[2]];
   ];
  n0 = n/(2^k);
  bin = IntegerDigits[n0, 2];
  length = Length[bin];
  For[i = Length[bin], i >= 1, i--,
   If[bin[[i]] != 0, PrependTo[m, length - i]];
   ];
  l = Length[m];
  If[l == 1, Return[{{n/2, n/2}}],
   AppendTo[
    qb, {2^k*(Sum[2^(m[[i]] - 1), {i, 1, l - 1}] + 1),
     2^k*(Sum[2^(m[[i]] - 1), {i, 1, l - 1}])}];
   For[j = 2, j <= l - 1, j++,
    If[m[[j]] > m[[j + 1]] + 1,
     AppendTo[
      qb, {2^k*(Sum[2^(m[[i]] - 1), {i, 1, j - 1}] + 2^m[[j]]),
       n - 2^k*(Sum[2^(m[[i]] - 1), {i, 1, j - 1}] + 2^m[[j]])}]];
    If[m[[j]] < m[[j - 1]] - 1,
     AppendTo[
      qb, {n - 2^k*Sum[2^(m[[i]] - 1), {i, 1, j - 1}],
       2^k*Sum[2^(m[[i]] - 1), {i, 1, j - 1}]}]];
    ];
   If[k >= 1, AppendTo[qb, {n/2, n/2}]];
   Return[qb];
   ];
  ]
minCbasedonQB[n_] := Module[{qb = QB[n], min = 0, i, na, nb},
  If[n == 1, Return[1],
   For[i = 1, i <= Length[qb], i++,
    na = qb[[i]][[1]]; nb = qb[[i]][[2]];
    If[na != nb, min = min + minCbasedonQB[na]*minCbasedonQB[nb],
     min = min + Binomial[minCbasedonQB[n/2] + 1, 2]];
    ];
   Return[min];
   ]
  ]

Crossrefs

The sequence is bounded above by A299037.

The sequence of the number of trees with minimal Colless index is also linked to the values of the minimal Colless index as given by A296062.

Sequence in context: A126347 A309240 A057001 * A299037 A173072 A219272

Adjacent sequences: A307686 A307687 A307688 * A307690 A307691 A307692

Keyword

nonn,look

Author

Mareike Fischer, Apr 22 2019

Status

approved