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.

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

Author

Peter Bala, Nov 27 2015

Keywords

• nonn
• tabl
• easy

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.

Examples

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

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.

Crossrefs

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

Programs

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

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.