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.

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

Author

Alois P. Heinz, Apr 28 2018

Keywords

• nonn
• tabf

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.

Examples

			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  ;
		

Links

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

Crossrefs

Row sums give A000142.

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

Programs

Maple

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

Mathematica

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

Formula

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.