A316293 -id:A316293 - 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).

A291722 Number T(n,k) of permutations p of [n] such that in 0p the sum of all jumps equals k + n; triangle T(n,k), n >= 0, 0 <= k <= n*(n-1)/2, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 6, 6, 5, 4, 1, 1, 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1, 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1, 1, 21, 105, 210, 350, 497, 554, 644, 567, 574, 420, 386, 238, 203, 105, 85, 35, 28, 8, 7, 1, 1

Offset: 0

Alois P. Heinz, Aug 30 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.
From David B. Wilson, Dec 14 2018: (Start)
T(n,k) equals the number of permutations p of [n] such that twice the sum of the leftward-down-jumps of p plus the number of descents of p equals k.
T(n,k) equals the number of cover-inclusive Dyck tilings whose lower boundary is the zig-zag path of order n (UD)^n, and which have k tiles.
A leftward-down-jump j occurs at position i in p if p_{i} > p_{i+1} and there are j positions k for which k p_k > p_{i+1}.
Cover-inclusive Dyck tilings are defined in the Kenyon and Wilson link below. (End)

Examples

T(4,0) = 1: 1234. T(4,1) = 6: 1243, 1324, 1342, 2134, 2314, 2341. T(4,2) = 6: 1432, 2143, 2431, 3214, 3241, 3421. T(4,3) = 5: 1423, 2413, 3124, 3412, 4321. T(4,4) = 4: 3142, 4213, 4231, 4312. T(4,5) = 1: 4123. T(4,6) = 1: 4132. T(5,5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312. Triangle T(n,k) begins: 1; 1; 1, 1; 1, 3, 1, 1; 1, 6, 6, 5, 4, 1, 1; 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1; 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1;

Links

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

R. W. Kenyon, D. B. Wilson, Double-dimer pairings and skew Young diagrams, The Electronic Journal of Combinatorics 18(1) #P130, 2011.

J. S. Kim, K. Mészáros, G. Panova, and D. B. Wilson. Dyck tilings, increasing trees, descents, and inversions, Journal of Combinatorial Theory A 122:9-27, 2014.

Crossrefs

Columns k=0-3 give: A000012, A000217(n-1) for n>0, A002415(n-1) for n>0, A291288(n-3) for n>0.

Row sums give A000142.

T(n,n) gives A289489.

Cf. A005990, A008292, A123125, A173018, A258829, A263776, A316292, A316293.

Programs

Maple

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: T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(0, n)): seq(T(n), n=0..10);

Mathematica

(* Generating function for tiles for Dyck tilings above the zigzag path of order n *) (* Computed by looking at descents in the insertion sequence for the Dyck-tiling-ribbon bijection, described in the Kim-Meszaros-Panova-Wilson reference *) (* Since it's above the zigzag, all insertion positions are even *) (* When the second argument is specified, refines by position of last insertion *) tilegen[n_, sn_] := tilegen[n, sn] = If[n == 0 || n == 1, 1, Sum[tilegen[n - 1, j] If[j >= sn, t^(j - sn + 1), 1] // Expand, {j, 0, 2 (n - 2), 2}] ]; tilegen[n_] := tilegen[n + 1, 2 n]; T[n_, k_] := Coefficient[tilegen[n], t, k]; (* David B. Wilson, Dec 14 2018 *)

Formula

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

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

A316294 Total number of permutations p of [k] such that n is the maximum of the partial sums of the signed up-down jump sequence of 0,p summed over all k >= 0.

Original entry on oeis.org

1, 1, 3, 19, 258, 7406, 442668, 54371100, 13585980916, 6859762797636, 6969135518632452, 14209819222900305044, 58061006907633910998660, 474996314819118381967232244, 7776635831062534849079443379908, 254723669580125156112963535996038036

Offset: 0

Alois P. Heinz, Jun 28 2018

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.

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

Column sums of A316292 or A316293.

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:
a:= n-> add(b(k, 0$2, n)-b(k, 0$2, n-1), k=n..n*(n+1)/2):
seq(a(n), n=0..15);

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, u}] +
     Sum[b[u + j - 1, o - j, c - j, k], {j, o}]]];
a[n_] := Sum[b[k, 0, 0, n] - b[k, 0, 0, n-1], {k, n, n(n+1)/2}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Sep 01 2021, after Alois P. Heinz *)

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

A291722 Number T(n,k) of permutations p of [n] such that in 0p the sum of all jumps equals k + n; triangle T(n,k), n >= 0, 0 <= k <= n*(n-1)/2, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A316294 Total number of permutations p of [k] such that n is the maximum of the partial sums of the signed up-down jump sequence of 0,p summed over all k >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica