A264868 -id:A264868 - cp's OEIS frontend

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.

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

Offset: 0

Alois P. Heinz, Aug 29 2017

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.

			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:
  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;
  ...

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

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.

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);

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 *)

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

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

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

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.

Original entry on oeis.org

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

Offset: 2

Peter Bala, Nov 27 2015

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

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

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

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.

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

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);

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.

A086521 Number of tandem duplication trees on n duplicated gene segments.

Original entry on oeis.org

1, 1, 3, 11, 46, 210, 1021, 5202, 27477, 149324, 830357, 4705386, 27087106, 158019030, 932390694, 5555902302, 33391080001, 202196156448, 1232550473918, 7558030268270, 46592437224093, 288599067239678, 1795348952256896

Offset: 2

Michael D Hendy (m.hendy(AT)massey.ac.nz), Sep 10 2003

For n > 2, 2*a(n) is the number of rooted tandem duplication trees. See A264869.

			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.

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

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.

Cf. A264868, A264869, A264870.

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

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

More terms from David Wasserman, Mar 11 2005

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.

Original entry on oeis.org

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

Offset: 0

Peter Bala, Nov 27 2015

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.

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

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

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.

Cf. A086521 (row sums), A264868, A264869.

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);

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.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A086521 Number of tandem duplication trees on n duplicated gene segments.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula