login
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.
3
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,7
COMMENTS
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.
REFERENCES
O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
LINKS
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.
FORMULA
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.
EXAMPLE
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
...
MAPLE
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);
CROSSREFS
Cf. A086521 (row sums), A264868, A264869.
Sequence in context: A042957 A341074 A343885 * A346048 A131048 A119688
KEYWORD
nonn,tabl,easy
AUTHOR
Peter Bala, Nov 27 2015
STATUS
approved