| Displaying 1-4 of 4 results found.
page
1
Number of tandem duplication trees on n duplicated gene segments.
+0
3
1, 1, 3, 11, 46, 210, 1021, 5202, 27477, 149324, 830357, 4705386, 27087106, 158019030, 932390694, 5555902302, 33391080001, 202196156448, 1232550473918, 7558030268270, 46592437224093, 288599067239678, 1795348952256896
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
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:
AUTHOR
Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003
Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.
+0
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
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.
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):
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];
Number of rooted tandem duplication trees on n gene segments.
+0
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
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
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.
EXAMPLE
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)])
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.
+0
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
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
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);
Search completed in 0.011 seconds
| 