A306209 Number A(n,k) of permutations of [n] within distance k of a fixed permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 6, 5, 1, 1, 1, 2, 6, 14, 8, 1, 1, 1, 2, 6, 24, 31, 13, 1, 1, 1, 2, 6, 24, 78, 73, 21, 1, 1, 1, 2, 6, 24, 120, 230, 172, 34, 1, 1, 1, 2, 6, 24, 120, 504, 675, 400, 55, 1, 1, 1, 2, 6, 24, 120, 720, 1902, 2069, 932, 89, 1, 1, 1, 2, 6, 24, 120, 720, 3720, 6902, 6404, 2177, 144, 1

Offset: 0

Author

Alois P. Heinz, Jan 29 2019

Keywords

• nonn
• tabl

Comments

A(n,k) counts permutations p of [n] such that |p(j)-j| <= k for all j in [n].

Examples

			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, ...
		

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.

Crossrefs

Columns k=0..10 give: A000012, A000045(n+1), A002524, A002526, A072856, A154654, A154655, A154656, A154657, A154658, A154659.

Rows n=1-2 give: A000012, A040000.

Main diagonal gives A000142.

A(2n,n) gives A048163(n+1).

A(2n+1,n) gives A092552(n+1).

A(n,floor(n/2)) gives A306267.

A(n+2,n) gives A001564.

Cf. A130152.

Programs

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 *)

Formula

A(n,k) = Sum_{j=0..k} A130152(n,j) for n > 0, A(0,k) = 1.