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,3

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

Table of n, a(n) for n=1..26.

Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. 25, 515-541 (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.

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

Prog

(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

Crossrefs

Cf. A299037, A345135.

Sequence in context: A096351 A367890 A373740 * A086667 A067098 A188897

Adjacent sequences: A344931 A344932 A344933 * A344935 A344936 A344937

Keyword

nonn

Author

Mareike Fischer, Jun 09 2021

Status

approved