A001455 Number of permutations of length n with longest increasing subsequence of length 4. (Formerly M5016 N2161)

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

Alois P. Heinz, Table of n, a(n) for n = 4..300

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

Adjacent sequences: A001452 A001453 A001454 * A001456 A001457 A001458

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Alois P. Heinz, Jul 01 2012

Name of the sequence clarified by Vaclav Kotesovec, Mar 18 2014

Status

approved