Как приготовить формулу Стирлинга

Все мы любим кошек. Многие даже умеют их готовить. Если у нас есть пятьдесят кошек и пятьдесят печек, то вариантов — сколько может быть комбинаций распихать кошек по печкам — будет факториал от пятидесяти.

744d29cf7f1dd1222539603b7ad089e7.jpg

Все мы знаем что такое факториал. Мы знаем, что вариантов куда запихать первую кошку будет 50, а у второй уже 49, и значит количество рассчитываемых вариантов на второй кошке будет 50×49 = 2450. Пока мы дойдём до последней кошки то все числа от 50 до 2 будут уже перемножены. И у нас останется одна свободная печка, куда мы последнюю кошку и запихнём.

И пока печки не включены, можно немного подумать, вдруг какой-нибудь из других 30414093201713378043612608166064768844377641568960511999999999999 вариантов расстановки был бы получше.

Умножать столько раз, каков сам аргумент, и каждый раз — на другое число, может быть утомительно. И точно дольше по сравнению с простым возведением в степень. В справочниках существует загадочная формула Стирлинга, которая помогает подсчитать количество вариантов как раз с этой особенностью — не с полной точностью, но зато через возведение в степень.

Я расскажу как в отсутствие справочника можно приготовить формулу Стирлинга в домашних условиях.

Для этого нам понадобится две вещи:

  1. Разложение логарифма.

\ln(1+x)=\sum_{k=1}^{\infty}-\frac{(-x)^k}{k} \qquad |x|<1

И

  1. Особенное соотношение двух переменных.

\frac{1+x}{1-x}=\frac{n+1}{n+0}

Которое может быть получено из обыкновенного равенства:

x=\frac{1}{2n+1}

Сначала мы применяем логарифм к соотношению и закатываем всё в одну строку.

\ln(1+n^{-1})=\ln(1+x)-\ln(1-x)

Затем применяем разложение.

\ln(1+n^{-1})=\sum_{k=1}^\infty-\frac{(-x)^k}{k}+\sum_{k=1}^\infty\frac{x^k}{k}

Важно разделить чётные и нечётные элементы.

\ln(1+n^{-1})={\small\sum_{k=0}^\infty-\frac{(-x)^{2k+1}}{2k+1}+\sum_{k=0}^\infty-\frac{(-x)^{2k+2}}{2k+2}+\sum_{k=0}^\infty\frac{x^{2k+2}}{2k+2}+\sum_{k=0}^\infty\frac{x^{2k+1}}{2k+1}}

Парочка сумм в центре растворится, а оставшаяся парочка, наоборот, усилится.

\ln(1+n^{-1})=2\sum_{k=0}^\infty\frac{x^{2k+1}}{2k+1}

Аккуратно выносим xиз суммы.

\ln(1+n^{-1})=2x\sum_{k=0}^\infty\frac{x^{2k}}{2k+1}

И заменяем его на n.

\ln(1+n^{-1})=\frac{1}{n+\frac{1}{2}}\sum_{k=0}^\infty\frac{(2n+1)^{-2k}}{2k+1}

Переносим коэффициент влево, и убираем добавленный в самом начале логарифм, с помощью экспоненты.

(1+n^{-1})^{n+\frac{1}{2}}=\exp\sum_{k=0}^\infty\frac{(2n+1)^{-2k}}{2k+1}

Теперь нужно так же аккуратно вынести из суммы вариант с k=0и перенести его влево.

\frac{\left(1+\frac{1}{n}\right)^{n+\frac{1}{2}}}{e}=\exp\sum_{k=1}^\infty\frac{(2n+1)^{-2k}}{2k+1}

А теперь очень необычная операция: перемножаем сразу все варианты для аргумента n.

\prod_{n=1}^\infty\frac{\left(1+\frac{1}{n}\right)^{n+\frac{1}{2}}}{e}=\exp\sum_{n=1}^\infty\sum_{k=1}^\infty\frac{(2n+1)^{-2k}}{2k+1}

Всё это закладываем в калькулятор и считаем до появления числа \pi.

\prod_{n=1}^\infty\frac{\left(1+\frac{1}{n}\right)^{n+\frac{1}{2}}}{e}=\frac{e}{\sqrt{2\pi}}

После того как достали из калькулятора ждём пока верхний предел остынет, и справа появится коэффициент расхождения.

\prod_{n=1}^k\frac{\left(1+\frac{1}{n}\right)^{n+\frac{1}{2}}}{e}=c_k\frac{e}{\sqrt{2\pi}}

Теперь по рецепту следует раскрыть произведение через все элементы.

\frac{\left(\frac{2}{1}\right)^{1+\frac{1}{2}}}{e}\cdot\frac{\left(\frac{3}{2}\right)^{2+\frac{1}{2}}}{e}\cdot\frac{\left(\frac{4}{3}\right)^{3+\frac{1}{2}}}{e}\cdot\frac{\left(\frac{5}{4}\right)^{4+\frac{1}{2}}}{e}\cdot\ldots\cdot\frac{\left(\frac{k+1}{k}\right)^{k+\frac{1}{2}}}{e} =c_k\frac{e}{\sqrt{2\pi}}

Здесь можно заметить, что для каждой пары соседних множителей числитель левой дроби и знаменатель правой дроби одинаковые, а значит могли бы быть полностью сокращены, если бы степени не отличались. А так как на единицу отличаются, то от каждой дроби остаётся знаменатель, и в результате в общем знаменателе появляется факториал.

\frac{(k+1)^{k+1/2}}{k! \;\; e^k}=c_k\frac{e}{\sqrt{2\pi}}

Теперь добавимn, только это будет совсем другой n, он будет равен k+1.

\frac{n^{n-1/2}}{(n-1)! \;\; e^{n-1}}=c_k\frac{e}{\sqrt{2\pi}}

Всё почти готово, последние шаги. Числитель и знаменатель в левой слева части надо оба умножить на n. И обе части равенства поделить на e.

\frac{n^{n+1/2}}{n! \; e^{n}}=c_k\frac{1}{\sqrt{2\pi}}

Вот и всё, если выразить факториал через остальное, то получится

c_k\cdot n!=\sqrt{2\pi n}\left(n/e\right)^n

Или

n! \approx \sqrt{2\pi n}\left(n/e\right)^n

Формула Стирлинга готова. Пользуйтесь.

Сравним результаты.

50!\approx \sqrt{2\pi\cdot 50}(50/e)^{50}

30414093201713378043612608166064768844377641568960512000000000000

30363445939381558207983726752112093959052599802286296951906806786,885…

Различие менее 0,17%. Отлично. А с увеличением аргумента точность только возрастает.

Коэффициент расхождения можно принять c_k=1/(1+1/(12n)), будет ещё точнее.

30414051682613860804997032963365614115651020801956774113493318131,530…

Различие меньше 0,00014%.

Итак, считаю, формула даёт качественное приближение, будет полезной для приготовления самых различных любимых блюд. Вкусного вам вечера!

© Habrahabr.ru