cp's OEIS Frontend

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

%I A345135 #42 Jul 18 2024 14:26:39
%S A345135 1,1,1,2,1,4,6,4,1,8,28,56,70,56,28,8,1,16,120,560,1820,4368,8008,
%T A345135 11440,12870,11440,8008,4368,1820,560,120,16,1,32,496,4960,35960,
%U A345135 201376,906192,3365856,10518300,28048800,64512240,129024480,225792840,347373600,471435600
%N A345135 Number of ordered rooted binary trees with n leaves and with minimal Sackin tree balance index.
%C A345135 Ordered rooted binary trees are trees with two descendants per inner node where left and right are distinguished.
%C A345135 The Sackin tree balance index is also known as total external path length.
%C A345135 a(0) = 1 by convention.
%H A345135 Alois P. Heinz, <a href="/A345135/b345135.txt">Table of n, a(n) for n = 0..4096</a>
%H A345135 Mareike Fischer, <a href="https://doi.org/10.1007/s00026-021-00539-2">Extremal Values of the Sackin Tree Balance Index.</a> Ann. Comb. 25, 515-541 (2021), Theorem 7.
%F A345135 a(n) = binomial(2^(ceiling(log_2(n))-1),n-2^(ceiling(log_2(n))-1)).
%F A345135 a(n) = binomial(A053644(n),n-A053644(n)).
%F A345135 a(2^n) = 1.
%F A345135 a(2^n-1) = A011782(n).
%F A345135 a(2^n+1) = A000079(n).
%F A345135 From _Alois P. Heinz_, Jun 09 2021: (Start)
%F A345135 max({ a(k) | k = 2^n..2^(n+1) }) = A037293(n).
%F A345135 Sum_{i=2^n..2^(n+1)-1} a(i) = 2^(2^n) - 1 = A051179(n). (End)
%F A345135 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
%e A345135 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))).
%p A345135 a:= n-> (b-> binomial(b, n-b))(2^ilog2(n)):
%p A345135 seq(a(n), n=0..46);  # _Alois P. Heinz_, Jun 09 2021
%t A345135 a[0] := 1; a[n_] := Module[{k = 2^(BitLength[n] - 1)}, Binomial[k, n - k]];
%t A345135 Table[a[n], {n, 0, 46}]
%Y A345135 Cf. A000079, A000108, A011782, A037293, A051179, A053644, A299037.
%K A345135 nonn,easy
%O A345135 0,4
%A A345135 _Mareike Fischer_, Jun 09 2021