

A184182


Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest 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 5412367 has 4 blocks: 5, 4, 123, and 67. Its longest block has length 3.


1



1, 1, 1, 3, 2, 1, 11, 10, 2, 1, 53, 53, 11, 2, 1, 309, 334, 63, 11, 2, 1, 2119, 2428, 415, 64, 11, 2, 1, 16687, 20009, 3121, 425, 64, 11, 2, 1, 148329, 184440, 26402, 3205, 426, 64, 11, 2, 1, 1468457, 1881050, 248429, 27145, 3215, 426, 64, 11, 2, 1, 16019531, 21034905, 2575936, 255479, 27229, 3216, 426, 64, 11, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Sum of entries in row n is n!.
T(n,1)=A000255(n).


LINKS

Table of n, a(n) for n=0..65.


FORMULA

T(n,k)=Sum[(b(n,m,k)b(n,m,k1))(d(m)+d(m1)), m=1..n), 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;
1,1;
3,2,1;
11,10,2,1;
53,53,11,2,1;
309,334,63,11,2,1;


MAPLE

d[0] := 1: for n to 40 do d[n] := n*d[n1]+(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[m1]), m = 1 .. n)add(b(n, m, k1)*(d[m]+d[m1]), m = 1 .. n) end proc: for n to 11 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form


CROSSREFS

Cf. A000255, A000166, A184180
Sequence in context: A104219 A123513 A117442 * A118435 A115085 A110616
Adjacent sequences: A184179 A184180 A184181 * A184183 A184184 A184185


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Feb 13 2011


STATUS

approved



