A306543 Number T(n,k) of permutations p of [n] such that |p(j)-j| >= k (for all j in [n]); triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

1, 1, 2, 1, 6, 2, 24, 9, 1, 120, 44, 4, 720, 265, 29, 1, 5040, 1854, 206, 8, 40320, 14833, 1708, 112, 1, 362880, 133496, 15702, 1168, 16, 3628800, 1334961, 159737, 13365, 436, 1, 39916800, 14684570, 1780696, 159414, 6984, 32, 479001600, 176214841, 21599745, 2036488, 114124, 1708, 1

Offset: 0

Author

Alois P. Heinz, Feb 22 2019

Keywords

• nonn
• tabf

Examples

			Triangle T(n,k) begins:
          1;
          1;
          2,         1;
          6,         2;
         24,         9,        1;
        120,        44,        4;
        720,       265,       29,       1;
       5040,      1854,      206,       8;
      40320,     14833,     1708,     112,      1;
     362880,    133496,    15702,    1168,     16;
    3628800,   1334961,   159737,   13365,    436,    1;
   39916800,  14684570,  1780696,  159414,   6984,   32;
  479001600, 176214841, 21599745, 2036488, 114124, 1708, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..22, flattened
• Wikipedia, Permutation

Crossrefs

Columns k=0-6 give (offsets may differ): A000142, A000166, A001883, A075851, A075852, A183242, A183243.

T(2n,n) gives A000012.

T(2n+1,n) gives A000079.

T(2n+2,n) gives A183245 for n > 0.

T(2n+3,n) gives A183246 for n > 0.

T(2n+4,n) gives A183247 for n > 0.

Cf. A183244, A299789.

Programs

Maple

T:= proc(n, k) option remember; `if`(n=0, 1, LinearAlgebra[
      Permanent](Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))
    end:
seq(seq(T(n, k), k=0..floor(n/2)), n=0..12);

Mathematica

T[n_, k_] := T[n, k] = If[n==0, 1, Permanent[Table[
     If[Abs[i-j] >= k, 1, 0], {i, n}, {j, n}]]];
Table[Table[T[n, k], {k, 0, Floor[n/2]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 26 2021, after Alois P. Heinz *)

Formula

T(n,k) = Sum_{j=k..floor(n/2)} A299789(n,j) for n > 0.