A184180 - cp's OEIS frontend

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.

%I A184180 #18 Sep 19 2024 04:52:57
%S A184180 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 A184180 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 A184180 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 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.
%C A184180 Sum of entries in row n is n!.
%C A184180 T(n,1) = A184181(n).
%F A184180 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 A184180 T(5,2) = 2 because we have 45123 and 34512.
%e A184180 Triangle starts:
%e A184180     1;
%e A184180     1, 1;
%e A184180     5, 0, 1;
%e A184180    22, 1, 0, 1;
%e A184180   117, 2, 0, 0, 1;
%e A184180   713, 5, 1, 0, 0, 1;
%e A184180   ...
%p A184180 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 A184180 T[n_, k_] := With[{d = Subfactorial},
%t A184180    Sum[Binomial[n-(k-1)*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/k]}] -
%t A184180    Sum[Binomial[n-k*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/(k+1)]}]];
%t A184180 Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 18 2024, after Maple code *)
%Y A184180 Cf. A000142, A000166, A184181, A184182.
%K A184180 nonn,tabl
%O A184180 1,4
%A A184180 _Emeric Deutsch_, Feb 13 2011

cp's OEIS Frontend