A306512 Number A(n,k) of permutations p of [n] having no index i with |p(i)-i| = k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 9, 1, 1, 2, 3, 5, 44, 1, 1, 2, 6, 9, 21, 265, 1, 1, 2, 6, 14, 34, 117, 1854, 1, 1, 2, 6, 24, 53, 176, 792, 14833, 1, 1, 2, 6, 24, 78, 265, 1106, 6205, 133496, 1, 1, 2, 6, 24, 120, 362, 1554, 8241, 55005, 1334961

Offset: 0

Author

Alois P. Heinz, Feb 20 2019

Keywords

• nonn
• tabl

Examples

			A(4,0) = 9: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
A(4,1) = 5: 1234, 1432, 3214, 3412, 4231.
A(4,2) = 9: 1234, 1243, 1324, 2134, 2143, 2341, 4123, 4231, 4321.
Square array A(n,k) begins:
     1,   1,    1,    1,    1,    1,    1,    1, ...
     0,   1,    1,    1,    1,    1,    1,    1, ...
     1,   1,    2,    2,    2,    2,    2,    2, ...
     2,   2,    3,    6,    6,    6,    6,    6, ...
     9,   5,    9,   14,   24,   24,   24,   24, ...
    44,  21,   34,   53,   78,  120,  120,  120, ...
   265, 117,  176,  265,  362,  504,  720,  720, ...
  1854, 792, 1106, 1554, 2119, 2790, 3720, 5040, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..45, flattened
• Wikipedia, Permutation

Crossrefs

Columns k=0-3 give: A000166, A078480, A306523, A324365.

A(n+2j,n+j) (j=0..5) give: A000142, A001564, A001688, A023043, A023045, A023047.

A(2n,n) gives A306535.

Cf. A306506.

Programs

Maple

A:= proc(n, k) option remember; `if`(k>=n, n!, LinearAlgebra[
      Permanent](Matrix(n, (i, j)-> `if`(abs(i-j)=k, 0, 1))))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);
# second Maple program:
b:= proc(s, k) option remember; (n-> `if`(n=0, 1, add(
      `if`(abs(i-n)=k, 0, b(s minus {i}, k)), i=s)))(nops(s))
    end:
A:= (n, k)-> `if`(k>=n, n!, b({$1..n}, k)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

A[n_, k_] := If[k > n, n!, Permanent[Table[If[Abs[i-j] == k, 0, 1], {i, 1, n}, {j, 1, n}]]]; A[0, 0] = 1;
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 05 2021, from first Maple program *)
b[s_, k_] := b[s, k] = With[{n = Length[s]}, If[n == 0, 1, Sum[
     If[Abs[i-n] == k, 0, b[s ~Complement~ {i}, k]], {i, s}]]];
A[n_, k_] := If[k >= n, n!, b[Range@n, k]];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Sep 01 2021, from second Maple program *)

Formula

A(n,k) = n! - A306506(n,k).

A(n,n+i) = n! for i >= 0.