cp's OEIS Frontend

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

%I A344934 #67 Jun 10 2021 01:47:16
%S A344934 1,1,3,3,30,135,315,315,11340,198450,2182950,16372125,85135050,
%T A344934 297972675,638512875,638512875,86837751000,5861548192500,
%U A344934 259861969867500,8445514020693750,212826953321482500,4292010225316563750,70511596558772118750,951906553543423603125,10576739483815817812500,96248329302723942093750
%N A344934 Number of rooted binary phylogenetic trees with n leaves and minimal Sackin tree balance index.
%C A344934 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 A344934 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 A344934 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 A344934 a(n) = g(n) + sum over all described pairs (na,nb): binomial(n,na)*a(na)*a(nb).
%F A344934 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 A344934 a[n_] := Module[{k = Ceiling[Log2[n]], int, na, nb, sum, i},
%t A344934   If[n == 1, Return[1],
%t A344934    int = IntegerPartitions[n, {2}];
%t A344934    If[OddQ[n], sum = 0, sum = 1/2*Binomial[n, n/2]*((a[n/2])^2)];
%t A344934    For[i = 1, i <= Length[int], i++,
%t A344934     na = int[[i]][[1]]; nb = int[[i]][[2]];
%t A344934     If[na > n/2 && na <= 2^(k - 1) && nb >= 2^(k - 2),
%t A344934      sum = sum + Binomial[n, na]*a[na]*a[nb];
%t A344934      ];
%t A344934     ];
%t A344934    Return[sum];
%t A344934    ]]
%o A344934 (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 A344934 Cf. A299037, A345135.
%K A344934 nonn
%O A344934 1,3
%A A344934 _Mareike Fischer_, Jun 09 2021