login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216499 The maximum possible number of rooted triples consistent with any galled-tree (level-1 phylogenetic network) containing exactly n leaves. 3

%I #21 Jan 19 2019 04:15:43

%S 0,0,0,2,7,16,32,55,87,130,184,252,335,433,550,686,842,1022,1224,1451,

%T 1706,1987,2299,2642,3015,3426,3870,4349,4870,5428,6028,6672,7357,

%U 8091,8871,9696,10576,11505,12486,13525,14616,15766,16976,18242,19574,20968

%N The maximum possible number of rooted triples consistent with any galled-tree (level-1 phylogenetic network) containing exactly n leaves.

%C Chao et al. (2012) proved: lim_{n --> infinity} a(n) / (3 (n choose 3)) = 2 (sqrt(3) - 1)/3 = 0.488033... and: a(n) / (3 (n choose 3)) > 2 (sqrt(3) - 1)/3 = 0.488033... for all n > 2.

%C a(n) = A061061(n) + (n choose 3).

%D J. Byrka, P. Gawrychowski, K. T. Huber and S. Kelk. Worst-case optimal approximation algorithms for maximizing triple consistency within phylogenetic networks. Journal of Discrete Algorithms, Vol. 8, Number 1, pp. 65-75, 2010.

%D K.-M. Chao, A.-C. Chu, J. Jansson, R. S. Lemence and A. Mancheron. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. Proceedings of the Ninth Annual Conference on Theory and Applications of Models of Computation (TAMC 2012), Lecture Notes in Computer Science, Vol. 7287, pp. 177-188, Springer-Verlag Berlin Heidelberg, 2012.

%D J. Jansson, N. B. Nguyen and W.-K. Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. SIAM Journal on Computing, Vol. 35, Number 5, pp. 1098-1121, Society for Industrial and Applied Mathematics (SIAM), 2006.

%H Alois P. Heinz, <a href="/A216499/b216499.txt">Table of n, a(n) for n = 0..1000</a>

%F a(0) = 0,

%F a(n) = max_{1<=i<=n} [C(i,3) +2*C(i,2)*(n-i) +i*C(n-i,2) +a(n-i)] for n>0.

%p a:= proc(n) option remember; `if`(n=0, 0, max(seq(

%p binomial(i, 3) +2*binomial(i, 2)*(n-i)+

%p i*binomial(n-i, 2) + a(n-i), i=1..n)))

%p end:

%p seq(a(n), n=0..70); # _Alois P. Heinz_, Jan 28 2016

%t a[0] = 0; a[n_] := a[n] = Max[Table[Binomial[i, 3] + 2*Binomial[i, 2]*(n-i) + i*Binomial[n-i, 2] + a[n-i], {i, 1, n}]]; Table[a[n], {n, 0, 70}] (* _Jean-François Alcover_, Oct 24 2016 *)

%Y Cf. A000292 (the analogous sequence for level-0 phylogenetic networks).

%K nonn

%O 0,4

%A _Jesper Jansson_, Sep 08 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)