%I #18 Sep 19 2024 04:52:57
%S 1,1,1,5,0,1,22,1,0,1,117,2,0,0,1,713,5,1,0,0,1,5026,11,2,0,0,0,1,
%T 40285,31,2,1,0,0,0,1,362799,73,5,2,0,0,0,0,1,3628584,201,11,2,1,0,0,
%U 0,0,1,39916243,532,20,2,2,0,0,0,0,0,1,479000017,1534,40,5,2,1,0,0,0,0,0,1,6227016356,4346,82,11,2,2,0,0,0,0,0,0,1
%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose shortest block is of length k (1 <= k <= n). A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 4512367 has 3 blocks: 45, 123, and 67. Its shortest block has length 2.
%C Sum of entries in row n is n!.
%C T(n,1) = A184181(n).
%F T(n,k) = Sum_{m=1..floor(n/k)} binomial(n-(k-1)*m-1, m-1)*(d(m) + d(m-1)) - Sum_{m=1..floor(n/(k+1))} binomial(n-km-1, m-1)*(d(m) + d(m-1)), where d(j) = A000166(j) are the derangement numbers.
%e T(5,2) = 2 because we have 45123 and 34512.
%e Triangle starts:
%e 1;
%e 1, 1;
%e 5, 0, 1;
%e 22, 1, 0, 1;
%e 117, 2, 0, 0, 1;
%e 713, 5, 1, 0, 0, 1;
%e ...
%p d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) options operator, arrow: sum(binomial(n-(k-1)*m-1, m-1)*(d[m]+d[m-1]), m = 1 .. floor(n/k))-(sum(binomial(n-k*m-1, m-1)*(d[m]+d[m-1]), m = 1 .. floor(n/(k+1)))) end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form
%t T[n_, k_] := With[{d = Subfactorial},
%t Sum[Binomial[n-(k-1)*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/k]}] -
%t Sum[Binomial[n-k*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/(k+1)]}]];
%t Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 18 2024, after Maple code *)
%Y Cf. A000142, A000166, A184181, A184182.
%K nonn,tabl
%O 1,4
%A _Emeric Deutsch_, Feb 13 2011