A184182 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).

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, 2119, 2428, 415, 64, 11, 2, 1, 0, 16687, 20009, 3121, 425, 64, 11, 2, 1, 0, 148329, 184440, 26402, 3205, 426, 64, 11, 2, 1, 0, 1468457, 1881050, 248429, 27145, 3215, 426, 64, 11, 2, 1

Offset: 0

Author

Emeric Deutsch, Feb 13 2011

Keywords

• nonn
• tabl

Comments

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.

Examples

			T(3,1) = 3 because we have 132, 213, and 321.
T(4,3) = 2 because we have 4123 and 2341.
Triangle starts:
  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;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

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

Cf. A000166, A184180.

Row sums are A000142.

Programs

Maple

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

Mathematica

b[n_, m_, k_] := Module[{t}, Coefficient[Total[t^Range[k]]^m, t, n]];
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}]]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 06 2024 *)

Formula

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.

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

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

Extensions

Row n=0 and column k=0 added by Alois P. Heinz, Feb 17 2024