A343535 Number T(n,k) of permutations of [n] having exactly k consecutive triples j, j+1, j-1; triangle T(n,k), n>=0, 0<=k<=floor(n/3), read by rows.

1, 1, 2, 5, 1, 20, 4, 102, 18, 626, 92, 2, 4458, 564, 18, 36144, 4032, 144, 328794, 32898, 1182, 6, 3316944, 301248, 10512, 96, 36755520, 3057840, 102240, 1200, 443828184, 34073184, 1085904, 14304, 24, 5800823880, 413484240, 12538080, 174000, 600, 81591320880

Offset: 0

Author

Alois P. Heinz, Apr 18 2021

Keywords

• nonn
• tabf

Comments

Terms in column k are multiples of k!.

Examples

			T(4,1) = 4: 1342, 2314, 3421, 4231.
Triangle T(n,k) begins:
              1;
              1;
              2;
              5,           1;
             20,           4;
            102,          18;
            626,          92,          2;
           4458,         564,         18;
          36144,        4032,        144;
         328794,       32898,       1182,        6;
        3316944,      301248,      10512,       96;
       36755520,     3057840,     102240,     1200;
      443828184,    34073184,    1085904,    14304,     24;
     5800823880,   413484240,   12538080,   174000,    600;
    81591320880,  5428157760,  156587040,  2214720,  10800;
  1228888215960, 76651163160, 2105035440, 29777520, 175800, 120;
  ...
		

Links

• Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).
• Wikipedia, Permutation

Crossrefs

Column k=0 gives A212580.

Row sums give A000142.

Cf. A047921, A123513, A197365, A216716.

Programs

Maple

b:= proc(s, l, t) option remember; `if`(s={}, 1, add((h->
      expand(b(s minus {j}, j, `if`(h=1, 2, 1))*
     `if`(t=2 and h=-2, x, 1)))(j-l), j=s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
               b({$1..n}, -1, 1)):
seq(T(n), n=0..13);

Mathematica

b[s_, l_, t_] := b[s, l, t] = If[s == {}, 1, Sum[Function[h,
     Expand[b[s ~Complement~ {j}, j, If[h == 1, 2, 1]]*
     If[t == 2 && h == -2, x, 1]]][j - l], {j, s}]];
T[n_] := CoefficientList[b[Range[n], -1, 1], x];
T /@ Range[0, 13] // Flatten (* Jean-François Alcover, Apr 26 2021, after Alois P. Heinz *)

Formula

T(3n,n) = n!.