login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216499 The maximum possible number of rooted triplets consistent with any galled-tree (level-1 phylogenetic network) containing exactly n leaves. 3
0, 0, 0, 2, 7, 16, 32, 55, 87, 130, 184, 252, 335, 433, 550, 686, 842, 1022, 1224, 1451, 1706, 1987, 2299, 2642, 3015, 3426, 3870, 4349, 4870, 5428, 6028, 6672, 7357, 8091, 8871, 9696, 10576, 11505, 12486, 13525, 14616, 15766, 16976, 18242, 19574, 20968 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

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

REFERENCES

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

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.

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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

a(0) = 0,

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.

MAPLE

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

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

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

    end:

seq(a(n), n=0..70);  # Alois P. Heinz, Jan 28 2016

MATHEMATICA

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

CROSSREFS

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

Sequence in context: A225311 A241526 A074470 * A228189 A023550 A130869

Adjacent sequences:  A216496 A216497 A216498 * A216500 A216501 A216502

KEYWORD

nonn

AUTHOR

Jesper Jansson, Sep 08 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 18:42 EDT 2017. Contains 286926 sequences.