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

1, 1, 3, 3, 30, 135, 315, 315, 11340, 198450, 2182950, 16372125, 85135050, 297972675, 638512875, 638512875, 86837751000, 5861548192500, 259861969867500, 8445514020693750, 212826953321482500, 4292010225316563750, 70511596558772118750, 951906553543423603125, 10576739483815817812500, 96248329302723942093750

Offset: 1

Author

Mareike Fischer, Jun 09 2021

Keywords

• nonn

Comments

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

Links

• Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. 25, 515-541 (2021).

Crossrefs

Cf. A299037, A345135.

Programs

Mathematica

a[n_] := Module[{k = Ceiling[Log2[n]], int, na, nb, sum, i},
  If[n == 1, Return[1],
   int = IntegerPartitions[n, {2}];
   If[OddQ[n], sum = 0, sum = 1/2*Binomial[n, n/2]*((a[n/2])^2)];
   For[i = 1, i <= Length[int], i++,
    na = int[[i]][[1]]; nb = int[[i]][[2]];
    If[na > n/2 && na <= 2^(k - 1) && nb >= 2^(k - 2),
     sum = sum + Binomial[n, na]*a[na]*a[nb];
     ];
    ];
   Return[sum];
   ]]

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

Formula

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:

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

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.