A264868 -id:A264868

Search: a264868 -id:a264868

Displaying 1-4 of 4 results found.

page 1

A291680

Number T(n,k) of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 2; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

+10
15

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 9, 8, 4, 0, 1, 25, 36, 20, 10, 0, 1, 71, 156, 108, 58, 26, 0, 1, 205, 666, 586, 340, 170, 74, 0, 1, 607, 2860, 3098, 2014, 1078, 528, 218, 0, 1, 1833, 12336, 16230, 11888, 6772, 3550, 1672, 672, 0, 1, 5635, 53518, 85150, 69274, 42366, 23284, 11840, 5454, 2126

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

COMMENTS

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

FORMULA

T(n,n) = A206464(n-1) for n>0.

Sum_{k=0..n} T(n,k) = A264868(n+1).

EXAMPLE

T(4,1) = 1: 1234.

T(4,2) = 9: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431.

T(4,3) = 8: 1423, 1432, 3124, 3142, 3214, 3241, 3412, 3421.

T(4,4) = 4: 4213, 4231, 4312, 4321.

T(5,5) = 10: 53124, 53142, 53214, 53241, 53412, 53421, 54213, 54231, 54312, 54321.

Triangle T(n,k) begins:

0, 1;

0, 1, 1;

0, 1, 3, 2;

0, 1, 9, 8, 4;

0, 1, 25, 36, 20, 10;

0, 1, 71, 156, 108, 58, 26;

0, 1, 205, 666, 586, 340, 170, 74;

0, 1, 607, 2860, 3098, 2014, 1078, 528, 218;

...

MAPLE

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,

add(b(u-j, o+j-1, k), j=1..min(2, u))+

add(b(u+j-1, o-j, k), j=1..min(k, o)))

end:

T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):

seq(seq(T(n, k), k=0..n), n=0..12);

MATHEMATICA

b[u_, o_, k_] := b[u, o, k] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, k], {j, 1, Min[2, u]}] + Sum[b[u+j-1, o-j, k], {j, 1, Min[k, o]}]];

T[n_, k_] := b[0, n, k] - If[k == 0, 0, b[0, n, k-1]];

Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 29 2019, after Alois P. Heinz *)

PROG

(Python)

from sympy.core.cache import cacheit

@cacheit

def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(2, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])

def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))

for n in range(13): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 30 2017

CROSSREFS

Columns k=0-10 give: A000007, A057427, A291683, A321110, A321111, A321112, A321113, A321114, A321115, A321116, A321117.

T(2n,n) gives A320290.

Cf. A203717, A206464, A264868.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Aug 29 2017

STATUS

approved

A264869

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.

+10
5

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, 420, 420, 420, 218, 454, 782, 1202, 1622, 2042, 2042, 2042, 672, 1454, 2656, 4278, 6320, 8362, 10404, 10404, 10404, 2126, 4782, 9060, 15380, 23742, 34146, 44550, 54954, 54954, 54954

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

2,4

COMMENTS

See Figure 3(a) in Gascuel et al. (2003).

REFERENCES

O. Gascuel (Ed.), Mathematics of Evolution and Phylogeny, Oxford University Press, 2005

LINKS

Table of n, a(n) for n=2..56.

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

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.

T(n,k) = T(n,k-1) + T(n-1,k+1) for n >= 3, 1 <= k <= n - 2.

EXAMPLE

Triangle begins

n\k| 0 1 2 3 4 5 6 7

---+---------------------------------------

2 | 1

3 | 1 1

4 | 2 2 2

5 | 4 6 6 6

6 | 10 16 22 22 22

7 | 26 48 70 92 92 92

8 | 74 144 236 328 420 420 420

9 | 218 454 782 1202 1622 2042 2042 2042

...

MAPLE

A264869 := proc (n, k) option remember;

`if`(n <= 2, 1, add(A264869(n - 1, j), j = 0 .. min(k + 1, n - 3))) end proc:

seq(seq(A264869(n, k), k = 0..n - 2), n = 2..11);

CROSSREFS

Cf. A206464 (column 0), A264868 (row sums and main diagonal), A086521.

KEYWORD

nonn,tabl,easy

AUTHOR

Peter Bala, Nov 27 2015

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.008 seconds