login
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).
6

%I #29 Aug 06 2024 14:36:21

%S 1,0,1,0,1,1,0,3,2,1,0,11,10,2,1,0,53,53,11,2,1,0,309,334,63,11,2,1,0,

%T 2119,2428,415,64,11,2,1,0,16687,20009,3121,425,64,11,2,1,0,148329,

%U 184440,26402,3205,426,64,11,2,1,0,1468457,1881050,248429,27145,3215,426,64,11,2,1

%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).

%C A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67. Its longest block has length 3.

%H Alois P. Heinz, <a href="/A184182/b184182.txt">Rows n = 0..140, flattened</a>

%F T(n,k) = Sum_{m=1..n} (b(n,m,k)-b(n,m,k-1))*(d(m)+d(m-1)), where b(n,m,k) = coefficient of t^n in (t+t^2+...+t^k)^m and d(j) = A000166(j) are the derangement numbers.

%F T(n,1) = A000255(n-1) for n>=1.

%F Sum_{k=1..n} T(n,k) = n! (row sums).

%e T(3,1) = 3 because we have 132, 213, and 321.

%e T(4,3) = 2 because we have 4123 and 2341.

%e Triangle starts:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 3, 2, 1;

%e 0, 11, 10, 2, 1;

%e 0, 53, 53, 11, 2, 1;

%e 0, 309, 334, 63, 11, 2, 1;

%e ...

%p d[-1]:= 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, m, k) options operator, arrow: coeff(add(t^j, j = 1 .. k)^m, t, n) end proc: T := proc (n, k) options operator, arrow: add(b(n, m, k)*(d[m]+d[m-1]), m = 0 .. n)-add(b(n, m, k-1)*(d[m]+d[m-1]), m = 1 .. n) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

%t b[n_, m_, k_] := Module[{t}, Coefficient[Total[t^Range[k]]^m, t, n]];

%t T[n_, k_] := If[n == 0, 1, Module[{d = Subfactorial}, Sum[(b[n, m, k] - b[n, m, k-1])*(d[m]+d[m-1]), {m, 1, n}]]];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 06 2024 *)

%Y Columns k=0..3 give A000007, A000255(n-1), A370390, A370392.

%Y Cf. A000166, A184180.

%Y Row sums are A000142.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Feb 13 2011

%E Row n=0 and column k=0 added by _Alois P. Heinz_, Feb 17 2024