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

1, 1, 0, 1, 0, 1, 2, 0, 4, 0, 5, 6, 10, 2, 1, 21, 36, 42, 12, 9, 0, 117, 226, 219, 104, 47, 6, 1, 792, 1568, 1472, 800, 328, 64, 16, 0, 6205, 12360, 11596, 6652, 2658, 688, 148, 12, 1, 55005, 109760, 103600, 60840, 24770, 7120, 1560, 200, 25, 0, 543597, 1085560, 1030649, 614420, 255830, 77732, 17750, 2876, 365, 20, 1

Offset: 0

Author

Alois P. Heinz, Jan 23 2019

Keywords

• nonn
• tabl

Examples

			T(4,0) = 5: 1234, 1432, 3214, 3412, 4231.
T(4,1) = 6: 2431, 3241, 3421, 4132, 4213, 4312.
T(4,2) = 10: 1243, 1324, 1342, 1423, 2134, 2314, 2413, 3124, 3142, 4321.
T(4,3) = 2: 2341, 4123.
T(4,4) = 1: 2143.
Triangle T(n,k) begins:
      1;
      1,      0;
      1,      0,      1;
      2,      0,      4,     0;
      5,      6,     10,     2,     1;
     21,     36,     42,    12,     9,    0;
    117,    226,    219,   104,    47,    6,    1;
    792,   1568,   1472,   800,   328,   64,   16,   0;
   6205,  12360,  11596,  6652,  2658,  688,  148,  12,  1;
  55005, 109760, 103600, 60840, 24770, 7120, 1560, 200, 25,  0;
  ...
		

Links

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

Crossrefs

Column k=0 gives A078480.

Row sums give A000142.

Main diagonal gives A059841.

Cf. A008290, A008291, A052582, A082033, A323671.

Programs

Maple

b:= proc(s) option remember; expand((n-> `if`(n=0, 1, add(
     `if`(abs(n-j)=1, x, 1)*b(s minus {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[With[{n = Length[s]}, If[n==0, 1, Sum[
     If[Abs[n-j]==1, x, 1]*b[s~Complement~{j}], {j, 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} k * T(n,k) = A052582(n-1) for n > 0.

Sum_{k=0..n} (k+1) * T(n,k) = A082033(n-1) for n > 0.