A216716 Triangle read by rows: number of permutations of [1..n] with k progressions of rise 2, distance 1 and length 3 (n >= 0, k >= 0).

1, 1, 2, 6, 24, 114, 6, 674, 44, 2, 4714, 294, 30, 2, 37754, 2272, 276, 16, 2, 340404, 20006, 2236, 216, 16, 2, 3412176, 193896, 20354, 2200, 156, 16, 2, 37631268, 2056012, 206696, 20738, 1908, 160, 16, 2, 452745470, 23744752, 2273420, 215024, 21136, 1616, 164, 16, 2

Offset: 0

Author

N. J. A. Sloane, Sep 15 2012

Keywords

• nonn
• tabf

Examples

			Triangle begins:
         1
         1
         2
         6 [this is for n=3]
        24
       114       6
       674      44      2
      4714     294     30     2
     37754    2272    276    16    2
    340404   20006   2236   216   16   2
   3412176  193896  20354  2200  156  16  2
  37631268 2056012 206696 20738 1908 160 16 2
  ...
		

Links

• Alois P. Heinz, Rows n = 0..21, flattened
• K. J. Parsons, Arithmetic progressions in permutations, Thesis, Washington and Lee University, 2011
• Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012. [broken link]

Crossrefs

Row sums give A000142.

Column k=0 gives A174072.

Programs

Maple

b:= proc(s, x, y) option remember; expand(`if`(s={}, 1, add(
     `if`(x>0 and x-y=2 and y-j=2, z, 1)*b(s minus {j}, y, j), j=s)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b({$1..n}, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Apr 13 2021

Mathematica

b[s_, x_, y_] := b[s, x, y] = Expand[If[s == {}, 1, Sum[
     If[x > 0 && x - y == 2 && y - j == 2, z, 1]*
     b[s ~Complement~ {j}, y, j], {j, s}]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0,
     Exponent[p, z]}]][b[Range[n], 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)

Extensions

More terms from Alois P. Heinz, Apr 13 2021