A001456 Number of permutations of length n with longest increasing subsequence of length 5. (Formerly M5183 N2251)

1, 25, 421, 6105, 83029, 1100902, 14516426, 192422979, 2579725656, 35098717902, 485534447114, 6835409506841, 97966603326993, 1429401763567226, 21226755241285022, 320692032888290224, 4926576077469905280, 76913478420068425515, 1219520974164038038455

Offset

5,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

Vaclav Kotesovec, Table of n, a(n) for n = 5..700 (first 100 terms from Alois P. Heinz)

R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.

Formula

Recurrence: (n-5)*(n+3)^3*(n+4)^2*(n+6)^2*(11025*n^8 + 25515*n^7 - 286443*n^6 - 161641*n^5 + 2585080*n^4 - 59048*n^3 - 7819612*n^2 + 146328*n + 7254720)*a(n) = (n+3)^2*(606375*n^14 + 6629175*n^13 - 3194685*n^12 - 243068077*n^11 - 448185134*n^10 + 2897169968*n^9 + 6909605819*n^8 - 18854806947*n^7 - 49141228309*n^6 + 52949408689*n^5 + 157003723774*n^4 - 31022236184*n^3 - 177627829824*n^2 - 22499155440*n + 46832450400)*a(n-1) - (n-1)*(11278575*n^15 + 107036370*n^14 - 128493459*n^13 - 3499379232*n^12 - 3757671198*n^11 + 38759610078*n^10 + 60611718946*n^9 - 233170832954*n^8 - 421914005785*n^7 + 715791177016*n^6 + 1483014906497*n^5 - 861954416990*n^4 - 2293879983512*n^3 + 206528474736*n^2 + 1232273843856*n + 13490305056)*a(n-2) + (n-2)^2*(n-1)*(84286125*n^13 + 498481200*n^12 - 2434626540*n^11 - 13242031168*n^10 + 26565838790*n^9 + 116444106688*n^8 - 166166829480*n^7 - 520627558844*n^6 + 548244457053*n^5 + 1265779705376*n^4 - 798189974324*n^3 - 1219994476884*n^2 + 526747368888*n + 238058922240)*a(n-3) - 2*(n-3)^2*(n-2)^2*(n-1)*(116181450*n^11 + 631786995*n^10 - 3196642374*n^9 - 12497984441*n^8 + 40113159004*n^7 + 67582342915*n^6 - 249420026774*n^5 - 74467478051*n^4 + 592968590146*n^3 - 201054848490*n^2 - 142917171372*n - 573108048)*a(n-4) + 14400*(n-4)^2*(n-3)^3*(n-2)^2*(n-1)*(11025*n^8 + 113715*n^7 + 200862*n^6 - 727084*n^5 - 854995*n^4 + 4446427*n^3 + 2445184*n^2 - 7589778*n + 1695924)*a(n-5). - Vaclav Kotesovec, Mar 16 2014

a(n) ~ 9 * 5^(2*n+25/2) / (2^9 * Pi^2 * n^12). - Vaclav Kotesovec, Mar 16 2014

Crossrefs

Column k=5 of A047874.

Sequence in context: A025975 A025953 A020595 * A021964 A022456 A020593

Adjacent sequences: A001453 A001454 A001455 * A001457 A001458 A001459

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