Формула Стирлинга в комбинаторике¶

Формула Стирлинга — асимптотическая формула для приближённого вычисления факториала больших чисел. Она выражает значение \(n!\) через элементарные функции и играет ключевую роль в комбинаторике, теории вероятностей, статистической физике и анализе алгоритмов, где факториалы больших порядков вычислять напрямую затруднительно.

¶Формулировка

Классическая формула Стирлинга имеет вид:

\[ n! \sim \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^n \]

Знак \(\sim\) означает асимптотическую эквивалентность: отношение левой и правой частей стремится к единице при \(n \to \infty\). Иначе говоря,

\[ \lim_{n\to\infty} \frac{n!}{\sqrt{2\pi n}\,(n/e)^n} = 1. \]

Для практических вычислений часто используют логарифмическую форму:

\[ \ln n! = n\ln n - n + \tfrac{1}{2}\ln(2\pi n) + O\!\left(\frac{1}{n}\right). \]

¶История

Формулу получил шотландский математик Джеймс Стирлинг в 1730 году в работе «Methodus differentialis». Близкий результат ранее рассматривал Абрахам де Муавр, изучавший биномиальные коэффициенты и нормальное распределение; поэтому в англоязычной литературе закрепляется двойное название — формула Стирлинга — Муавра. Стирлинг предложил не только главный член, но и уточняющие поправки, что делает формулу пригодной уже при небольших \(n\).

¶Уточнения и ряд

Точное разложение в асимптотический ряд имеет вид:

\[ 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} - \cdots\right). \]

Коэффициенты этого ряда связаны с числами Бернулли. Уже первый поправочный член \(1/(12n)\) даёт высокую точность: например, для \(n = 10\) относительная погрешность главного члена составляет около 0,8 %, а с поправкой — доли процента. При \(n = 1\) формула даёт \(\sqrt{2\pi}/e \approx 0{,}922\), тогда как \(1! = 1\).

¶Оценки и границы

Помимо асимптотики, существуют двусторонние неравенства, удобные в доказательствах:

\[ \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n+1)} < n! < \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n)}. \]

Эти оценки показывают, что формула Стирлинга не только приближает, но и ограничивает факториал сверху и снизу, что важно при строгих выкладках в комбинаторике и теории чисел.

¶Применение

¶Комбинаторика

Формула позволяет оценивать число перестановок, размещений и сочетаний при больших \(n\). Например, для центрального биномиального коэффициента \(\binom{2n}{n}\) получается асимптотика \(\sim 4^n/\sqrt{\pi n}\), что используется при анализе случайных блужданий и распределения вероятностей.

¶Теория вероятностей

Формула лежит в основе вывода локальной теоремы Муавра — Лапласа и приближения биномиального распределения нормальным. Она связывает дискретные вероятности с непрерывной гауссовой кривой.

¶Статистическая физика

В выводе распределения Максвелла — Больцмана и в вычислении энтропии через число микросостояний \(\ln W\) формула Стирлинга заменяет факториалы, что позволяет перейти от дискретных сумм к непрерывным выражениям. Именно так получается формула энтропии идеального газа.

¶Анализ алгоритмов

При оценке сложности алгоритмов, связанных с сортировкой, деревьями решений и перебором, формула Стирлинга даёт асимптотику \(\log_2 n! \approx n\log_2 n - n\log_2 e\), откуда следует нижняя граница \(\Omega(n\log n)\) для сортировки сравнениями.

¶Связь с гамма-функцией

Факториал обобщается гамма-функцией Эйлера: \(n! = \Gamma(n+1)\). Формула Стирлинга представляет собой асимптотику гамма-функции:

\[ \Gamma(z+1) \sim \sqrt{2\pi z}\left(\frac{z}{e}\right)^z, \quad z \to \infty. \]

Это позволяет применять формулу к нецелым аргументам и комплексным значениям в аналитической теории чисел.

¶Ошибки и ограничения

Формула асимптотическая: при малых \(n\) она даёт заметную относительную погрешность, поэтому для точных вычислений используют поправочные члены или табличные значения. Кроме того, ряд Стирлинга расходится при любом фиксированном \(n\), будучи лишь асимптотическим: при увеличении числа членов сверх оптимального точность падает. Оптимальное число членов зависит от \(n\) и примерно равно \(\pi n\).

¶Значение

Формула Стирлинга — один из базовых инструментов прикладной математики. Она связывает дискретное (факториал) с непрерывным (степень и корень), что делает возможным аналитическое исследование задач, где прямое вычисление невозможно из-за огромных чисел. Её выводы используются в физике, информатике, статистике и теории информации, в частности при выводе формулы Хартли и оценке количества информации.

Источники: Фихтенгольц Г. М. «Курс дифференциального и интегрального исчисления»; Кнут Д. «Искусство программирования»; Graham R., Knuth D., Patashnik O. «Concrete Mathematics»; справочные материалы по асимптотическому анализу.