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,3

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.

Links

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

Example

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

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

Crossrefs

Row sums and main diagonal (shifted) of A291684.

Cf. A288910, A288911, A288912.

Sequence in context: A149957 A148393 A148394 * A268571 A001428 A055726

Adjacent sequences: A291682 A291683 A291684 * A291686 A291687 A291688

Keyword

nonn

Author

Alois P. Heinz, Aug 29 2017

Status

approved