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

Links

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

Wikipedia, Derangement

Formula

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

Example

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;

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 i<j and j>k, 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 *)

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

Sequence in context: A199126 A247569 A115389 * A121867 A307132 A300673

Adjacent sequences: A303561 A303562 A303563 * A303565 A303566 A303567

Keyword

nonn,tabf

Author

Alois P. Heinz, Apr 26 2018

Status

approved