login
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

%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