A291722 -id:A291722 - cp's OEIS frontend

A258829 Number T(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 11, 3, 1, 0, 16, 38, 28, 4, 1, 0, 61, 263, 130, 62, 5, 1, 0, 272, 1260, 1263, 340, 129, 6, 1, 0, 1385, 10871, 8090, 4734, 819, 261, 7, 1, 0, 7936, 66576, 88101, 33855, 16066, 1890, 522, 8, 1, 0, 50521, 694599, 724189, 495371, 127538, 52022, 4260, 1040, 9, 1

Offset: 0

Alois P. Heinz, Jun 11 2015

			p = 1432 is counted by T(4,2) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.
q = 4321 is not counted by any T(4,k) because the up-down signature of 0,q = 04321 is 1,-1,-1,-1 with partial sums 1,0,-1,-2.
T(4,1) = 5: 2143, 3142, 3241, 4132, 4231.
T(4,2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.
T(4,3) = 3: 1243, 1342, 2341.
T(4,4) = 1: 1234.
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,     1;
  0,    2,     2,    1;
  0,    5,    11,    3,    1;
  0,   16,    38,   28,    4,   1;
  0,   61,   263,  130,   62,   5,   1;
  0,  272,  1260, 1263,  340, 129,   6, 1;
  0, 1385, 10871, 8090, 4734, 819, 261, 7, 1;

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

Columns k=0-10 give: A000007, A000111 for n>0, A259213, A316390, A316391, A316392, A316393, A316394, A316395, A316396, A316397.
Row sums give A258830.
T(2n,n) gives A266947.
Cf. A262124, A262125, A262163, A291722, A316292, A316293.

b:= proc(u, o, c, k) option remember;
      `if`(c<0 or c>k, 0, `if`(u+o=0, 1,
       add(b(u-j, o-1+j, c+1, k), j=1..u)+
       add(b(u+j-1, o-j, c-1, k), j=1..o)))
    end:
A:= (n, k)-> b(n, 0$2, k):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

b[u_, o_, c_, k_] := b[u, o, c, k] = If[c < 0 || c > k, 0, If[u + o == 0, 1, Sum[b[u - j, o - 1 + j, c + 1, k], {j, 1, u}] + Sum[b[u + j - 1, o - j, c - 1, k], {j, 1, o}]]];
A[n_, k_] := b[n, 0, 0, k];
T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k - 1]];
Table[T[n, k], {n, 0, 12}, { k, 0, n}] // Flatten (* Jean-François Alcover, Jun 09 2018, after Alois P. Heinz *)

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

A263776 Triangle read by rows: T(n,k) (n>=0, 0<=k<=A002620(n-1)) is the number of permutations of [n] with k nestings.

Original entry on oeis.org

1, 1, 2, 5, 1, 14, 8, 2, 42, 45, 25, 7, 1, 132, 220, 198, 112, 44, 12, 2, 429, 1001, 1274, 1092, 700, 352, 140, 42, 9, 1, 1430, 4368, 7280, 8400, 7460, 5392, 3262, 1664, 716, 256, 74, 16, 2, 4862, 18564, 38556, 56100, 63648, 59670, 47802, 33338, 20466, 11115

Offset: 0

Christian Stump, Oct 26 2015

Row sums give A000142.
First column gives A000108.
Also the number of permutations of [n] with k crossings (see Corteel, Proposition 4).
Also the number of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 13-2 (alternatively: 2-13, 2-31, or 31-2). - Alois P. Heinz, Nov 14 2015

			Triangle begins:
0 :   1;
1 :   1;
2 :   2;
3 :   5,    1;
4 :  14,    8,    2;
5 :  42,   45,   25,    7,   1;
6 : 132,  220,  198,  112,  44,  12,   2;
7 : 429, 1001, 1274, 1092, 700, 352, 140, 42, 9, 1;
...

Alois P. Heinz, Rows n = 0..50, flattened
A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, arXiv:math/0110036 [math.CO], 2001.
S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math 38 (2007) 149-163.
FindStat - Combinatorial Statistic Finder, The number of nestings of a permutation, The number of crossings of a permutation
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.
Lucas Sá and Antonio M. García-García, The Wishart-Sachdev-Ye-Kitaev model: Q-Laguerre spectral density and quantum chaos, arXiv:2104.07647 [hep-th], 2021.

Columns k=0-10 give: A000108, A002696, A094218, A094219, A120812, A120813, A120814, A120815, A120816, A264496, A264497.

Cf. A000142, A001754, A002620, A260665, A260670, A287328, A291722.

b:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(b(u-j, o+j-1), j=1..u)+
       add(expand(b(u+j-1, o-j)*x^(j-1)), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);  # Alois P. Heinz, Nov 14 2015

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[u-j, o+j-1], {j, 1, u}] + Sum[Expand[b[u+j-1, o-j]*x^(j-1)], {j, 1, o}]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[ T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

Sum_{k>0} k * T(n,k) = A001754(n).

T(n,n) = A287328(n). - Alois P. Heinz, Aug 31 2017

More terms from Alois P. Heinz, Oct 26 2015

A303697 Number T(n,k) of permutations p of [n] whose difference between sum of up-jumps and sum of down-jumps equals k; triangle T(n,k), n>=0, min(0,1-n)<=k<=max(0,n-1), read by rows.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 4, 5, 4, 5, 4, 1, 1, 11, 19, 19, 20, 19, 19, 11, 1, 1, 26, 82, 100, 101, 100, 101, 100, 82, 26, 1, 1, 57, 334, 580, 619, 619, 620, 619, 619, 580, 334, 57, 1, 1, 120, 1255, 3394, 4339, 4420, 4421, 4420, 4421, 4420, 4339, 3394, 1255, 120, 1

Offset: 0

Alois P. Heinz, Apr 28 2018

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.

			Triangle T(n,k) begins:
:                               1                             ;
:                               1                             ;
:                          1,   0,   1                        ;
:                     1,   1,   2,   1,   1                   ;
:                1,   4,   5,   4,   5,   4,   1              ;
:           1,  11,  19,  19,  20,  19,  19,  11,   1         ;
:      1,  26,  82, 100, 101, 100, 101, 100,  82,  26,  1     ;
:  1, 57, 334, 580, 619, 619, 620, 619, 619, 580, 334, 57, 1  ;

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

Row sums give A000142.

Cf. A000295, A001720, A005165, A008292, A081285, A153229, A291680, A291684, A291722, A316292, A316293, A321316.

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1)*x^(-j), j=1..u)+
      add(b(u+j-1, o-j)*x^( j), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=ldegree(p)..degree(p)))(
        `if`(n=0, 1, add(b(j-1, n-j), j=1..n))):
seq(T(n), n=0..12);

b[u_, o_] := b[u, o] = Expand[If[u+o == 0, 1,
     Sum[b[u-j, o+j-1] x^-j, {j, 1, u}] +
     Sum[b[u+j-1, o-j] x^j, {j, 1, o}]]];
T[0] = {1};
T[n_] := x^n Sum[b[j-1, n-j], {j, 1, n}] // CoefficientList[#, x]& // Rest;
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Feb 20 2021, after Alois P. Heinz *)

T(n,0) = A153229(n) for n > 0.
T(n,1) = A005165(n-1) for n > 0.
T(n+1,n-1) = A000295(n).
T(n,k) = T(n,-k).
Sum_{k=0..n-1} k^2 * T(n,k) = A001720(n+2) for n>1.

A316292 Number T(n,k) of permutations p of [n] such that k is the maximum of the partial sums of the signed up-down jump sequence of 0,p; triangle T(n,k), n>=0, ceiling((sqrt(1+8*n)-1)/2)<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 2, 1, 5, 8, 16, 5, 50, 65, 1, 79, 314, 326, 69, 872, 2142, 1957, 34, 1539, 8799, 16248, 13700, 9, 1823, 24818, 89273, 137356, 109601, 1, 1494, 50561, 355271, 947713, 1287350, 986410, 856, 76944, 1070455, 4923428, 10699558, 13281458, 9864101

Offset: 0

Alois P. Heinz, Jun 28 2018

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.

			Triangle T(n,k) begins:
: 1;
:    1;
:       2;
:       1, 5;
:          8, 16;
:          5, 50,   65;
:          1, 79,  314,   326;
:             69,  872,  2142,   1957;
:             34, 1539,  8799,  16248,  13700;
:              9, 1823, 24818,  89273, 137356,  109601;
:              1, 1494, 50561, 355271, 947713, 1287350, 986410;

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

Row sums give A000142.
Column sums give A316294.
Main diagonal gives A000522.
Cf. A002024, A123578, A258829, A291722, A303697, A316293 (same read by columns).

b:= proc(u, o, c, k) option remember;
      `if`(c>k, 0, `if`(u+o=0, 1,
       add(b(u-j, o-1+j, c+j, k), j=1..u)+
       add(b(u+j-1, o-j, c-j, k), j=1..o)))
    end:
T:= (n, k)-> b(n, 0$2, k) -`if`(k=0, 0, b(n, 0$2, k-1)):
seq(seq(T(n, k), k=ceil((sqrt(1+8*n)-1)/2)..n), n=0..14);

b[u_, o_, c_, k_] := b[u, o, c, k] =
     If[c > k, 0, If[u + o == 0, 1,
     Sum[b[u - j, o - 1 + j, c + j, k], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, c - j, k], {j, 1, o}]]];
