login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..54.

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: A181530 A035362 A042957 * A131048 A119688 A126868

Adjacent sequences:  A264867 A264868 A264869 * A264871 A264872 A264873

KEYWORD

nonn,tabl,easy

AUTHOR

Peter Bala, Nov 27 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 20:21 EDT 2020. Contains 335473 sequences. (Running on oeis4.)