cp's OEIS Frontend

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

%I A299037 #97 Aug 19 2023 20:51:35
%S A299037 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,
%T A299037 1,1,1,5,10,30,55,121,207,378,575,894,1217,1651,1993,2373,2546,2682,
%U A299037 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
%N A299037 a(n) is the number of rooted binary trees with minimal Sackin index and n leaves.
%C A299037 a(n) is also the number of maximally balanced trees with n leaves according to the Sackin index.
%C A299037 From _Omar E. Pol_, Feb 02 2018: (Start)
%C A299037 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).
%C A299037 Column 1 gives A000012. Column 2 gives A000027.
%C A299037 Conjecture 1: column 3 gives the nonzero terms of A000217.
%C A299037 Conjecture 2: column 4 gives the nonzero terms of A000330. (End)
%C A299037 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.
%C A299037 From _Omar E. Pol_, Mar 01 2018: (Start)
%C A299037 Conjecture 3: column 5 gives the nonzero terms of A212415.
%C A299037 Conjecture 4: row sums give 1 together with A006893.
%C A299037 Conjecture 5: T(i,j) has i >= 0 where "i" is the height of the rooted trees.
%C A299037 Conjecture 6: For i >= 1, j is the number of leaves minus 2^(i-1). (End)
%H A299037 Mareike Fischer, <a href="/A299037/b299037.txt">Table of n, a(n) for n = 1..1024</a>
%H A299037 Mareike Fischer, <a href="https://arxiv.org/abs/1801.10418">Extremal values of the Sackin balance index for rooted binary trees</a>, arXiv:1801.10418 [q-bio.PE], 2018, (see theorem 8 and subsequent remark).
%H A299037 Mareike Fischer, <a href="https://doi.org/10.1007/s00026-021-00539-2">Extremal Values of the Sackin Tree Balance Index</a>, Ann. Comb. (2021) Vol. 25, 515-541, Remark 5.
%H A299037 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A299037 a(1) = 1.
%F A299037 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).
%e A299037 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.
%e A299037 From _Omar E. Pol_, Feb 01 2018: (Start)
%e A299037 Written as an irregular triangle the sequence begins:
%e A299037   1;
%e A299037   1;
%e A299037   1, 1;
%e A299037   1, 2, 1,  1;
%e A299037   1, 3, 3,  5,  3,  3,  1,  1;
%e A299037   1, 4, 6, 14, 17, 27, 28, 35, 28, 27, 17, 14, 6, 4, 1, 1;
%e A299037   ... (End)
%t A299037 maxnumber = 1024;
%t A299037 minlist = {1}; For[n = 2, n <= maxnumber, n++,
%t A299037 parts = IntegerPartitions[n, {2}];
%t A299037 total = 0;
%t A299037 For[s = 1, s <= Length[parts], s++,
%t A299037   na = parts[[s]][[1]]; nb = parts[[s]][[2]]; k = Ceiling[Log2[n]];
%t A299037   ka = Ceiling[Log2[na]]; kb = Ceiling[Log2[nb]];
%t A299037   If[na >= n/2 && ka == k - 1 && kb == k - 1 && na != nb,
%t A299037    total = total + minlist[[na]]*minlist[[nb]],
%t A299037    If[na >= n/2 && ka == k - 1 && kb == k - 1 && na == nb,
%t A299037     total = total + Binomial[minlist[[na]] - 1 + 2, 2],
%t A299037     If[na >= n/2 && nb == 2^(k - 2) && ka == k - 1,
%t A299037      total = total + minlist[[na]]]]];
%t A299037   ]; AppendTo[minlist, total];
%t A299037 ]
%Y A299037 Cf. A001190 (number of rooted binary trees with n leaves), A011782.
%K A299037 nonn,tabf
%O A299037 1,6
%A A299037 _Mareike Fischer_, Feb 01 2018