|
|
A344934
|
|
Number of rooted binary phylogenetic trees with n leaves and minimal Sackin tree balance index.
|
|
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|