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

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.

Links

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

Example

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.

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

Prog

(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

Crossrefs

Column k=2 of A291680.

Sequence in context: A211295 A211289 A211292 * A079857 A265940 A309104

Adjacent sequences: A291680 A291681 A291682 * A291684 A291685 A291686

Keyword

nonn

Author

Alois P. Heinz, Aug 29 2017

Status

approved