A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.

0, 0, 1, 2, 8, 40, 236, 1648, 13125, 117794, 1175224, 12903874, 154615096, 2007498192, 28075470833, 420753819282, 6726830163592, 114278495205524, 2055782983578788, 39039148388975552, 780412763620655061, 16381683795665956242, 360258256118419518680, 8283042472303599966974

Offset

0,4

Links

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

Formula

a(n) = A000142(n) - A001883(n) - A002467(n).

a(n) = A000166(n) - A001883(n).

a(n) = Sum_{k=1..n} A323671(n,k).

a(n) is odd <=> n in { A016933 }.

a(n) is even <=> n in { A047252 }.

Example

a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
a(5) = 40: 21453, 21534, 23154, 23451, 23514, 24153, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34152, 34251, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45132, 45213, 45231, 51234, 51423, 51432, 53124, 53214, 53412, 53421, 54132, 54213, 54231.

Maple

b:= proc(s, k) option remember; (n-> `if`(n=0, `if`(k=1, 1, 0), add(
      `if`(n=j, 0, b(s minus {j}, min(k, abs(n-j)))), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}, n):
seq(a(n), n=0..14);
# second Maple program:
a:= n-> (f-> f(1)-f(2))(k-> `if`(n=0, 1, LinearAlgebra[Permanent](
        Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))):
seq(a(n), n=0..14);
# third Maple program:
g:= proc(n) g(n):= `if`(n<2, 1-n, (n-1)*(g(n-1)+g(n-2))) end:
h:= proc(n) h(n):= `if`(n<7, [1, 0$3, 1, 4, 29][n+1], n*h(n-1)+4*h(n-2)
      -3*(n-3)*h(n-3)+(n-4)*h(n-4)+2*(n-5)*h(n-5)-(n-7)*h(n-6)-h(n-7))
    end:
a:= n-> g(n)-h(n):
seq(a(n), n=0..25);

Mathematica

g[n_] := g[n] = If[n < 2, 1-n, (n-1)(g[n-1] + g[n-2])];
h[n_] := h[n] = If[n < 7, {1, 0, 0, 0, 1, 4, 29}[[n+1]],
     n h[n-1] + 4h[n-2] - 3(n-3)h[n-3] + (n-4)h[n-4] +
     2(n-5)h[n-5] - (n-7)h[n-6] - h[n-7]];
a[n_] := g[n] - h[n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after third Maple program *)

Crossrefs

Column k=1 of A299789.

Cf. A000142, A000166, A001883, A002467, A016933, A047252, A323671.

Sequence in context: A116456 A341876 A305406 * A347666 A055882 A002301

Adjacent sequences: A296047 A296048 A296049 * A296051 A296052 A296053

Keyword

nonn

Author

Alois P. Heinz, Jan 21 2019

Status

approved