T[n_, k_] := b[n, 0, 0, k] - If[k == 0, 0, b[n, 0, 0, k - 1]];
Table[Table[T[n, k], {k, Ceiling[(Sqrt[8n+1]-1)/2], n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 27 2021, after Alois P. Heinz *)

A316293 Number T(n,k) of permutations p of [n] such that k is the maximum of the partial sums of the signed up-down jump sequence of 0,p; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 2, 1, 5, 8, 5, 1, 16, 50, 79, 69, 34, 9, 1, 65, 314, 872, 1539, 1823, 1494, 856, 339, 89, 14, 1, 326, 2142, 8799, 24818, 50561, 76944, 89546, 80938, 57284, 31771, 13707, 4520, 1103, 188, 20, 1, 1957, 16248, 89273, 355271, 1070455, 2514044, 4705648

Offset: 0

Alois P. Heinz, Jun 28 2018

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.

			Triangle T(n,k) begins:
: 1;
:    1;
:       2;
:       1, 5;
:          8, 16;
:          5, 50,   65;
:          1, 79,  314,   326;
:             69,  872,  2142,   1957;
:             34, 1539,  8799,  16248,  13700;
:              9, 1823, 24818,  89273, 137356,  109601;
:              1, 1494, 50561, 355271, 947713, 1287350, 986410;

Alois P. Heinz, Columns k = 0..40, flattened

Row sums give A000142.
Column sums give A316294.
Main diagonal gives A000522.
Cf. A000217, A258829, A291722, A303697, A316292 (same read by rows).

b:= proc(u, o, c, k) option remember;
      `if`(c>k, 0, `if`(u+o=0, 1,
       add(b(u-j, o-1+j, c+j, k), j=1..u)+
       add(b(u+j-1, o-j, c-j, k), j=1..o)))
    end:
T:= (n, k)-> b(n, 0$2, k) -`if`(k=0, 0, b(n, 0$2, k-1)):
seq(seq(T(n, k), n=k..k*(k+1)/2), k=0..8);

b[u_, o_, c_, k_] := b[u, o, c, k] = If[c > k, 0, If[u + o == 0, 1,
     Sum[b[u - j, o - 1 + j, c + j, k], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, c - j, k], {j, 1, o}]]];
T[n_, k_] := b[n, 0, 0, k] - If[k == 0, 0, b[n, 0, 0, k - 1]];
Table[Table[T[n, k], {n, k, k(k+1)/2}], {k, 0, 8}] // Flatten (* Jean-François Alcover, Mar 14 2021, after Alois P. Heinz *)

A289489 Number of permutations p of [n] such that in 0p the sum of all jumps equals 2n.

Original entry on oeis.org

1, 0, 0, 1, 4, 15, 104, 644, 3696, 23388, 151842, 979110, 6445659, 43148963, 290832906, 1977914328, 13574296048, 93787977144, 651970844448, 4558718881927, 32038664402074, 226200869873851, 1603811085640698, 11415385190127413, 81538284501095235

Offset: 0

Alois P. Heinz, Sep 02 2017

nonn

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.

			a(3) = 1: 312.
a(4) = 4: 3142, 4213, 4231, 4312.
a(5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312.
a(6) = 104: 126354, 136254, 142635, 146253, ..., 653421, 654213, 654231, 654312.

Alois P. Heinz, Table of n, a(n) for n = 0..300

Cf. A291722.

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1)*x^(j-1), j=1..u)+
      add(b(u+j-1, o-j)*x^(j-1), j=1..o)))
    end:
a:= n-> coeff(b(0, n), x, n):
seq(a(n), n=0..26);

b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,
   Sum[b[u - j, o + j - 1]*x^(j - 1), {j, 1, u}] +
   Sum[b[u + j - 1, o - j]*x^(j - 1), {j, 1, o}]]];
a[n_] := Coefficient[b[0, n], x, n];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Nov 17 2022, after Alois P. Heinz *)

a(n) = A291722(n,n).

a(n) ~ c * d^n / n^2, where d = 7.7572369635460295... and c = 0.022080578979754... - Vaclav Kotesovec, Nov 17 2022

cp's OEIS Frontend

A258829 Number T(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A263776 Triangle read by rows: T(n,k) (n>=0, 0<=k<=A002620(n-1)) is the number of permutations of [n] with k nestings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A303697 Number T(n,k) of permutations p of [n] whose difference between sum of up-jumps and sum of down-jumps equals k; triangle T(n,k), n>=0, min(0,1-n)<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A316292 Number T(n,k) of permutations p of [n] such that k is the maximum of the partial sums of the signed up-down jump sequence of 0,p; triangle T(n,k), n>=0, ceiling((sqrt(1+8*n)-1)/2)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A316293 Number T(n,k) of permutations p of [n] such that k is the maximum of the partial sums of the signed up-down jump sequence of 0,p; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A289489 Number of permutations p of [n] such that in 0p the sum of all jumps equals 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula