A299037 a(n) is the number of rooted binary trees with minimal Sackin index and n leaves.

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 5, 3, 3, 1, 1, 1, 4, 6, 14, 17, 27, 28, 35, 28, 27, 17, 14, 6, 4, 1, 1, 1, 5, 10, 30, 55, 121, 207, 378, 575, 894, 1217, 1651, 1993, 2373, 2546, 2682, 2546, 2373, 1993, 1651, 1217, 894, 575, 378, 207, 121, 55, 30, 10, 5, 1, 1, 1, 6, 15, 55, 135, 381, 903, 2205, 4848, 10599, 21631

Offset: 1

Author

Mareike Fischer, Feb 01 2018

Keywords

• nonn
• tabf

Comments

a(n) is also the number of maximally balanced trees with n leaves according to the Sackin index.

From Omar E. Pol, Feb 02 2018: (Start)

Also the sequence can be written as an irregular triangle read by rows in which the row lengths are the terms of A011782 (see example section).

Column 1 gives A000012. Column 2 gives A000027.

Conjecture 1: column 3 gives the nonzero terms of A000217.

Conjecture 2: column 4 gives the nonzero terms of A000330. (End)

Comment from the author, Feb 02 2018: Denote the (i,j)-th entry of the irregular triangle described above (row i, column j) with T(i,j), i >= 1 and 1 <= j <= A011782(i-1). Then, rows 1 and 2 contain a 1 each (and they denote the number of trees minimizing the Sackin index with 1 and two leaves, respectively) and row i ranges from 2^(i-2) + 1 to 2^(i-1) leaves and for each of these numbers gives the number of trees with minimum Sackin index. E.g., row 4 gives the number of such trees for 2^(4-2) + 1 = 5 leaves up to 2^(4-1) = 8 leaves.

From Omar E. Pol, Mar 01 2018: (Start)

Conjecture 3: column 5 gives the nonzero terms of A212415.

Conjecture 4: row sums give 1 together with A006893.

Conjecture 5: T(i,j) has i >= 0 where "i" is the height of the rooted trees.

Conjecture 6: For i >= 1, j is the number of leaves minus 2^(i-1). (End)

Examples

			Whenever n = 2^k, i.e., n is a power of 2, then the tree minimizing the Sackin index is unique, namely the so-called fully balanced tree of height k.
From _Omar E. Pol_, Feb 01 2018: (Start)
Written as an irregular triangle the sequence begins:
  1;
  1;
  1, 1;
  1, 2, 1,  1;
  1, 3, 3,  5,  3,  3,  1,  1;
  1, 4, 6, 14, 17, 27, 28, 35, 28, 27, 17, 14, 6, 4, 1, 1;
  ... (End)
		

Links

• Mareike Fischer, Table of n, a(n) for n = 1..1024
• Mareike Fischer, Extremal values of the Sackin balance index for rooted binary trees, arXiv:1801.10418 [q-bio.PE], 2018, (see theorem 8 and subsequent remark).
• Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Remark 5.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A001190 (number of rooted binary trees with n leaves), A011782.

Programs

Mathematica

maxnumber = 1024;
minlist = {1}; For[n = 2, n <= maxnumber, n++,
parts = IntegerPartitions[n, {2}];
total = 0;
For[s = 1, s <= Length[parts], s++,
  na = parts[[s]][[1]]; nb = parts[[s]][[2]]; k = Ceiling[Log2[n]];
  ka = Ceiling[Log2[na]]; kb = Ceiling[Log2[nb]];
  If[na >= n/2 && ka == k - 1 && kb == k - 1 && na != nb,
   total = total + minlist[[na]]*minlist[[nb]],
   If[na >= n/2 && ka == k - 1 && kb == k - 1 && na == nb,
    total = total + Binomial[minlist[[na]] - 1 + 2, 2],
    If[na >= n/2 && nb == 2^(k - 2) && ka == k - 1,
     total = total + minlist[[na]]]]];
  ]; AppendTo[minlist, total];
]

Formula

a(1) = 1.

a(n) = Sum_{(n_a,n_b): n_a+n_b=n, n_a>=n/2, ceiling(log_2(n_a)) = ceiling(log_2(n))-1, ceiling(log_2(n_b)) = ceiling(log_2(n))-1,n_a!=n_b} a(n_a)*a(n_b) + Sum_{(n_a,n_b): n_a+n_b=n, ceiling(log_2(n_a)) = ceiling(log_2(n)) - 1, ceiling(log_2(n_b)) = ceiling(log_2(n)) - 1, n_a = n_b} binomial(a(n_a)+1,2) + Sum_{(n_a,n_b): n_a+n_b=n, ceiling(log_2(n_a)) = ceiling(log_2(n)) - 1, n_b = 2^(ceiling(log_2(n))-2)} a(n_a).