cp's OEIS Frontend

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.

%I A303564 #24 May 31 2018 18:01:08
%S A303564 1,0,1,1,1,3,6,5,33,6,11,152,102,21,663,1068,102,43,2778,9060,2952,85,
%T A303564 11413,68250,50796,2952,171,46332,477978,679368,131112,341,186867,
%U A303564 3192192,7824834,3349224,131112,683,750878,20648088,81751824,64791576,8271792
%N 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.
%H A303564 Alois P. Heinz, <a href="/A303564/b303564.txt">Rows n = 0..20, flattened</a>
%H A303564 Wikipedia, <a href="https://en.wikipedia.org/wiki/Derangements">Derangement</a>
%F A303564 T(2*n+1,n) = A129815(2*n+1) = A129817(2*n+1) = A162979(2*n+1,0) = A162980(2*n+1,0).
%e A303564 T(5,0) = 5: 51234, 53124, 53214, 54123, 54213.
%e A303564 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 A303564 T(5,2) = 6: 23154, 24153, 34152, 34251, 45132, 45231.
%e A303564 Triangle T(n,k) begins:
%e A303564     1;
%e A303564     0;
%e A303564     1;
%e A303564     1,      1;
%e A303564     3,      6;
%e A303564     5,     33,        6;
%e A303564    11,    152,      102;
%e A303564    21,    663,     1068,      102;
%e A303564    43,   2778,     9060,     2952;
%e A303564    85,  11413,    68250,    50796,     2952;
%e A303564   171,  46332,   477978,   679368,   131112;
%e A303564   341, 186867,  3192192,  7824834,  3349224,  131112;
%e A303564   683, 750878, 20648088, 81751824, 64791576, 8271792;
%p A303564 b:= proc(s, i, j) option remember; expand(`if`(s={}, 1, add(
%p A303564       `if`(k=nops(s), 0, b(s minus {k}, `if`(j>k, 0, j), k)*
%p A303564       `if`(i>0 and j>0 and i<j and j>k, x, 1)), k=s)))
%p A303564     end:
%p A303564 T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, degree(p))))(b({$1..n}, 0$2)):
%p A303564 seq(T(n), n=0..12);
%t A303564 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 A303564 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Max[0, Exponent[p, x]]}]][b[Range[n], 0, 0]];
%t A303564 Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, May 31 2018, from Maple *)
%Y A303564 Columns k=0-1 give: A001045(n-1) for n>0, A301272.
%Y A303564 Row sums give A000166.
%Y A303564 Cf. A008303 (the same for permutations), A004526, A129815, A129817, A162979, A162980, A216963, A303648 (the same for involutions).
%K A303564 nonn,tabf
%O A303564 0,6
%A A303564 _Alois P. Heinz_, Apr 26 2018