[go: up one dir, main page]

login
A001455
Number of permutations of length n with longest increasing subsequence of length 4.
(Formerly M5016 N2161)
3
1, 16, 181, 1821, 17557, 167449, 1604098, 15555398, 153315999, 1538907306, 15743413076, 164161815768, 1744049683213, 18865209953045, 207591285198178, 2321616416280982, 26362085777156567, 303635722412859447, 3544040394934246209, 41881891423602685193
OFFSET
4,2
REFERENCES
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.
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
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
FORMULA
Recurrence: (n-4)*(n+2)^2*(n+3)^2*(n+4)*(225*n^5 - 180*n^4 - 1713*n^3 + 1354*n^2 + 3326*n - 1604)*a(n) = (n+2)^2*(6750*n^9 - 4500*n^8 - 128025*n^7 + 28068*n^6 + 758512*n^5 - 184396*n^4 - 1719825*n^3 + 606292*n^2 + 573428*n - 274224)*a(n-1) - (n-1)*(61425*n^10 - 39915*n^9 - 1118034*n^8 + 644778*n^7 + 5929529*n^6 - 4355935*n^5 - 10322152*n^4 + 7841792*n^3 + 4333856*n^2 - 3087760*n - 58944)*a(n-2) + 2*(n-2)^2*(n-1)*(92250*n^8 - 88875*n^7 - 1380300*n^6 + 1835846*n^5 + 4241004*n^4 - 9250339*n^3 + 4259094*n^2 + 1427720*n - 1155840)*a(n-3) - 576*(n-3)^2*(n-2)^3*(n-1)*(225*n^5 + 945*n^4 - 183*n^3 - 2615*n^2 + 1300*n + 1408)*a(n-4). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ 3 * 2^(4*n+9) / (Pi^(3/2) * n^(15/2)). - Vaclav Kotesovec, Mar 15 2014
CROSSREFS
Column k=4 of A047874.
Sequence in context: A016305 A218895 A016909 * A199018 A204608 A279282
KEYWORD
nonn
EXTENSIONS
More terms from Alois P. Heinz, Jul 01 2012
Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014
STATUS
approved