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

Links

Alois P. Heinz, Rows n = 0..22, flattened

Wikipedia, Permutation

Formula

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

Example

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

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

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.

Sequence in context: A325703 A321898 A284434 * A243484 A181811 A284431

Adjacent sequences: A306540 A306541 A306542 * A306544 A306545 A306546

Keyword

nonn,tabf

Author

Alois P. Heinz, Feb 22 2019

Status

approved