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

Author

Peter Bala, Nov 27 2015

Keywords

• nonn
• tabl
• easy

Comments

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

Examples

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

References

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

Links

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

Crossrefs

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

Programs

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

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.