A291685 Number of permutations p of [n] such that 0p has a nonincreasing jump sequence.

1, 1, 2, 5, 16, 52, 189, 683, 2621, 10061, 40031, 159201, 650880, 2657089, 11062682, 46065143, 194595138, 822215099, 3513875245, 15021070567, 64785349064, 279575206629, 1214958544538, 5283266426743, 23106210465665, 101120747493793, 444614706427665

Offset: 0

Author

Alois P. Heinz, Aug 29 2017

Keywords

• nonn

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

			a(3) = 5 = 6 - 1 counts all permutations of {1,2,3} except 132 with jump sequence 1, 2, 1.
		

Links

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

Crossrefs

Row sums and main diagonal (shifted) of A291684.

Cf. A288910, A288911, A288912.

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:
a:= n-> b(0, n$2):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1,
     Sum[b[u-j, o+j-1, j], {j, Min[t, u]}]+
     Sum[b[u+j-1, o-j, j], {j, Min[t, o]}]];
a[n_] := b[0, n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)