Что такое факториал и как его вычислить

Факториал числа — это фундаментальная математическая функция, обозначаемая символом восклицательного знака (!) после числа. Если n — это натуральное число, его факториал (n!) определяется как произведение всех целых чисел от 1 до n. Формально:

n!=n(n-1)(n-2)...1.

Например:

5!=5⋅4⋅3⋅2⋅1=120.

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

Сейчас же эта функция всё ещё очень актуальна, ибо лежит в основе многих распределений теории вероятностей, а следовательно, повсеместно встречается в Data Science. Но помимо неё, конечно, исследователям, нужно разбираться в линейной алгебре, математическом анализе и обязательно — в статистике. Этому можно научиться на курсе «Математика для анализа данных».

1. Быстрый рост

Факториал n! растёт чрезвычайно быстро по мере увеличения n.

Например:

5!=120;
10!=3 628 800;
20!=2,432902⋅10^18.

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

2. Чётность

Факториал любого числа n при n > 1 является чётным числом, поскольку
n!=n(n-1)...2⋅1, то есть в числе множителей всегда будет число 2.

3. Нулевая основа

Определение 0! = 1 является аксиоматическим и обусловлено необходимостью согласования математических формул. Например, формула расчёта числа комбинаций и биномиальных коэффициентов:

была бы некорректной без этой аксиомы.

4. Связь с числами комбинаций

Исторически функция факториала появилась как средство для подсчёта числа перестановок. Перестановка — это один из возможных способов упорядочить элементы множества. Например, если имеется три элемента, то число их перестановок равно 3!=3⋅2⋅1=6. В более общем виде факториал даёт ответ на вопрос, сколько есть способов, чтоб упорядочить n элементов.

Все возможные перестановки трёх элементов

5. Асимптотическое поведение

Факториал демонстрирует определённые закономерности при стремлении к бесконечности:

где ln(n!) растёт линейно относительно n⋅ln(n). Это свойство используется в аналитической теории чисел.

6. Обобщение через гамма-функцию

Факториал целого числа n является частным случаем гамма-функции:

n!=Γ(n+1).

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

7. Остатки факториала

Факториал обладает интересными свойствами в теории чисел, связанными с делением на простые числа. Например, если p — простое число, то:

(p-1)!≡-1(mod p).

Это свойство известно как теорема Вильсона и является основой для доказательства простоты конкретных чисел.

Факториал может быть вычислен разными способами в зависимости от задачи и доступных инструментов. Рассмотрим основные подходы.

1. Рекурсия

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

n!=n⋅(n-1)!

Базовым случаем здесь является 0!=1!=1. Такой подход удобен для программирования, но может быть ресурсоёмким для больших значений n.

2. Итеративный метод

Итеративное вычисление основывается на последовательном умножении чисел от 1 до n:

n!=1⋅2⋅3⋅...⋅n.

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

3. Формула Стирлинга

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

Эта формула полезна в прикладной математике и статистике, где не требуется абсолютная точность. Также можно утверждать, что

4. Обобщение через гамма-функцию

В теории функций факториал обобщается с использованием гамма-функции, которая определена следующим образом:

n!=Γ(n+1).

Здесь Γ(x) (или Gamma(x)) — это гамма-функция, которая расширяет определение факториала на все вещественные и комплексные числа, кроме чисел с неположительной вещественной частью. Определяется она следующим образом:

где z — комплексное число с положительной вещественной частью.

5. Табличные значения

Для небольших значений n факториалы часто хранятся в таблицах или вычисляются заранее. Например:

0! = 1;
1! = 1;
2! = 2;
3! = 6;
4! = 24;
5! = 120.

Таблицы позволяют сократить время вычислений в прикладных задачах.

Попробуем оценить 10! с использованием формулы Стирлинга:

Рассчитав приблизительное значение, получаем:

10! ≈ 3 598 696.

Для сравнения, точное значение 10! = 3 628 800, что показывает высокую точность формулы Стирлинга, поскольку погрешность составила менее 1%.

Подсчёт же точных значений факториала интереснее рассматривать на примерах, связанных с программированием. К примеру, вот так можно посчитать факториал числа n с помощью Python:

В цикле for числа поочерёдно домножаются к результату, в котором по окончании работы цикла и будет содержаться нужное число

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

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

В прикладных задачах лучше всего для подсчёта факториала использовать готовые функции из оптимизированных математических библиотек.

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

В комбинаторике факториал используется для подсчёта числа перестановок, сочетаний и размещений. Например:
● Число перестановок n элементов равно n!.
● Формула для сочетаний с использованием факториала:

Эта формула позволяет найти число способов выбрать k элементов из n.

2. Теория вероятностей

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

где k — ожидаемое число успехов в n испытаниях, вероятность успеха в каждом равна p.

3. Математический анализ

В математическом анализе факториал появляется в разложениях функций в ряды. Например, разложение экспоненты в ряд Тейлора имеет вид:

Здесь факториал в знаменателе играет роль нормализующего множителя.

4. Статистика

В статистике, как и в теории вероятностей, факториал применяется при вычислении различных распределений для случайных процессов, например пуассоновского. Формула для вероятности в этом распределении включает n! в знаменателе:

где k — количество событий, λ — математическое ожидание случайной величины.