OFFSET
0,3
COMMENTS
Number of permutations p of [n] such that |p(i-1)-p(i)| < |p(i)-p(i+1)| if i is even and |p(i-1)-p(i)| > |p(i)-p(i+1)| if i is odd.
LINKS
Wikipedia, Permutation
EXAMPLE
a(0) = 1: (), the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 2: 213, 231.
a(4) = 8: 1243, 2134, 2143, 2413, 3142, 3412, 3421, 4312.
a(5) = 20: 12435, 12453, 21435, 21453, 23541, 31425, 31452, 31542, 32451, 32541, 34125, 34215, 35124, 35214, 35241, 43125, 45213, 45231, 54213, 54231.
a(6) = 82: 124356, 124365, 125364, 125634, ..., 652143, 652413, 653412, 653421.
MAPLE
b:= proc(s, x, y) option remember; (n-> `if`(n=0, 1, add((d->
`if`(x=0 or n::even and x<d or n::odd and x>d, b(s minus {j},
`if`(y=0, 0, d), j), 0))(abs(y-j)), j=s)))(nops(s))
end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..12);
MATHEMATICA
b[s_, x_, y_] := b[s, x, y] = Function[n, If[n == 0, 1, Sum[Function[d,
If[x == 0 || EvenQ[n] && x < d || OddQ[n] && x > d, b[s ~Complement~
{j}, If[y == 0, 0, d], j], 0]][Abs[y - j]], {j, s}]]][Length[s]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Mar 07 2022, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Alois P. Heinz, Oct 25 2021
STATUS
approved