|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
a(n) is also the number of maximally balanced trees with n leaves according to the Sackin index.
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).
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.
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
|
|
|
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.
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|