Editing Factorial (section)

===Growth and approximation===
[[File:Mplwp factorial stirling loglog2.svg|thumb|Comparison of the factorial, Stirling's approximation, and the simpler approximation {{nowrap|<math>(n/e)^n</math>,}} on a doubly logarithmic scale]]
[[File:Stirling series relative error.svg|thumb|upright=1.6|[[Relative error]] in a truncated Stirling series vs. number of terms]]
{{main|Stirling's approximation}}

As a function {{nowrap|of <math>n</math>,}} the factorial has faster than [[exponential growth]], but grows more slowly than a [[double exponential function]].<ref>{{cite book | last = Cameron | first = Peter J. | author-link = Peter Cameron (mathematician) | contribution = 2.4: Orders of magnitude | isbn = 978-0-521-45133-8 | pages = 12–14 | publisher = Cambridge University Press | title = Combinatorics: Topics, Techniques, Algorithms | year = 1994}}</ref> Its growth rate is similar {{nowrap|to <math>n^n</math>,}} but slower by an exponential factor. One way of approaching this result is by taking the [[natural logarithm]] of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral:
<math display="block">\ln n! = \sum_{x=1}^n \ln x \approx \int_1^n\ln x\, dx=n\ln n-n+1.</math>
Exponentiating the result (and ignoring the negligible <math>+1</math> term) approximates <math>n!</math> as {{nowrap|<math>(n/e)^n</math>.<ref>{{cite book | last = Magnus | first = Robert | contribution = 11.10: Stirling's approximation | contribution-url = https://books.google.com/books?id=5hvxDwAAQBAJ&pg=PA391 | doi = 10.1007/978-3-030-46321-2 | isbn = 978-3-030-46321-2 | location = Cham | mr = 4178171 | page = 391 | publisher = Springer | series = Springer Undergraduate Mathematics Series | title = Fundamental Mathematical Analysis | year = 2020| s2cid = 226465639 }}</ref>}}
More carefully bounding the sum both above and below by an integral, using the [[trapezoid rule]], shows that this estimate needs a correction factor proportional {{nowrap|to <math>\sqrt n</math>.}} The constant of proportionality for this correction can be found from the [[Wallis product]], which expresses <math>\pi</math> as a limiting ratio of factorials and powers of two. The result of these corrections is [[Stirling's approximation]]:<ref>{{cite book | last = Palmer | first = Edgar M. | contribution = Appendix II: Stirling's formula | isbn = 0-471-81577-2 | location = Chichester | mr = 795795 | pages = 127–128 | publisher = John Wiley & Sons | series = Wiley-Interscience Series in Discrete Mathematics | title = Graphical Evolution: An introduction to the theory of random graphs | year = 1985}}</ref>
<math display="block">n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\,.</math>
Here, the <math>\sim</math> symbol means that, as <math>n</math> goes to infinity, the ratio between the left and right sides approaches one in the [[Limit (mathematics)|limit]].
Stirling's formula provides the first term in an [[asymptotic series]] that becomes even more accurate when taken to greater numbers of terms:<ref name="asymptotic">{{cite journal | last1 = Chen | first1 = Chao-Ping | last2 = Lin | first2 = Long | doi = 10.1016/j.aml.2012.06.025 | issue = 12 | journal = Applied Mathematics Letters | mr = 2967837 | pages = 2322–2326 | title = Remarks on asymptotic expansions for the gamma function | volume = 25 | year = 2012| doi-access = free }}</ref>
<math display="block">
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 +\frac{1}{12n}+\frac{1}{288n^2} - \frac{139}{51840n^3} -\frac{571}{2488320n^4}+ \cdots \right).</math>
An alternative version uses only odd exponents in the correction terms:<ref name=asymptotic/>
<math display=block>
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \exp\left(\frac{1}{12n} - \frac{1}{360n^3} + \frac{1}{1260n^5} -\frac{1}{1680n^7}+ \cdots \right).</math>
Many other variations of these formulas have also been developed, by [[Srinivasa Ramanujan]], [[Bill Gosper]], and others.<ref name=asymptotic/>

The [[binary logarithm]] of the factorial, used to analyze [[comparison sort]]ing, can be very accurately estimated using Stirling's approximation. In the formula below, the <math>O(1)</math> term invokes [[big O notation]].<ref name=knuth-sorting>{{cite book|title=The Art of Computer Programming, Volume 3: Sorting and Searching|first=Donald E.|last=Knuth|author-link=Donald Knuth|edition=2nd|publisher=Addison-Wesley|year=1998|isbn=978-0-321-63578-5|page=182|url=https://books.google.com/books?id=cYULBAAAQBAJ&pg=PA182}}</ref>
<math display=block>\log_2 n! = n\log_2 n-(\log_2 e)n + \frac12\log_2 n + O(1).</math>