A303564 Number T(n,k) of derangements of [n] having exactly k peaks; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

1, 0, 1, 1, 1, 3, 6, 5, 33, 6, 11, 152, 102, 21, 663, 1068, 102, 43, 2778, 9060, 2952, 85, 11413, 68250, 50796, 2952, 171, 46332, 477978, 679368, 131112, 341, 186867, 3192192, 7824834, 3349224, 131112, 683, 750878, 20648088, 81751824, 64791576, 8271792

Offset: 0

Author

Alois P. Heinz, Apr 26 2018

Keywords

• nonn
• tabf

Examples

			T(5,0) = 5: 51234, 53124, 53214, 54123, 54213.
T(5,1) = 33: 21453, 21534, 23451, 23514, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34512, 34521, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45123, 45213, 51423, 51432, 53412, 53421, 54132, 54231.
T(5,2) = 6: 23154, 24153, 34152, 34251, 45132, 45231.
Triangle T(n,k) begins:
    1;
    0;
    1;
    1,      1;
    3,      6;
    5,     33,        6;
   11,    152,      102;
   21,    663,     1068,      102;
   43,   2778,     9060,     2952;
   85,  11413,    68250,    50796,     2952;
  171,  46332,   477978,   679368,   131112;
  341, 186867,  3192192,  7824834,  3349224,  131112;
  683, 750878, 20648088, 81751824, 64791576, 8271792;
		

Links

• Alois P. Heinz, Rows n = 0..20, flattened
• Wikipedia, Derangement

Crossrefs

Columns k=0-1 give: A001045(n-1) for n>0, A301272.

Row sums give A000166.

Cf. A008303 (the same for permutations), A004526, A129815, A129817, A162979, A162980, A216963, A303648 (the same for involutions).

Programs

Maple

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

Mathematica

b[s_, i_, j_] := b[s, i, j] = Expand[If[s == {}, 1, Sum[If[k == Length[s], 0, b[s ~Complement~ {k}, If[j > k, 0, j], k]*If[i > 0 && j > 0 && i < j && j > k, x, 1]], {k, s}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Max[0, Exponent[p, x]]}]][b[Range[n], 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 31 2018, from Maple *)

Formula

T(2*n+1,n) = A129815(2*n+1) = A129817(2*n+1) = A162979(2*n+1,0) = A162980(2*n+1,0).