OFFSET
0,9
COMMENTS
A(n,k) counts permutations p of [n] such that |p(j)-j| <= k for all j in [n].
LINKS
Alois P. Heinz, Antidiagonals n = 0..36, flattened
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Torleiv Kløve, Generating functions for the number of permutations with limited displacement, Electron. J. Combin., 16 (2009), #R104.
FORMULA
A(n,k) = Sum_{j=0..k} A130152(n,j) for n > 0, A(0,k) = 1.
EXAMPLE
A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(5,2) = 31: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14253, 14325, 14523, 21345, 21354, 21435, 21453, 21534, 21543, 23145, 23154, 24135, 24153, 31245, 31254, 31425, 31524, 32145, 32154, 34125.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, 2, 2, ...
1, 3, 6, 6, 6, 6, 6, 6, 6, ...
1, 5, 14, 24, 24, 24, 24, 24, 24, ...
1, 8, 31, 78, 120, 120, 120, 120, 120, ...
1, 13, 73, 230, 504, 720, 720, 720, 720, ...
1, 21, 172, 675, 1902, 3720, 5040, 5040, 5040, ...
1, 34, 400, 2069, 6902, 17304, 30960, 40320, 40320, ...
MATHEMATICA
A[0, _] = 1;
A[n_ /; n > 0, k_] := A[n, k] = Permanent[Table[If[Abs[i - j] <= k, 1, 0], {i, 1, n}, {j, 1, n}]];
Table[A[n - k, k], {n, 0, 12}, {k, n, 0, -1 }] // Flatten (* Jean-François Alcover, Oct 18 2021, after Alois P. Heinz in A130152 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jan 29 2019
STATUS
approved