A323671 Number T(n,k) of permutations p of [n] with no fixed points such that |{ j : |p(j)-j| = 1 }| = k; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 2, 3, 2, 1, 4, 12, 14, 8, 6, 0, 29, 68, 82, 54, 25, 6, 1, 206, 496, 546, 376, 170, 48, 12, 0, 1708, 3960, 4349, 2922, 1353, 430, 98, 12, 1, 15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0, 159737, 358786, 383523, 257552, 120919, 41508, 10647, 1998, 270, 20, 1

Offset: 0

Author

Alois P. Heinz, Jan 23 2019

Keywords

• nonn
• tabl

Examples

			T(4,0) = 1: 3412.
T(4,1) = 2: 3421, 4312.
T(4,2) = 3: 2413, 3142, 4321.
T(4,3) = 2: 2341, 4123.
T(4,4) = 1: 2143.
Triangle T(n,k) begins:
      1;
      0,     0;
      0,     0,     1;
      0,     0,     2,     0;
      1,     2,     3,     2,     1;
      4,    12,    14,     8,     6,    0;
     29,    68,    82,    54,    25,    6,   1;
    206,   496,   546,   376,   170,   48,  12,   0;
   1708,  3960,  4349,  2922,  1353,  430,  98,  12,  1;
  15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..23, flattened

Crossrefs

Column k=0 gives A001883.

Row sums give A000166.

Main diagonal and lower diagonal give A059841, A110660.

Cf. A296050, A320582.

Programs

Maple

b:= proc(s) option remember; expand((n-> `if`(n=0, 1, add(
      (t-> `if`(t=0, 0, `if`(t=1, x, 1)*b(s minus {j}))
       )(abs(n-j)), j=s)))(nops(s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b({$1..n})):
seq(T(n), n=0..12);

Mathematica

b[s_] := b[s] = Expand[Function[n, If[n==0, 1, Sum[Function[t, If[t==0, 0, If[t==1, x, 1]*b[s~Complement~{j}]]][Abs[n-j]], {j, s}]]][Length[s]]];
T[n_] := PadRight[CoefficientList[b[Range[n]], x], n+1];
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

Formula

Sum_{k=1..n} T(n,k) = A296050(n).