A306506 Number T(n,k) of permutations p of [n] having at least one index i with |p(i)-i| = k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 1, 1, 4, 4, 3, 15, 19, 15, 10, 76, 99, 86, 67, 42, 455, 603, 544, 455, 358, 216, 3186, 4248, 3934, 3486, 2921, 2250, 1320, 25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360, 229384, 307875, 292509, 272064, 245806, 214551, 179058, 133800, 75600

Offset: 1

Author

Alois P. Heinz, Feb 20 2019

Keywords

• nonn
• tabl

Comments

T(n,k) is defined for n,k>=0. The triangle contains only the terms with k=n.

Examples

			The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have absolute displacement sets {|p(i)-i|, i=1..3}: {0}, {0,1}, {0,1}, {1,2}, {1,2}, {0,2}, respectively. Number 0 occurs four times, 1 occurs four times, and 2 occurs thrice. So row n=3 is [4, 4, 3].
Triangle T(n,k) begins:
      1;
      1,     1;
      4,     4,     3;
     15,    19,    15,    10;
     76,    99,    86,    67,    42;
    455,   603,   544,   455,   358,   216;
   3186,  4248,  3934,  3486,  2921,  2250,  1320;
  25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..35, flattened
• Wikipedia, Permutation

Crossrefs

Columns k=0-3 give: A002467, A306511, A306524, A324366.

T(n+2,n+1) gives A007680 (for n>=0).

T(2n,n) gives A306675.

Cf. A000142, A010050, A306461, A306512, A306535.

Programs

Maple

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

Mathematica

T[n_, k_] := n!-Permanent[Table[If[Abs[i-j]==k, 0, 1], {i, 1, n}, {j, 1, n} ]];
Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, May 01 2019, from 2nd Maple program *)

Formula

T(n,k) = n! - A306512(n,k).

T(2n,n) = T(2n,0) = A002467(2n) = (2n)! - A306535(n).