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

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, 40285, 31, 2, 1, 0, 0, 0, 1, 362799, 73, 5, 2, 0, 0, 0, 0, 1, 3628584, 201, 11, 2, 1, 0, 0, 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

Offset: 1

Author

Emeric Deutsch, Feb 13 2011

Keywords

• nonn
• tabl

Comments

Sum of entries in row n is n!.

T(n,1) = A184181(n).

Examples

			T(5,2) = 2 because we have 45123 and 34512.
Triangle starts:
    1;
    1, 1;
    5, 0, 1;
   22, 1, 0, 1;
  117, 2, 0, 0, 1;
  713, 5, 1, 0, 0, 1;
  ...
		

Crossrefs

Cf. A000142, A000166, A184181, A184182.

Programs

Maple

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

Mathematica

T[n_, k_] := With[{d = Subfactorial},
   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)]}]];
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 18 2024, after Maple code *)

Formula

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.