Факториал в математике¶
Факториал — это произведение всех натуральных чисел от 1 до данного числа n. Обозначается символом «!» после числа: например, 5! = 5 × 4 × 3 × 2 × 1 = 120. Факториал определён для неотрицательных целых чисел; по определению 0! = 1. Это одна из базовых операций комбинаторики, теории вероятностей и математического анализа, используемая при подсчёте числа перестановок, размещений и сочетаний.
¶Определение и обозначение
Формально факториал числа n определяется как:
n! = 1 × 2 × 3 × … × n = ∏(k=1..n) k
При n = 0 произведение пустое, поэтому по соглашению 0! = 1. Это соглашение не противоречит математике: оно согласуется с формулой сочетаний C(n, k) = n! / (k!(n−k)!) при k = n и упрощает запись множества формул.
Примеры:
| n | n! |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5040 |
| 8 | 40320 |
| 10 | 3628800 |
Факториалы растут чрезвычайно быстро: уже 10! превышает три миллиона, а 20! ≈ 2.43 × 10¹⁸ — больше числа атомов в наблюдаемой Вселенной (оценка ~10⁸⁰, хотя 20! ещё меньше, 70! уже превышает эту величину).
¶Свойства
- Рекуррентная формула: n! = n × (n−1)!. Это свойство позволяет вычислять факториалы итеративно и лежит в основе определения гамма-функции.
- Формула удвоения (Лежандра): (2n)! = 2²ⁿ × (n!)² × (1 × 3 × 5 × … × (2n−1)) / (2n)! — ряд других тождеств, связывающих факториалы чётных и нечётных чисел.
- Формула Стирлинга — асимптотическая аппроксимация для больших n:
n! ≈ √(2πn) × (n/e)ⁿ Относительная погрешность формулы убывает как O(1/n), поэтому для n ≥ 10 она даёт результат с точностью до 0.1 %.
- Разложение в ряд: 1/n! = e × ∫ tⁿ e^(−t) dt от 0 до ∞ (интегральное представление), что позволяет обобщить факториал на вещественные и комплексные числа.
¶История
Символ «!» для обозначения факториала ввёл французский математик Кристиан Крамп в 1808 году. До этого использовались другие обозначения: Лейбниц в 1697 году писал «1.2.3…n», Христиан Вольф — «1.2.3…n», а в XIX веке встречалось обозначение n! в работах Огюстен-Луи Коши и других.
Само понятие возникло раньше символа: в XVII веке факториалы рассматривались при решении задач о перестановках. Якоб Бернулли в трактате «Ars Conjectandi» (1713) исследовал асимптотику факториалов и получил формулу, близкую к формуле Стирлинга. Джеймс Стирлинг опубликовал свою формулу в 1730 году в труде «Methodus Differentialis».
¶Применение
¶Комбинаторика
Число перестановок из n различных элементов равно n!. Число размещений A(n, k) = n! / (n−k)!, число сочетаний C(n, k) = n! / (k!(n−k)!). Факториал — базовая единица измерения «перестановочной мощности»: так, 5! = 120 — количество способов расставить 5 книг на полке.
¶Теория вероятностей
Факториалы входят в формулу Бернулли для биномиального распределения, в формулу Пуассона и в определение распределения Пуассона. Без факториалов невозможно записать вероятность комбинаторных событий.
¶Математический анализ
Факториал лежит в основе гамма-функции Γ(n) = (n−1)!, которая обобщает факториал на вещественные и комплексные числа. Гамма-функция применяется в интегральном исчислении, теории чисел и математической физике.
¶Информатика и вычислительная математика
Факториалы используются в оценках сложности алгоритмов (например, перебор всех перестановок имеет сложность O(n!)), в теории кодирования и в численных методах.
¶Интересные факты
- Факториалы делятся на все числа от 1 до n: n! кратно любому k ≤ n.
- Среди факториалов только 1! и 0! являются полными квадратами (доказано в 1996 году).
- Факториал простого числа p удовлетворяет теореме Вильсона: (p−1)! ≡ −1 (mod p) — это критерий простоты.
- Факториалы часто встречаются в задачах о «путешественнике коммивояжёре» и в теории графов.
¶Источники
- Куртом, А. А. «Курс математического анализа»
- Радченко, В. А. «Комбинаторика»
- Graham, R. L., Knuth, D. E., Patashnik, O. «Concrete Mathematics»
- Weisstein, E. W. «Factorial» // MathWorld
