A086521 -id:A086521 - cp's OEIS frontend

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

Peter Bala, Nov 27 2015

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

			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)

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

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.

Cf. A086521, A264869, A264870, A291680.

Cf. A005773.

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);

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

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

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

A264869 Triangular array: For n >= 2 and 0 <= k <= n - 2, T(n, k) equals the number of rooted duplication trees on n gene segments whose leftmost visible duplication event is (k, r), for 1 <= r <= (n - k)/2.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 4, 6, 6, 6, 10, 16, 22, 22, 22, 26, 48, 70, 92, 92, 92, 74, 144, 236, 328, 420, 420, 420, 218, 454, 782, 1202, 1622, 2042, 2042, 2042, 672, 1454, 2656, 4278, 6320, 8362, 10404, 10404, 10404, 2126, 4782, 9060, 15380, 23742, 34146, 44550, 54954, 54954, 54954

Offset: 2

Peter Bala, Nov 27 2015

See Figure 3(a) in Gascuel et al. (2003).

			Triangle begins
  n\k|   0    1    2    3    4    5    6    7
  ---+---------------------------------------
   2 |   1
   3 |   1    1
   4 |   2    2    2
   5 |   4    6    6    6
   6 |  10   16   22   22   22
   7 |  26   48   70   92   92   92
   8 |  74  144  236  328  420  420  420
   9 | 218  454  782 1202 1622 2042 2042 2042
  ...

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

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

Cf. A206464 (column 0), A264868 (row sums and main diagonal), A086521.

A264869 := proc (n, k) option remember;
`if`(n <= 2, 1, add(A264869(n - 1, j), j = 0 .. min(k + 1, n - 3))) end proc:
seq(seq(A264869(n, k), k = 0..n - 2), n = 2..11);

T(n,k) = Sum_{j = 0.. k+1} T(n-1,j) for n >= 3, 0 <= k <= n - 2, with T(2,0) = 1 and T(n,k) = 0 for k >= n - 1.

T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 3, 1 <= k <= n - 2.

A264870 Triangular array: For n >= 2 and 0 < k <= n - 2, T(n, k) equals the number of (unrooted) duplication trees on n gene segments that are canonical and whose leftmost visible duplication event is (k, r), for 1 <= r <= (n - k)/2.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 3, 3, 3, 5, 8, 11, 11, 11, 13, 24, 35, 46, 46, 46, 37, 72, 118, 164, 210, 210, 210, 109, 227, 391, 601, 811, 1021, 1021, 1021, 336, 727, 1328, 2139, 3160, 4181, 5202, 5202, 5202, 1063, 2391, 4530, 7690, 11871, 17073, 22275, 27477, 27477, 27477

Offset: 0

Peter Bala, Nov 27 2015

See Figure 3(b) in Gascuel et al. (2003).
From row 4 onwards, the entries are one-half the corresponding entries in A264879.
Row sums give the number of unrooted duplication trees on n gene segments, A086521.

			Triangle begins
n\k|   0    1    2    3    4     5     6     7
----------------------------------------------
.2.|   1
.3.|   0    1
.4.|   1    1    1
.5.|   2    3    3    3
.6.|   5    8   11   11   11
.7.|  13   24   35   46   46    46
.8.|  37   72  118  164  210   210   210
.9.| 109  227  391  601  811  1021  1021  1021
...

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

O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, The combinatorics of tandem duplication trees, Systematic Biology 52, 110-118, (2003).
J. Yang and L. Zhang, On Counting Tandem Duplication Trees", Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.

Cf. A086521 (row sums), A264868, A264869.

A264870 := proc (n, k) option remember;
`if`(n = 3 and k = 0, 0, `if`(n <= 4 and k <= n-2, 1, `if`(k > n - 2, 0, add(A264870(n-1, j), j = 0..min(k+1, n))))) end proc:
seq(seq(A264870(n, k), k = 0..n-2), n = 2..11);

T(n,k) = Sum_{j = 0..k+1} T(n-1,j) for n >= 4, 0 <= k <= n - 2, with T(2,0) = T(3,1) = 1, T(3,0) = 0 and T(n,k) = 0 for k >= n - 1.

T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 4, 1 <= k <= n - 2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A264869 Triangular array: For n >= 2 and 0 <= k <= n - 2, T(n, k) equals the number of rooted duplication trees on n gene segments whose leftmost visible duplication event is (k, r), for 1 <= r <= (n - k)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A264870 Triangular array: For n >= 2 and 0 < k <= n - 2, T(n, k) equals the number of (unrooted) duplication trees on n gene segments that are canonical and whose leftmost visible duplication event is (k, r), for 1 <= r <= (n - k)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula