login
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.
6
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,10
LINKS
Wikipedia, Permutation
FORMULA
A(n,k) = n! - A306506(n,k).
A(n,n+i) = n! for i >= 0.
EXAMPLE
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, ...
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 *)
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.
Sequence in context: A114551 A191620 A214751 * A343938 A239397 A307884
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Feb 20 2019
STATUS
approved