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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A264868 Number of rooted tandem duplication trees on n gene segments. 5
1, 1, 2, 6, 22, 92, 420, 2042, 10404, 54954, 298648, 1660714, 9410772, 54174212, 316038060, 1864781388, 11111804604, 66782160002, 404392312896, 2465100947836, 15116060536540, 93184874448186, 577198134479356, 3590697904513792, 22425154536754776 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

REFERENCES

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

LINKS

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

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, Letter. On Counting Tandem Duplication Trees, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.

FORMULA

a(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*a(n-k) with a(1) = a(2) = 1 (Yang and Zhang).

For n >= 3, 1/2*a(n) = A086521(n) is the number of tandem duplication trees on n gene segments.

Main diagonal and row sums of A264869.

a(n) = Sum_{k=0..n-1} A291680(n-1,k). - Alois P. Heinz, Aug 29 2017

MAPLE

a:= proc(n) option remember;

       if n = 1 then 1 elif n = 2 then 1 else add((-1)^(k+1)*

          binomial(n+1-2*k, k)*a(n-k), k = 1..floor((n+1)/3))

       end if;

    end proc:

seq(a(n), n = 1..24);

MATHEMATICA

a[n_] := a[n] = If[n == 1, 1, If[n == 2, 1, Sum[(-1)^(k+1) Binomial[n+1-2k, k] a[n-k], {k, 1, Floor[(n+1)/3]}]]]; Array[a, 25] (* Jean-Fran├žois Alcover, May 29 2019 *)

PROG

(Python)

from sympy.core.cache import cacheit

from sympy import floor, binomial

@cacheit

def a(n): return 1 if n<3 else sum([(-1)**(k + 1)*binomial(n + 1 - 2*k, k)*a(n - k) for k in range(1, floor((n + 1)//3) + 1)])

print (map(a, range(1, 26))) # Indranil Ghosh, Aug 30 2017

CROSSREFS

Cf. A086521, A264869, A264870, A291680.

Sequence in context: A155866 A150273 A303923 * A001181 A130579 A279570

Adjacent sequences:  A264865 A264866 A264867 * A264869 A264870 A264871

KEYWORD

nonn,easy

AUTHOR

Peter Bala, Nov 27 2015

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 October 16 21:10 EDT 2019. Contains 328103 sequences. (Running on oeis4.)