login
A299037
a(n) is the number of rooted binary trees with minimal Sackin index and n leaves.
5
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,6
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)
LINKS
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.
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).
EXAMPLE
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)
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];
]
CROSSREFS
Cf. A001190 (number of rooted binary trees with n leaves), A011782.
Sequence in context: A309240 A057001 A307689 * A173072 A219272 A084097
KEYWORD
nonn,tabf
AUTHOR
Mareike Fischer, Feb 01 2018
STATUS
approved