A264868 Number of rooted tandem duplication trees on n gene segments.

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

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

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

Cf. A086521, A264869, A264870, A291680.

Cf. A005773.

Sequence in context: A150273 A342292 A303923 * A342290 A342293 A342291

Adjacent sequences: A264865 A264866 A264867 * A264869 A264870 A264871

Keyword

nonn,easy

Author

Peter Bala, Nov 27 2015

Status

approved