login
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
OFFSET
1,3
COMMENTS
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
REFERENCES
Mathematics of Evolution and Phylogeny, O. Gascuel (ed.), Oxford University Press, 2005
LINKS
O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, The combinatorics of tandem duplication trees, Systematic Biology 52, (2003), 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
EXAMPLE
Form Joerg Arndt, Jan 26 2024: (Start)
The a(5) = 22 words as described in the comment are (dots denote zeros, leading zeros omitted):
1: [ . . . ]
2: [ . . 1 ]
3: [ . . 2 ]
4: [ . . 3 ]
5: [ . 1 . ]
6: [ . 1 1 ]
7: [ . 1 2 ]
8: [ . 1 3 ]
9: [ . 2 1 ]
10: [ . 2 2 ]
11: [ . 2 3 ]
12: [ 1 . . ]
13: [ 1 . 1 ]
14: [ 1 . 2 ]
15: [ 1 . 3 ]
16: [ 1 1 . ]
17: [ 1 1 1 ]
18: [ 1 1 2 ]
19: [ 1 1 3 ]
20: [ 1 2 1 ]
21: [ 1 2 2 ]
22: [ 1 2 3 ]
(End)
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 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, (n + 1)//3 + 1)])
print([a(n) for n in range(1, 26)]) # Indranil Ghosh, Aug 30 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Peter Bala, Nov 27 2015
STATUS
approved