A206464 -id:A206464 - 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.

A351642 Number of length n word structures with all distinct runs using an infinite alphabet.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 74, 218, 668, 2116, 6928, 23254, 79998, 281694, 1011956, 3704900, 13815692, 52386978, 201787950, 789178950, 3130824160, 12589367840, 51287685476, 211557376938, 883067740514, 3728494418330, 15916998678040, 68672820917088, 299331260431104

Offset: 0

Andrew Howroyd, Feb 15 2022

nonn

Permuting the symbols will not change the structure.

Equivalently, a(n) is the number of restricted growth strings [s(0), s(1), ..., s(n-1)] where s(0)=0 and s(i) <= 1 + max(prefix) for i >= 1 and all runs are distinct.

			The a(4) = 10 words are 1111, 1112, 1121, 1122, 1211, 1222, 1123, 1223, 1233, 1234.

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row sums of A351641.
The initial terms are similar to A206464.
Cf. A351200, A351638.

\\ See A351641 for R, S.
seq(n)={my(q=S(n)); concat([1], sum(k=1, n, R(q^k-1)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)/r!) )); }

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

A351642 Number of length n word structures with all distinct runs using an infinite alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI