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

%I M5016 N2161 #34 Feb 03 2022 00:50:24

%S 1,16,181,1821,17557,167449,1604098,15555398,153315999,1538907306,

%T 15743413076,164161815768,1744049683213,18865209953045,

%U 207591285198178,2321616416280982,26362085777156567,303635722412859447,3544040394934246209,41881891423602685193

%N Number of permutations of length n with longest increasing subsequence of length 4.

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001455/b001455.txt">Table of n, a(n) for n = 4..300</a>

%H R. M. Baer and P. Brock, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0228216-8">Natural sorting over permutation spaces</a>, Math. Comp. 22 1968 385-410.

%F 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

%F a(n) ~ 3 * 2^(4*n+9) / (Pi^(3/2) * n^(15/2)). - _Vaclav Kotesovec_, Mar 15 2014

%Y Column k=4 of A047874.

%K nonn

%O 4,2

%A _N. J. A. Sloane_

%E More terms from _Alois P. Heinz_, Jul 01 2012

%E Name of the sequence clarified by _Vaclav Kotesovec_, Mar 18 2014