|
|
A001454
|
|
Number of permutations of length n with longest increasing subsequence of length 3.
(Formerly M4640 N1983)
|
|
7
|
|
|
1, 9, 61, 381, 2332, 14337, 89497, 569794, 3704504, 24584693, 166335677, 1145533650, 8017098273, 56928364553, 409558170361, 2981386305018, 21935294881644, 162951791097669, 1221201051018189, 9225637750090023, 70209505971502533, 537934326588404973
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,2
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
J. M. Hammersley, A few seedings of research, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.
|
|
FORMULA
|
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
(18*(n-1)*(2*n-5)*(3*n^2+2*n-3)*(n-2)^2*a(n-3)
-(n-1)*(147*n^5-553*n^4+199*n^3+937*n^2-790*n+96)*a(n-2)
+(n+1)*(42*n^5-146*n^4+21*n^3+171*n^2+14*n-48)*a(n-1))/
((n-3)*(n+1)*(3*n^2-4*n-2)*(n+2)^2)))
end:
|
|
MATHEMATICA
|
h[l_List] := Module[{n = Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_List] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; T[n_] := Table[g[n-k, Min[n-k, k], {k}], {k, 1, n}]; Table[T[n], {n, 3, 24}][[All, 3]] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)hotmail.com), Oct 17 2005
|
|
STATUS
|
approved
|
|
|
|