OFFSET
0,4
COMMENTS
Ordered rooted binary trees are trees with two descendants per inner node where left and right are distinguished.
The Sackin tree balance index is also known as total external path length.
a(0) = 1 by convention.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..4096
Mareike Fischer, Extremal Values of the Sackin Tree Balance Index. Ann. Comb. 25, 515-541 (2021), Theorem 7.
FORMULA
a(n) = binomial(2^(ceiling(log_2(n))-1),n-2^(ceiling(log_2(n))-1)).
a(2^n) = 1.
a(2^n-1) = A011782(n).
a(2^n+1) = A000079(n).
From Alois P. Heinz, Jun 09 2021: (Start)
max({ a(k) | k = 2^n..2^(n+1) }) = A037293(n).
Sum_{i=2^n..2^(n+1)-1} a(i) = 2^(2^n) - 1 = A051179(n). (End)
Conjecture: Sum_{n>=0} a(n)*x^n = 1 + x + Sum_{n>=0} x^(2^n) * ((1 + x)^(2^n) - 1). - Paul D. Hanna, Jul 18 2024
EXAMPLE
a(1) = a(2) = 1 because there are only the trees (o) and (o,o) which get counted. a(3) = 2 because the trees ((o,o),o) and (o,(o,o)) get counted. a(4) = 1 because only the tree ((o,o),(o,o)) is counted. Note that the other possible rooted binary ordered trees with four leaves, namely the different orderings of (((o,o),o),o), are not Sackin minimal. a(5) = 4 because the following trees get counted: (((o,o),o),(o,o)), ((o,(o,o)),(o,o)), ((o,o),((o,o),o)), ((o,o),(o,(o,o))).
MAPLE
a:= n-> (b-> binomial(b, n-b))(2^ilog2(n)):
seq(a(n), n=0..46); # Alois P. Heinz, Jun 09 2021
MATHEMATICA
a[0] := 1; a[n_] := Module[{k = 2^(BitLength[n] - 1)}, Binomial[k, n - k]];
Table[a[n], {n, 0, 46}]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Mareike Fischer, Jun 09 2021
STATUS
approved