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

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,8

Comments

Sum of entries in row n is n!.

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

Links

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

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.

Example

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;
  ...

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

Crossrefs

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

Cf. A000166, A184180.

Row sums are A000142.

Sequence in context: A259790 A246654 A370506 * A085771 A253286 A344499

Adjacent sequences: A184179 A184180 A184181 * A184183 A184184 A184185

Keyword

nonn,tabl

Author

Emeric Deutsch, Feb 13 2011

Extensions

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

Status

approved