A344934 - OEIS

%I #67 Jun 10 2021 01:47:16

%S 1,1,3,3,30,135,315,315,11340,198450,2182950,16372125,85135050,

%T 297972675,638512875,638512875,86837751000,5861548192500,

%U 259861969867500,8445514020693750,212826953321482500,4292010225316563750,70511596558772118750,951906553543423603125,10576739483815817812500,96248329302723942093750

%N Number of rooted binary phylogenetic trees with n leaves and minimal Sackin tree balance index.

%C Rooted binary phylogenetic trees with n leaves are rooted trees for which each internal node has precisely two children and whose leaves are bijectively labeled by the set {1,...,n}.

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

%F With k:=log_2(n) and g(n):=0 if n is odd and g(n) := (1/2)*binomial(n,n/2)*a(n/2) if n is even and pairs := set of all pairs (na,nb) such that na+nb=n and na >= nb and na > n/2 and na <= 2^(k-1) and nb >= 2^(k-2), we get:

%F a(n) = g(n) + sum over all described pairs (na,nb): binomial(n,na)*a(na)*a(nb).

%F a(n) = g(n) + Sum_{i=floor(n/2)+1..2^(k-1), i <= 2^(k-2)} binomial(n,i)*a(i)*a(n-i), where k = ceiling(log_2(n)) and g(n)=0 for odd n, g(n) = binomial(n,n/2)*a(n/2)/2 for even n.

%t a[n_] := Module[{k = Ceiling[Log2[n]], int, na, nb, sum, i},

%t   If[n == 1, Return[1],

%t    int = IntegerPartitions[n, {2}];

%t    If[OddQ[n], sum = 0, sum = 1/2*Binomial[n, n/2]*((a[n/2])^2)];

%t    For[i = 1, i <= Length[int], i++,

%t     na = int[[i]][[1]]; nb = int[[i]][[2]];

%t     If[na > n/2 && na <= 2^(k - 1) && nb >= 2^(k - 2),

%t      sum = sum + Binomial[n, na]*a[na]*a[nb];

%t      ];

%t     ];

%t    Return[sum];

%t    ]]

%o (PARI) seq(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, my(k=1+logint(n-1,2)); a[n]=if(n%2==0, a[n/2]*binomial(n,n/2)/2) + sum(i=n\2+1, min(2^(k-1), n-2^(k-2)), binomial(n,i)*a[i]*a[n-i])); a} \\ _Andrew Howroyd_, Jun 09 2021

%Y Cf. A299037, A345135.

%K nonn

%O 1,3

%A _Mareike Fischer_, Jun 09 2021