A335872 Number T(n,k) of permutations of [n] having k points that are fixed or reflected; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 0, 2, 0, 4, 0, 2, 4, 0, 16, 0, 4, 16, 36, 32, 32, 0, 4, 80, 192, 216, 128, 96, 0, 8, 672, 1472, 1440, 984, 320, 144, 0, 8, 4752, 10752, 11776, 7680, 3936, 1024, 384, 0, 16, 48768, 103568, 104448, 65920, 28544, 9312, 1792, 512, 0, 16

Offset: 0

Author

Alois P. Heinz, Jun 28 2020

Keywords

• nonn
• tabl

Comments

A permutation p of [n] has fixed point j if p(j) = j, it has reflected point j if p(n+1-j) = j. A point can be fixed and reflected at the same time.

Examples

			      1;
      0,      1;
      0,      0,      2;
      0,      4,      0,     2;
      4,      0,     16,     0,     4;
     16,     36,     32,    32,     0,    4;
     80,    192,    216,   128,    96,    0,    8;
    672,   1472,   1440,   984,   320,  144,    0,   8;
   4752,  10752,  11776,  7680,  3936, 1024,  384,   0, 16;
  48768, 103568, 104448, 65920, 28544, 9312, 1792, 512,  0, 16;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..22, flattened
• T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
• Wikipedia, Permutation

Crossrefs

Column k=0 gives A003471.

Main diagonal gives A016116.

Row sums give A000142.

Cf. A008290, A335873.

Programs

Maple

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

Mathematica

b[s_, i_, t_] := b[s, i, t] = With[{n = Length[s]}, If[n == 0, x^t, Sum[b[s ~Complement~ {j}, i+1, t + If[j == i || j == n, 1, 0]], {j, s}]]];
T[n_] := CoefficientList[b[Range[n], 1, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)

Formula

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

T(n,n-2) = floor((n-1)^2/2) * 2^floor(n/2).