login
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.
5
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
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
KEYWORD
nonn,tabl,easy
AUTHOR
Peter Bala, Nov 27 2015
STATUS
approved