|
Contents
Stirling's approximation
Stirling's approximation (or Stirling's formula) is an approximation for large factorials. It is named in honour of James Stirling. Formally, it states:
- <math>\lim_{n \rightarrow \infty} {n!\over \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n} } = 1</math>
which is often written as
- <math>n! \sim \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}</math>
(See limit, square root, π, e.) For large n, the right hand side is a good approximation for n!, and much faster and easier to calculate. For example, the formula gives for 30! the approximation 2.6451 × 1032 while the correct value is about 2.6525 × 1032.
It can be shown that
- <math>n^n \ge n! \ge \left(\frac{n}{2}\right)^\frac{n}{2}</math>
using Stirling's appoximation.
The speed of convergence of the above limit is expressed by the formula
- <math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}\left(1 + \Theta\left(\frac{1}{n}\right)\right)</math>
where Θ(1/n) denotes a function whose asymptotical behavior for n→∞ is like a constant times 1/n; see Big O notation.
More precisely still:
- <math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}e^{\lambda_n}</math>
with
- <math>\frac{1}{12n+1} < \lambda_n < \frac{1}{12n}</math>
The formula, together with precise estimates of its error, can be derived as follows. Instead of approximating n!, one considers the natural logarithm ln(n!) = ln(1) + ln(2) + ... + ln(n); the Euler-Maclaurin formula gives estimates for sums like these. The goal, then, is to show the approximation formula in its logarithmic form:
- <math>\ln n! \approx \left(n+\frac{1}{2}\right)\ln n - n +\ln\left(\sqrt{2\pi}\right)</math>
The formula was first discovered by Abraham de Moivre in the form
- <math>n!\sim [{\rm constant}]\cdot n^{n+1/2} e^{-n}</math>
Stirling's contribution consisted of showing that the "constant"
is <math>\sqrt{2\pi}</math>.
| Elsewhere |  | |
Search engine
Web directory
|
CONTENTS:
|
