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

Comments

Sum of entries in row n is n!.

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

Links

Table of n, a(n) for n=1..91.

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.

Example

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

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

Crossrefs

Cf. A000142, A000166, A184181, A184182.

Sequence in context: A371994 A227322 A216718 * A256069 A356652 A267480

Adjacent sequences: A184177 A184178 A184179 * A184181 A184182 A184183

Keyword

nonn,tabl

Author

Emeric Deutsch, Feb 13 2011

Status

approved