A291683 Number of permutations p of [n] such that in 0p the largest up-jump equals 2 and no down-jump is larger than 2.

0, 0, 1, 3, 9, 25, 71, 205, 607, 1833, 5635, 17577, 55515, 177191, 570699, 1852571, 6055079, 19910729, 65823751, 218654099, 729459551, 2443051213, 8210993363, 27685671843, 93625082139, 317470233149, 1079183930827, 3676951654519, 12554734605495, 42952566314235

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.

All positive terms are odd.

Examples

			a(2) = 1: 21.
a(3) = 3: 132, 213, 231.
a(4) = 9: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431.
a(5) = 25: 12354, 12435, 12453, 13245, 13254, 13425, 13452, 13524, 13542, 21345, 21354, 21435, 21453, 23145, 23154, 23415, 23451, 23514, 23541, 24135, 24153, 24315, 24351, 24513, 24531.
		

Links

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

Crossrefs

Column k=2 of A291680.

Programs

Maple

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(2, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
a:= n-> b(0, n, 2)-b(0, n, 1):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[2, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
a[n_] := b[0, n, 2] - b[0, n, 1];
Array[a, 30, 0] (* Jean-François Alcover, May 31 2019, from Maple *)

Python

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(2, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def a(n): return b(0, n, 2) - b(0, n, 1)
for n in range(31): print (a(n)) # Indranil Ghosh, Aug 30 2017