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

Comments

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

Links

Alois P. Heinz, Rows n = 1..35, flattened

Wikipedia, Permutation

Formula

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

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

Example

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

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

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.

Sequence in context: A345294 A233581 A193628 * A241056 A212618 A066602

Adjacent sequences: A306503 A306504 A306505 * A306507 A306508 A306509

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 20 2019

Status

approved