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

Comments

Terms in column k are multiples of k!.

Links

Table of n, a(n) for n=0..40.

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

Wikipedia, Permutation

Formula

T(3n,n) = n!.

Example

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

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

Crossrefs

Column k=0 gives A212580.

Row sums give A000142.

Cf. A047921, A123513, A197365, A216716.

Sequence in context: A187244 A120294 A186766 * A047921 A242783 A177250

Adjacent sequences: A343532 A343533 A343534 * A343536 A343537 A343538

Keyword

nonn,tabf

Author

Alois P. Heinz, Apr 18 2021

Status

approved