login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307689 The number of rooted binary trees with minimal Colless tree balance index. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

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

LINKS

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

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

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

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

AUTHOR

Mareike Fischer, Apr 22 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 12 10:06 EDT 2021. Contains 342920 sequences. (Running on oeis4.)