[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a264869 -id:a264869
Displaying 1-4 of 4 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A264868
Number of rooted tandem duplication trees on n gene segments.
+10
5
1, 1, 2, 6, 22, 92, 420, 2042, 10404, 54954, 298648, 1660714, 9410772, 54174212, 316038060, 1864781388, 11111804604, 66782160002, 404392312896, 2465100947836, 15116060536540, 93184874448186, 577198134479356, 3590697904513792, 22425154536754776
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
Apparently a(n) is the number of words [d(0)d(1)d(2)...d(n)] where d(k) <= k (so d(0)=0) and if w(k-1) > w(k) then w(k-1) - w(k) = 1 (that is, descents by 2 or more are forbidden). - Joerg Arndt, Jan 26 2024
REFERENCES
Mathematics of Evolution and Phylogeny, O. Gascuel (ed.), Oxford University Press, 2005
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000
O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, The combinatorics of tandem duplication trees, Systematic Biology 52, (2003), 110-118.
J. Yang and L. Zhang, Letter. On Counting Tandem Duplication Trees, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.
FORMULA
a(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*a(n-k) with a(1) = a(2) = 1 (Yang and Zhang).
For n >= 3, (1/2)*a(n) = A086521(n) is the number of tandem duplication trees on n gene segments.
Main diagonal and row sums of A264869.
a(n) = Sum_{k=0..n-1} A291680(n-1,k). - Alois P. Heinz, Aug 29 2017
EXAMPLE
Form Joerg Arndt, Jan 26 2024: (Start)
The a(5) = 22 words as described in the comment are (dots denote zeros, leading zeros omitted):
1: [ . . . ]
2: [ . . 1 ]
3: [ . . 2 ]
4: [ . . 3 ]
5: [ . 1 . ]
6: [ . 1 1 ]
7: [ . 1 2 ]
8: [ . 1 3 ]
9: [ . 2 1 ]
10: [ . 2 2 ]
11: [ . 2 3 ]
12: [ 1 . . ]
13: [ 1 . 1 ]
14: [ 1 . 2 ]
15: [ 1 . 3 ]
16: [ 1 1 . ]
17: [ 1 1 1 ]
18: [ 1 1 2 ]
19: [ 1 1 3 ]
20: [ 1 2 1 ]
21: [ 1 2 2 ]
22: [ 1 2 3 ]
(End)
MAPLE
a:= proc(n) option remember;
if n = 1 then 1 elif n = 2 then 1 else add((-1)^(k+1)*
binomial(n+1-2*k, k)*a(n-k), k = 1..floor((n+1)/3))
end if;
end proc:
seq(a(n), n = 1..24);
MATHEMATICA
a[n_] := a[n] = If[n == 1, 1, If[n == 2, 1, Sum[(-1)^(k+1) Binomial[n+1-2k, k] a[n-k], {k, 1, Floor[(n+1)/3]}]]]; Array[a, 25] (* Jean-François Alcover, May 29 2019 *)
PROG
(Python)
from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def a(n):
return 1 if n<3 else sum([(-1)**(k + 1)*binomial(n + 1 - 2*k, k)*a(n - k) for k in range(1, (n + 1)//3 + 1)])
print([a(n) for n in range(1, 26)]) # Indranil Ghosh, Aug 30 2017
CROSSREFS
Cf. A086521, A264869, A264870, A291680.
Cf. A005773.
KEYWORD
nonn,easy
AUTHOR
Peter Bala, Nov 27 2015
STATUS
approved
A206464
Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.
+10
4
1, 1, 2, 4, 10, 26, 74, 218, 672, 2126, 6908, 22876, 77100, 263514, 911992, 3189762, 11261448, 40083806, 143713968, 518594034, 1882217168, 6867064856, 25172021144, 92666294090, 342467464612, 1270183943200, 4726473541216, 17640820790092, 66025467919972
(list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Catalan-RGS are strings with first digit d(0)=zero, and d(k+1) <= d(k)+1, falling factorial mixed-radix numbers have last digit <= 1, second last <= 2, etc.
The digits of the RGS are <= floor(n/2).
The first few terms are the same as for A089429.
Column k=0 of A264869. - Peter Bala, Nov 27 2015
a(n) = A291680(n+1,n+1). - Alois P. Heinz, Aug 29 2017
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
Conjecture: a(n) = Sum_{k = 0..floor(n/4)} (-1)^k * C(floor(n/2) + 1 - k, k + 1) * a(n - 1 - k), a(0) = 1. - Gionata Neri, Jun 17 2018
EXAMPLE
The a(5)=26 strings for n=5 are (dots for zeros):
1: [ . . . . . ]
2: [ . . . . 1 ]
3: [ . . . 1 . ]
4: [ . . . 1 1 ]
5: [ . . 1 . . ]
6: [ . . 1 . 1 ]
7: [ . . 1 1 . ]
8: [ . . 1 1 1 ]
9: [ . . 1 2 . ]
10: [ . . 1 2 1 ]
11: [ . 1 . . . ]
12: [ . 1 . . 1 ]
13: [ . 1 . 1 . ]
14: [ . 1 . 1 1 ]
15: [ . 1 1 . . ]
16: [ . 1 1 . 1 ]
17: [ . 1 1 1 . ]
18: [ . 1 1 1 1 ]
19: [ . 1 1 2 . ]
20: [ . 1 1 2 1 ]
21: [ . 1 2 . . ]
22: [ . 1 2 . 1 ]
23: [ . 1 2 1 . ]
24: [ . 1 2 1 1 ]
25: [ . 1 2 2 . ]
26: [ . 1 2 2 1 ]
MAPLE
b:= proc(i, l) option remember;
`if`(i<=0, 1, add(b(i-1, j), j=0..min(l+1, i)))
end:
a:= n-> b(n-1, 0):
seq(a(n), n=0..40); # Alois P. Heinz, Feb 08 2012
MATHEMATICA
b[i_, l_] := b[i, l] = If[i <= 0, 1, Sum[b[i-1, j], {j, 0, Min[l+1, i]}]];
a[n_] := b[n-1, 0];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)
CROSSREFS
Cf. A080935, A080936, A264869, A291680.
KEYWORD
nonn
AUTHOR
Joerg Arndt, Feb 08 2012
STATUS
approved
A086521
Number of tandem duplication trees on n duplicated gene segments.
+10
3
1, 1, 3, 11, 46, 210, 1021, 5202, 27477, 149324, 830357, 4705386, 27087106, 158019030, 932390694, 5555902302, 33391080001, 202196156448, 1232550473918, 7558030268270, 46592437224093, 288599067239678, 1795348952256896
(list; graph; refs; listen; history; text; internal format)
OFFSET
2,3
COMMENTS
For n > 2, 2*a(n) is the number of rooted tandem duplication trees. See A264869.
REFERENCES
O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005
LINKS
Table of n, a(n) for n=2..24.
O. Gascuel, M. Hendy, A. Jean-Marie and R. McLachlan, (2003) The combinatorics of tandem duplication trees, Systematic Biology 52, 110-118.
J. Yang and L. Zhang, On Counting Tandem Duplication Trees, Molecular Biology and Evolution, Volume 21, Issue 6, (2004) 1160-1163.
FORMULA
a(n) = b(n+1, n-1), where b(n, 0) = b(n-1, 0) + b(n-1, 1); b(n, k) = b(n-1, k+1) + b(n, k-1), for k = 1, ..., n-2; with initial values b(2, 0) = 1, b(3, 0) = 0, b(3, 1) = 1.
For n >= 2, a(n) = b(n)/2, where b(n) = Sum_{k = 1..floor((n + 1)/3)} (-1)^(k + 1)*binomial(n + 1 - 2*k,k)*b(n-k) with b(1) = b(2) = 1 (Yang and Zhang). - Peter Bala, Nov 27 2015
EXAMPLE
a(5) = 11, so there are 11 binary leaf labeled trees on 5 duplicate genes. As there are 15 binary leaf labeled trees, this means not all binary leaf labeled trees can represent a gene duplication tree.
MAPLE
with(combinat):
b := proc (n) option remember;
if n = 2 then 2 elif n = 3 then 2 else add((-1)^(k+1)*binomial(n+1-2*k, k)*b(n-k), k = 1..floor((n+1)/3)) end if; end proc:
seq(b(n)/2, n = 2..24); # Peter Bala, Nov 27 2015
CROSSREFS
Cf. A264868, A264869, A264870.
KEYWORD
nonn,easy
AUTHOR
Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003
EXTENSIONS
More terms from David Wasserman, Mar 11 2005
STATUS
approved
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.
+10
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.
KEYWORD
nonn,tabl,easy
AUTHOR
Peter Bala, Nov 27 2015
STATUS
approved
page 1

Search completed in 0.012 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified October 5 14:13 EDT 2024. Contains 376560 sequences.
License Agreements, Terms of Use, Privacy Policy