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!)
A264868 Number of rooted tandem duplication trees on n gene segments. 5

%I #37 Jan 26 2024 10:18:42

%S 1,1,2,6,22,92,420,2042,10404,54954,298648,1660714,9410772,54174212,

%T 316038060,1864781388,11111804604,66782160002,404392312896,

%U 2465100947836,15116060536540,93184874448186,577198134479356,3590697904513792,22425154536754776

%N Number of rooted tandem duplication trees on n gene segments.

%C Apparently a(n) is the number of words [d(0)d(1)d(2)...d(n)] where d(k) <= k (so d(0)=0) and if w(k-1) > w(k) then w(k-1) - w(k) = 1 (that is, descents by 2 or more are forbidden). - _Joerg Arndt_, Jan 26 2024

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

%H Alois P. Heinz, <a href="/A264868/b264868.txt">Table of n, a(n) for n = 1..1000</a>

%H O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, <a href="http://www.massey.ac.nz/~rmclachl/duplications.pdf">The combinatorics of tandem duplication trees</a>, Systematic Biology 52, (2003), 110-118.

%H J. Yang and L. Zhang, <a href="http://dx.doi.org/10.1093/molbev/msh115">Letter. On Counting Tandem Duplication Trees</a>, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.

%F 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).

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

%F Main diagonal and row sums of A264869.

%F a(n) = Sum_{k=0..n-1} A291680(n-1,k). - _Alois P. Heinz_, Aug 29 2017

%e Form _Joerg Arndt_, Jan 26 2024: (Start)

%e The a(5) = 22 words as described in the comment are (dots denote zeros, leading zeros omitted):

%e 1: [ . . . ]

%e 2: [ . . 1 ]

%e 3: [ . . 2 ]

%e 4: [ . . 3 ]

%e 5: [ . 1 . ]

%e 6: [ . 1 1 ]

%e 7: [ . 1 2 ]

%e 8: [ . 1 3 ]

%e 9: [ . 2 1 ]

%e 10: [ . 2 2 ]

%e 11: [ . 2 3 ]

%e 12: [ 1 . . ]

%e 13: [ 1 . 1 ]

%e 14: [ 1 . 2 ]

%e 15: [ 1 . 3 ]

%e 16: [ 1 1 . ]

%e 17: [ 1 1 1 ]

%e 18: [ 1 1 2 ]

%e 19: [ 1 1 3 ]

%e 20: [ 1 2 1 ]

%e 21: [ 1 2 2 ]

%e 22: [ 1 2 3 ]

%e (End)

%p a:= proc(n) option remember;

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

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

%p end if;

%p end proc:

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

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

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import binomial

%o @cacheit

%o def a(n):

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

%o print([a(n) for n in range(1, 26)]) # _Indranil Ghosh_, Aug 30 2017

%Y Cf. A086521, A264869, A264870, A291680.

%Y Cf. A005773.

%K nonn,easy

%O 1,3

%A _Peter Bala_, Nov 27 2015

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 13:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)