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

Author

Mareike Fischer, Jun 09 2021

Keywords

• nonn
• easy

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.

Examples

			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))).
		

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.

Crossrefs

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

Programs

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}]

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)

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