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

Links

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

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.

Example

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

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

Crossrefs

Column k=0 gives A078480.

Row sums give A000142.

Main diagonal gives A059841.

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

Sequence in context: A065806 A331185 A228087 * A119690 A166260 A319813

Adjacent sequences: A320579 A320580 A320581 * A320583 A320584 A320585

Keyword

nonn,tabl

Author

Alois P. Heinz, Jan 23 2019

Status

approved