%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
|