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
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
KEYWORD
nonn
AUTHOR
Mareike Fischer, Jun 09 2021
STATUS
approved