login
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.
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).
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Feb 13 2011
STATUS
approved