A306209 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; table; graph; refs; listen; history; text; internal format)

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, 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}]];