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

Links

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

Formula

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

Example

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

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

Crossrefs

Column k=0 gives A001883.

Row sums give A000166.

Main diagonal and lower diagonal give A059841, A110660.

Cf. A296050, A320582.

Sequence in context: A005813 A049262 A145201 * A340707 A284265 A119464

Adjacent sequences: A323668 A323669 A323670 * A323672 A323673 A323674

Keyword

nonn,tabl

Author

Alois P. Heinz, Jan 23 2019

Status

approved