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

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.

Links

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

T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)

Wikipedia, Permutation

Formula

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

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

Example

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

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

Crossrefs

Column k=0 gives A003471.

Main diagonal gives A016116.

Row sums give A000142.

Cf. A008290, A335873.

Sequence in context: A349127 A279228 A181481 * A239489 A259759 A364817

Adjacent sequences: A335869 A335870 A335871 * A335873 A335874 A335875

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 28 2020

Status

approved