A291684 Number T(n,k) of permutations p of [n] such that 0p has a nonincreasing jump sequence beginning with k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 5, 5, 5, 0, 1, 9, 12, 14, 16, 0, 1, 17, 36, 36, 47, 52, 0, 1, 31, 81, 98, 117, 166, 189, 0, 1, 57, 174, 327, 327, 425, 627, 683, 0, 1, 101, 413, 788, 988, 1116, 1633, 2400, 2621, 0, 1, 185, 889, 1890, 3392, 3392, 4291, 6471, 9459, 10061

Offset: 0

Author

Alois P. Heinz, Aug 29 2017

Keywords

• nonn
• tabl

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

			T(3,1) = 1: 123.
T(3,2) = 2: 213, 231.
T(3,3) = 2: 312, 321.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,   2;
  0, 1,   5,   5,   5;
  0, 1,   9,  12,  14,  16;
  0, 1,  17,  36,  36,  47,   52;
  0, 1,  31,  81,  98, 117,  166,  189;
  0, 1,  57, 174, 327, 327,  425,  627,  683;
  0, 1, 101, 413, 788, 988, 1116, 1633, 2400, 2621;
		

Links

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

Crossrefs

Columns k=0-10 give: A000007, A057427, A292168, A292169, A292170, A292171, A292172, A292173, A292174, A292175, A292176.

Row sums and T(n+1,n+1) give A291685.

T(2n,n) gives A291688, T(2n+1,n+1) gives A303203, T(n,ceiling(n/2)) gives A303204.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, j), j=1..min(t, u))+
      add(b(u+j-1, o-j, j), j=1..min(t, 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);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, j], {j, 1, Min[t, u]}] + Sum[b[u + j - 1, o - j, j], {j, 1, Min[t, 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, Jul 09 2018, after Alois P. Heinz *)

Formula

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

T(2n,n) = T(2n,n+1) for all n>0.