A338765 - OEIS

%I #18 Mar 21 2022 04:46:37

%S 1,1,2,6,18,38,76,162,330,650,1272,2586,5262,10506,20856,41928,83684,

%T 165800,329310,653614,1303388,2584660,5139580,10210912,20288128,

%U 40224174,79824572,158316222,314272812

%N Number of permutations p of [n] such that | |p(i) - p(i-1)| - |p(i+1) - p(i)| | <= 1.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%p b:= proc(s, x, y) option remember; `if`(s={}, 1, add(

%p       `if`(x=0 or y=0 or abs(abs(x-y)-abs(y-j))<=1,

%p          b(s minus {j}, y, j), 0), j=s))

%p     end:

%p a:= n-> b({$1..n}, 0$2):

%p seq(a(n), n=0..15);

%t b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[

%t      If[x == 0 || y == 0 || Abs[Abs[x - y] - Abs[y - j]] <= 1,

%t      b[s ~Complement~ {j}, y, j], 0], {j, s}]];

%t a[n_] := b[Range[n], 0, 0];

%t a /@ Range[0, 15] (* _Jean-François Alcover_, Apr 26 2021, after _Alois P. Heinz_ *)

%Y Cf. A295370, A338766.

%K nonn,more

%O 0,3

%A _Alois P. Heinz_, Nov 07 2020