|
|
A008304
|
|
Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k.
|
|
27
|
|
|
1, 1, 1, 1, 4, 1, 1, 16, 6, 1, 1, 69, 41, 8, 1, 1, 348, 293, 67, 10, 1, 1, 2016, 2309, 602, 99, 12, 1, 1, 13357, 19975, 5811, 1024, 137, 14, 1, 1, 99376, 189524, 60875, 11304, 1602, 181, 16, 1, 1, 822040, 1960041, 690729, 133669, 19710, 2360, 231, 18, 1, 1, 7477161
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
Row n has n terms.
|
|
REFERENCES
|
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. of column k: 1/Sum_{n>=0} ((k+1)*n+1-x)*x^((k+1)*n)/((k+1)*n+1)! - 1/Sum_{n>=0} (k*n+1-x)*x^(k*n)/(k*n+1)!. - Alois P. Heinz, Oct 13 2013
|
|
EXAMPLE
|
Triangle T(n,k) begins:
1;
1, 1;
1, 4, 1;
1, 16, 6, 1;
1, 69, 41, 8, 1;
1, 348, 293, 67, 10, 1;
...
T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.
|
|
MAPLE
|
b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
`if`(max(t, u)+o<k, 0, add(b(u+j-1, o-j, t+1, k), j=1..o)+
add(b(u-j, o+j-1, 1, k), j=1..u)))
end:
T:= (n, k)-> b(0, n, 0, k) -b(0, n, 0, k+1):
|
|
MATHEMATICA
|
b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u]+o < k, 0, Sum[b[u+j-1, o-j, t+1, k], {j, 1, o}] + Sum[b[u-j, o+j-1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k+1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Jan 10 2014, translated from Alois P. Heinz's Maple code *)
(*additional code*)
nn=12; a[r_]:=Apply[Plus, Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i, {i, 1, r}]), {x, 0, nn}]][[n]]/(n+r)!, {n, 1, nn-r}]]/.y->-1; Map[Select[#, #>0&]&, Transpose[Prepend[Table[Drop[Range[0, nn]! CoefficientList[Series[1/(1-x-a[n+1])-1/(1-x-a[n]), {x, 0, nn}], x], 1], {n, 1, 8}], Table[1, {nn}]]]]//Grid (* Geoffrey Critzer, Feb 25 2014 *)
|
|
CROSSREFS
|
T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|