A345135 Number of ordered rooted binary trees with n leaves and with minimal Sackin tree balance index.

1, 1, 1, 2, 1, 4, 6, 4, 1, 8, 28, 56, 70, 56, 28, 8, 1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1, 32, 496, 4960, 35960, 201376, 906192, 3365856, 10518300, 28048800, 64512240, 129024480, 225792840, 347373600, 471435600

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(n) = binomial(A053644(n),n-A053644(n)).

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)

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

Cf. A000079, A000108, A011782, A037293, A051179, A053644, A299037.

Sequence in context: A193902 A043302 A343964 * A291057 A143897 A217298

Adjacent sequences: A345132 A345133 A345134 * A345136 A345137 A345138

Keyword

nonn,easy

Author

Mareike Fischer, Jun 09 2021

Status

approved