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

0, 0, 0, 1, 3, 9, 19, 38, 64, 106, 162, 243, 343, 479, 645, 860, 1110, 1424, 1790, 2237, 2743, 3349, 4035, 4842, 5734, 6770, 7920, 9239, 10679, 12315, 14105, 16120, 18290, 20716, 23342, 26257, 29377, 32821, 36517, 40574, 44880, 49586, 54602, 60059, 65827, 72079, 78705, 85860, 93376, 101468

Offset: 1

Author

Francesc Rosselló, Mar 06 2018

Keywords

• nonn
• easy

Comments

Grows asymptotically in O(n^4).

Links

• T. M. Coronado, A. Mir, F. Rosselló, and G. Valiente, A balance index for phylogenetic trees based on quartets, arXiv preprint arXiv:1803.01651 [q-bio.PE], 2018.
• Tomás M. Coronado, Balance indices for phylogenetic trees under well-known probability models, Linköping University (Sweden, 2020).

Programs

Mathematica

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 *)

R

q=c(0,0,0,1)
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)}

Formula

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.