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.

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,4

Comments

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

References

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

Links

Table of n, a(n) for n=2..56.

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.

Formula

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.

Example

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

Maple

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

Crossrefs

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

Sequence in context: A341695 A008238 A218870 * A292728 A365719 A096575

Adjacent sequences: A264866 A264867 A264868 * A264870 A264871 A264872

Keyword

nonn,tabl,easy

Author

Peter Bala, Nov 27 2015

Status

approved