|
%I #9 Nov 29 2015 14:04:19
%S 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,
%T 210,210,109,227,391,601,811,1021,1021,1021,336,727,1328,2139,3160,
%U 4181,5202,5202,5202,1063,2391,4530,7690,11871,17073,22275,27477,27477,27477
%N 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.
%C See Figure 3(b) in Gascuel et al. (2003).
%C From row 4 onwards, the entries are one-half the corresponding entries in A264879.
%C Row sums give the number of unrooted duplication trees on n gene segments, A086521.
%D O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
%H O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, <a href="http://www.massey.ac.nz/~rmclachl/duplications.pdf">The combinatorics of tandem duplication trees</a>, Systematic Biology 52, 110-118, (2003).
%H J. Yang and L. Zhang, <a href="http://dx.doi.org/10.1093/molbev/msh115">On Counting Tandem Duplication Trees"</a>, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.
%F 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.
%F T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 4, 1 <= k <= n - 2.
%e Triangle begins
%e n\k| 0 1 2 3 4 5 6 7
%e ----------------------------------------------
%e .2.| 1
%e .3.| 0 1
%e .4.| 1 1 1
%e .5.| 2 3 3 3
%e .6.| 5 8 11 11 11
%e .7.| 13 24 35 46 46 46
%e .8.| 37 72 118 164 210 210 210
%e .9.| 109 227 391 601 811 1021 1021 1021
%e ...
%p A264870 := proc (n, k) option remember;
%p `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:
%p seq(seq(A264870(n, k), k = 0..n-2), n = 2..11);
%Y Cf. A086521 (row sums), A264868, A264869.
%K nonn,tabl,easy
%O 0,7
%A _Peter Bala_, Nov 27 2015
|
