login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A086521 Number of tandem duplication trees on n duplicated gene segments. 3
1, 1, 3, 11, 46, 210, 1021, 5202, 27477, 149324, 830357, 4705386, 27087106, 158019030, 932390694, 5555902302, 33391080001, 202196156448, 1232550473918, 7558030268270, 46592437224093, 288599067239678, 1795348952256896 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

For n > 2, 2*a(n) is the number of rooted tandem duplication trees. See A264869.

REFERENCES

O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005

LINKS

Table of n, a(n) for n=2..24.

O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, (2003) The combinatorics of tandem duplication trees, Systematic Biology 52, 110-118.

J. Yang and L. Zhang, On Counting Tandem Duplication Trees, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.

FORMULA

a(n) = b(n+1, n-1), where b(n, 0) = b(n-1, 0) + b(n-1, 1); b(n, k) = b(n-1, k+1) + b(n, k-1), for k = 1, ..., n-2; with initial values b(2, 0) = 1, b(3, 0) = 0, b(3, 1) = 1.

For n >= 2, a(n) = b(n)/2, where b(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*b(n-k) with b(1) = b(2) = 1 (Yang and Zhang). - Peter Bala, Nov 27 2015

EXAMPLE

a(5) = 11, so there are 11 binary leaf labeled trees on 5 duplicate genes. As there are 15 binary leaf labeled trees, this means not all binary leaf labeled trees can represent a gene duplication tree.

MAPLE

with(combinat):

b := proc (n) option remember;

if n = 2 then 2 elif n = 3 then 2 else add((-1)^(k+1)*binomial(n+1-2*k, k)*b(n-k), k = 1..floor((n+1)/3)) end if; end proc:

seq(b(n)/2, n = 2..24); # Peter Bala, Nov 27 2015

CROSSREFS

Cf. A264868, A264869, A264870.

Sequence in context: A287891 A233389 A281548 * A225293 A046996 A248426

Adjacent sequences:  A086518 A086519 A086520 * A086522 A086523 A086524

KEYWORD

nonn,easy

AUTHOR

Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003

EXTENSIONS

More terms from David Wasserman, Mar 11 2005

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 13:47 EDT 2021. Contains 347617 sequences. (Running on oeis4.)