Факториал, Стирлинг и перестановки

23 December 2020

Есть такая математическая операция как факториал: для натурального числа n это произведение всех натуральных чисел от 1 до n. Обозначается n!. Если записать рекуррентное (или рекурсивное, если угодно) определение 1!=1, (n+1)!=(n+1)n!, то можно получить и факториал нуля: 0!=1, положив n=0. Но дальше таким путем никак не пройти. Да и нужды нет.

Смысл факториала в том, что он выражает число упорядоченных перестановок n предметов. Ну, в самом деле: если предмет один, перестановок и нет, точнее, есть ровно одна. Если больше, то первым можно поставить любой предмет, это n вариантов. Каждому варианту соответствует (n-1)! перестановок меньшего числа предметов.

Если предметов нет вообще, то это "одна" перестановка.

Так, из трех цифр 6, 7 и 8 можно составить шесть трехзначных чисел: 678, 687, 768, 786, 867, 876.

А вот из букв слова МОЛОКО можно составить не 6!=720 шестибуквенных слов, потому что перестановки букв О слова не меняют. Поэтому надо разделить на число перестановок трех букв О, их 3!=6, и получится 5!=120.

Далее комбинаторные формулы быстро размножаются. Число способов выбрать упорядоченный набор из k предметов из n возможных, без повтора, конечно, это n!/(n-k)!. Это легко понять, если упорядочить все предметы и взять k последних; при этом каждому набору соответствует n-k первых, которые (n-k)! способами можно упорядочить, но их порядок нас уже не волнует.

А неупорядоченных наборов из k предметов из n возможных еще в k! раз меньше. Эта формула заслуживает отдельной заметки.

Когда-то были популярны кодовые замки. На нем было десять кнопок с цифрами, и нужно было нажать три или четыре кнопки одновременно, чтобы отпереть замок. Сколько различных кодов и как быстро можно код подобрать?
Мы имеем именно такую задачу. Выбор без повтора и без учета порядка: кнопки нажимаются одновременно. Число кнопок n=10, выбор k=3 или 4. Получается 10!/7!/3!.
Считать это правильно так: сократим множители от 1 до 7, получив 8910/123=4310=120. Для k=4 получим 210. Всего 330 комбинаций, всего-то. Если три секунды положить на проверку комбинации, то за тысячу секунд, то есть минут за двадцать, можно отпереть любой кодовый замок.

Факториал очень быстро растет, быстрее экспоненты. Но медленнее, чем n в степени n. Немного медленнее. Для его приближенного вычисления есть формула Стирлинга:

Все собрались... и пи, и е))
Все собрались... и пи, и е))

Формула асимптотическая: отношение точного значения к приближенному стремится к единице при n к бесконечности. Однако менее известно, что формула неплохо работает и при малых n.

Так, при n=1 Стирлинг дает 0.92 вместо 1, то есть относительная погрешность менее 8%, а далее только убывает: при n=2 Стирлинг дает 1.9 вместо 2 (ошибка 4%), для n=3 имеем 5.8 вместо 6 (ошибка 2.7%), и так далее. И это я еще взял грубые оценки для чисел пи и е.

Формулу вывести точно — не так просто, но грубо — легко. Логарифм факториала есть сумма логарифмов, а ее можно приблизить интегралом:

Факториал, Стирлинг и перестановки

Отсюда получается основная часть, а вот более точные оценки уже хитрее.

Обнаружил вот, что логарифм по основанию 16 от 42! примерно равен 42. Неспроста! Неспроста!!

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

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

Так, такой однострочник

time perl -E 'sub f{my $n=shift;$n>1?return log($n)+f($n-1):return 0}; for(1 .. shift()){say f($_)}' 2000 > 1

работает на моем компьютере 0.685 секунды, а такой:

time perl -E 'for(1 .. shift()){$f=0;for my$i(1..$_){$f+=log($i)}say $f}' 2000 > 2

0.191 секунды: в 3.5 раза быстрее. Оба считают логарифмы факториалов чисел от 1 до 2000.

Да и вообще, факториал надо осторожно считать. Сокращать где надо... В общем, в лоб лучше не переть.

Факториал не вполне подпадает под условия теоремы об аналитическом продолжении (две аналитические функции, совпадающие на множестве с предельно точкой, совпадают повсюду в области определения), но функция, принимающая в точках 1, 2, ... заданные значения существует и может считаться аналитическим продолжением факториала. Это гамма-функция. Точнее, Г(n+1)=n!, но это мелочи. Про нее расскажу в другой раз.

Он. Факториал!
Он. Факториал!

Путеводитель по каналу