%I #24 May 31 2018 18:01:08

%S 1,0,1,1,1,3,6,5,33,6,11,152,102,21,663,1068,102,43,2778,9060,2952,85,

%T 11413,68250,50796,2952,171,46332,477978,679368,131112,341,186867,

%U 3192192,7824834,3349224,131112,683,750878,20648088,81751824,64791576,8271792

%N 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.

%H Alois P. Heinz, <a href="/A303564/b303564.txt">Rows n = 0..20, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Derangements">Derangement</a>

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

%e T(5,0) = 5: 51234, 53124, 53214, 54123, 54213.

%e 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.

%e T(5,2) = 6: 23154, 24153, 34152, 34251, 45132, 45231.

%e Triangle T(n,k) begins:

%e 1;

%e 0;

%e 1;

%e 1, 1;

%e 3, 6;

%e 5, 33, 6;

%e 11, 152, 102;

%e 21, 663, 1068, 102;

%e 43, 2778, 9060, 2952;

%e 85, 11413, 68250, 50796, 2952;

%e 171, 46332, 477978, 679368, 131112;

%e 341, 186867, 3192192, 7824834, 3349224, 131112;

%e 683, 750878, 20648088, 81751824, 64791576, 8271792;

%p b:= proc(s, i, j) option remember; expand(`if`(s={}, 1, add(

%p `if`(k=nops(s), 0, b(s minus {k}, `if`(j>k, 0, j), k)*

%p `if`(i>0 and j>0 and i<j and j>k, x, 1)), k=s)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, degree(p))))(b({$1..n}, 0$2)):

%p seq(T(n), n=0..12);

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Max[0, Exponent[p, x]]}]][b[Range[n], 0, 0]];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, May 31 2018, from Maple *)

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

%Y Row sums give A000166.

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

%K nonn,tabf

%O 0,6

%A _Alois P. Heinz_, Apr 26 2018