cp's OEIS Frontend

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.

%I A264870 #9 Nov 29 2015 14:04:19
%S A264870 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 A264870 210,210,109,227,391,601,811,1021,1021,1021,336,727,1328,2139,3160,
%U A264870 4181,5202,5202,5202,1063,2391,4530,7690,11871,17073,22275,27477,27477,27477
%N 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.
%C A264870 See Figure 3(b) in Gascuel et al. (2003).
%C A264870 From row 4 onwards, the entries are one-half the corresponding entries in A264879.
%C A264870 Row sums give the number of unrooted duplication trees on n gene segments, A086521.
%D A264870 O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
%H A264870 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 A264870 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 A264870 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 A264870 T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 4, 1 <= k <= n - 2.
%e A264870 Triangle begins
%e A264870 n\k|   0    1    2    3    4     5     6     7
%e A264870 ----------------------------------------------
%e A264870 .2.|   1
%e A264870 .3.|   0    1
%e A264870 .4.|   1    1    1
%e A264870 .5.|   2    3    3    3
%e A264870 .6.|   5    8   11   11   11
%e A264870 .7.|  13   24   35   46   46    46
%e A264870 .8.|  37   72  118  164  210   210   210
%e A264870 .9.| 109  227  391  601  811  1021  1021  1021
%e A264870 ...
%p A264870 A264870 := proc (n, k) option remember;
%p A264870 `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 A264870 seq(seq(A264870(n, k), k = 0..n-2), n = 2..11);
%Y A264870 Cf. A086521 (row sums), A264868, A264869.
%K A264870 nonn,tabl,easy
%O A264870 0,7
%A A264870 _Peter Bala_, Nov 27 2015