17.04.2023 16:46
yurixi 7 2400 Источник

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

Все мы знаем что такое факториал. Мы знаем, что вариантов куда запихать первую кошку будет 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%.

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

Комментарии (7)


  1. mobi
    17.04.2023 17:08
    #25456356

    Обычно результат еще умножают на 1+1/(12n). См. ряд Стирлинга для гамма-функции.


    1. yurixi Автор
      17.04.2023 17:08
      #25456372

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


  1. v1000
    17.04.2023 17:08
    #25456552

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


  1. SourenTopchian
    17.04.2023 17:08
    #25456910

    1. Стирилинг

    2. Стрилинг

    3. Стирлинг


    1. yurixi Автор
      17.04.2023 17:08
      #25456932

      Вот это да, опечатка прямо в названии. Была.


  1. hydroargerum
    17.04.2023 17:08
    #25458608
    +2

    Это наверное оффтоп, но кажется, чтобы посчитать факториал (точно!) в любом разумном диапазоне значений нужно меньше вычислений, чем с помощью формулы Стирлинга. Или на каком-то диапазоне ф.Стирлинга становится вычислительно быстрее?

    P.S. Приготовление кошек осуждаю, их нужно почёсывать за ушком


    1. h1pp0
      17.04.2023 17:08
      #25459732
      +1

      Зависит от границ "разумного диапазона". У формулы Стирлинга асимптотика лучше -- logN операций благодаря быстрому умножению