|
%I #14 Aug 29 2017 12:18:52
%S 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,
%T 420,420,420,218,454,782,1202,1622,2042,2042,2042,672,1454,2656,4278,
%U 6320,8362,10404,10404,10404,2126,4782,9060,15380,23742,34146,44550,54954,54954,54954
%N 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.
%C See Figure 3(a) in Gascuel et al. (2003).
%D O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
%H O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, (2003) <a href="http://www.massey.ac.nz/~rmclachl/duplications.pdf">The combinatorics of tandem duplication trees</a>, Systematic Biology 52, 110-118.
%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 >= 3, 0 <= k <= n - 2, with T(2,0) = 1 and T(n,k) = 0 for k >= n - 1.
%F T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 3, 1 <= k <= n - 2.
%e Triangle begins
%e n\k| 0 1 2 3 4 5 6 7
%e ---+---------------------------------------
%e 2 | 1
%e 3 | 1 1
%e 4 | 2 2 2
%e 5 | 4 6 6 6
%e 6 | 10 16 22 22 22
%e 7 | 26 48 70 92 92 92
%e 8 | 74 144 236 328 420 420 420
%e 9 | 218 454 782 1202 1622 2042 2042 2042
%e ...
%p A264869 := proc (n, k) option remember;
%p `if`(n <= 2, 1, add(A264869(n - 1, j), j = 0 .. min(k + 1, n - 3))) end proc:
%p seq(seq(A264869(n, k), k = 0..n - 2), n = 2..11);
%Y Cf. A206464 (column 0), A264868 (row sums and main diagonal), A086521.
%K nonn,tabl,easy
%O 2,4
%A _Peter Bala_, Nov 27 2015
|
