Факториал¶
Факториал — произведение всех натуральных чисел от 1 до заданного натурального числа n, обозначаемое n!. Факториал определяется для неотрицательных целых чисел; по определению 0! = 1. Факториал является одной из базовых функций комбинаторики, теории вероятностей и математического анализа, активно применяется в вычислительной математике и программировании.
¶Определение и свойства
Формально факториал определяется рекуррентно:
- n! = n · (n − 1)! при n ≥ 1
- 0! = 1
Прямое определение: n! = 1 · 2 · 3 · … · n. Значение 0! = 1 не противоречит рекуррентной формуле: из n! = n · (n − 1)! при n = 1 следует 1! = 1 · 0!, откуда 0! = 1. Это соглашение также согласуется с формулой числа перестановок: из n элементов можно составить ровно один способ пустую перестановку.
Основные свойства:
- n! делится на все числа от 1 до n;
- n! растёт быстрее любой степени n при n → ∞ (в частности, n! ≫ n^k для любого фиксированного k);
- отношение (n+1)! / n! = n + 1;
- факториал целого числа не является степенью целого числа при n > 1 (кроме тривиальных случаев) — следствие теоремы Бернулли о числе простых делителей.
Значения факториалов малых чисел:
| n | n! |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5040 |
| 8 | 40320 |
| 9 | 362880 |
| 10 | 3628800 |
¶Расширенные определения
¶Гамма-функция
Факториал целого числа естественным образом продолжается на вещественные и комплексные числа через гамма-функцию Эйлера — Пуассона:
Γ(n) = (n − 1)! для натуральных n.
Гамма-функция определена интегралом Γ(z) = ∫₀^∞ t^(z−1) e^(−t) dt для Re(z) > 0 и аналитически продолжается на всю комплексную плоскость с полюсами в точках z = 0, −1, −2, …. Свойство Γ(z+1) = z·Γ(z) является непрерывным аналогом рекуррентного соотношения для факториала. Через гамма-функцию определяются двойной факториал и функция Барнли.
¶Двойной факториал
Двойной факториал n!! — произведение чисел, одинаковых по чётности с n, до 1 или 2 включительно: например, 7!! = 7·5·3·1 = 105, 8!! = 8·6·4·2 = 384. Связь с обычным факториалом: (2n)!! = 2^n · n!, а (2n−1)!! = (2n)! / (2^n · n!).
¶Подфакториал
Подфакториал !n (число деранжирований) — количество перестановок n элементов, ни один из которых не остаётся на своём месте. Подфакториал удовлетворяет рекуррентной формуле !n = (n − 1)(!(n − 1) + !(n − 2)) и связан с факториалом асимптотикой !n ≈ n!/e.
¶Вычисление
¶Алгоритмы
Наивное вычисление n! требует n − 1 умножений. Для больших n используют более эффективные методы:
- Разбиение на произведение (алгоритм Борхардта — Штейнгаузера): разбиение множителей на подмножества с примерно одинаковым произведением снижает число умножений с O(n log² n) до O(M(n) log n), где M(n) — стоимость умножения двух n-разрядных чисел.
- Алгоритм Сплитинга (Splitting, Брайан Оверхолт): использует разложение факториала в произведение простых чисел с показателями степеней (по формуле Лежандра) и быстрое возведение в степень.
- Асимптотические формулы: формула Стирлинга n! ≈ √(2πn)·(n/e)^n широко используется для приближённых вычислений; более точная версия с поправкой: n! ≈ √(2πn)·(n/e)^n·(1 + 1/(12n)).
¶Точное вычисление больших факториалов
Факториал 100! содержит 158 цифр, 1000! — 2568 цифр, 10^6! — около 5,57 млн цифр. Для точного хранения таких чисел используют большие целые числа (bignum). Крупнейшие вычисленные факториалы на 2020-е годы достигают значений порядка 10^12 и выше (например, 10^12! вычислен полностью и содержит более 10^13 цифр).
¶Применение
¶Комбинаторика
Факториал определяет число перестановок n различных элементов: P(n) = n!. Число размещений A(n, k) = n!/(n−k)!, число сочетаний C(n, k) = n!/(k!(n−k)!). Формула числа перестановок с повторениями n!/(n₁!·n₂!·…·nₖ!) используется при подсчёте анаграмм и распределений.
¶Теория вероятностей и статистика
Факториал входит в формулу Бернулли — Лапласа для биномиального распределения, в определение распределения Пуассона, в формулу Стирлинга при аппроксимации дискретных распределений непрерывными. Статистический критерий хи-квадрат использует гамма-функцию как продолжение факториала.
¶Компьютерная наука
- Сложность алгоритмов сортировки: число перестановок n элементов равно n!, что определяет нижнюю границу сравнений в алгоритмах сортировки сравнениями — log₂(n!) ≈ n log₂ n − n log₂ e (следствие формулы Стирлинга).
- Алгоритмы генерации перестановок (алгоритм Стейнхауса — Джонсона — Троттера) нумеруют перестановки с помощью факториала.
- В криптографии факториалы больших чисел используются в некоторых схемах на основе перестановок.
¶Физика и химия
Факториал появляется в статистической механике при подсчёте микросостояний (формула Больцмана с факториалом для учёта неразличимости частиц), в квантовой теории поля при развёртке рядов возмущений.
¶История
Факториал как понятие возникло в связи с задачами комбинаторики. Кришнаджин (XII век) рассматривал число перестановок в индийской математической традиции. В Европе понятие развивалось в трудах Лейбница (1666), который обсуждал перестановки и их подсчёт. Обозначение n! ввёл Кристиан Крамп в 1808 году. Асимптотическую формулу n! ≈ √(2πn)·(n/e)^n открыл Джеймс Стирлинг в 1730 году (в работах, опубликованных позже, в 1749 году); точный коэффициент √(2π) был установлен Абрахамом де Муавром и Даниилом Бернулли. Гамма-функцию как непрерывное продолжение факториала ввёл Леонард Эйлер в 1729—1730 годах.
¶Интересные факты
- 1! + 2! + 3! + 4! + 5! = 153 — единственная (кроме 1 и 2) сумма факториалов от 1 до n, являющаяся числом Армстронга (сумма цифр в степени числа цифр).
- 145 = 1! + 4! + 5! — число, равное сумме факториалов своих цифр.
- Число перестановок 52-колооды равно 52! ≈ 8,07 × 10^67 — величина, многократно превышающая число атомов в наблюдаемой Вселенной (≈ 10^80).
¶Источники
- Кнут Д. «Искусство программирования», том 1: основные алгоритмы
- Рябов О. И., Ширяев А. Н. «Теория вероятностей»
- Градштейн И. С., Рыжик И. М. «Таблицы интегралов, сумм, рядов и произведений»
- Гнеденко Б. В. «Курс теории вероятностей»
- Справочник по математике (под ред. И. М. Виноградова)
