login
a(n) is the maximum value of the quartet index of a bifurcating rooted tree with n leaves.
0

%I #27 Mar 12 2021 19:33:30

%S 0,0,0,1,3,9,19,38,64,106,162,243,343,479,645,860,1110,1424,1790,2237,

%T 2743,3349,4035,4842,5734,6770,7920,9239,10679,12315,14105,16120,

%U 18290,20716,23342,26257,29377,32821,36517,40574,44880,49586,54602,60059,65827,72079,78705,85860,93376,101468

%N a(n) is the maximum value of the quartet index of a bifurcating rooted tree with n leaves.

%C Grows asymptotically in O(n^4).

%H T. M. Coronado, A. Mir, F. Rosselló, and G. Valiente, <a href="https://arxiv.org/abs/1803.01651">A balance index for phylogenetic trees based on quartets</a>, arXiv preprint arXiv:1803.01651 [q-bio.PE], 2018.

%H Tomás M. Coronado, <a href="https://www.ida.liu.se/divisions/stima/seminarier/Slides/Linkoping_University_Seminar_Balance_indices.pdf">Balance indices for phylogenetic trees under well-known probability models</a>, Linköping University (Sweden, 2020).

%F a(n) = a(floor(n/2)) + a(ceiling(n/2)) + binomial(floor(n/2),2) * binomial(ceiling(n/2),2) for n>3; with a(1)=a(2)=a(3)=0.

%t a[n_] := a[Floor[n/2]] + a[Ceiling[n/2]] + Binomial[Floor[n/2], 2]*Binomial[Ceiling[n/2], 2]; a[1] = 0; Array[a, 50] (* _Robert G. Wilson v_, Mar 06 2018 *)

%o (R) q=c(0,0,0,1)

%o for (i in (4:20)){q[i]=q[floor(i/2)] + q[ceiling(i/2)] + choose(floor(i/2),2) * choose(ceiling(i/2),2)}

%K nonn,easy

%O 1,5

%A _Francesc Rosselló_, Mar 06 2018