Арифметика
Факториал
Восклицательный знак, изменивший математику
До 1808 года математики писали факториал громоздко: «1·2·3·...·n» или «[n]» или «|n». **Кристиан Крамп**, эльзасский математик, решил: хватит. Он ввёл обозначение **n!** - и восклицательный знак идеально передал суть: факториал - это математический КРИК, число, которое взрывается за пределы воображения.
Я использую обозначение n! для произведения 1·2·3...n, потому что оно удобно. - Кристиан Крамп, 1808
Факториал 52! (способы перетасовать колоду карт) больше числа атомов в наблюдаемой Вселенной. Каждое тасование колоды почти наверняка уникально за всю историю человечества. Вы никогда не держали в руках ту же последовательность карт, что кто-то другой. **Никогда**.
Сколько способов разложить колоду из 52 карт? 52! ≈ 8×10⁶⁷. Это больше, чем атомов в наблюдаемой Вселенной! Каждое тасование почти наверняка уникально за всю историю человечества. Факториал - простая операция с потрясающими результатами.
- **Криптография:** пространство ключей, перестановочные шифры
- **Комбинаторика:** подсчёт вариантов, вероятности
- **Алгоритмы:** сложность перебора
Понятие факториала
**Факториал** числа n (обозначается n!) - произведение всех натуральных чисел от 1 до n. Это базовая операция в комбинаторике.
**Определение:** n! = 1 × 2 × 3 × ... × n **По соглашению:** 0! = 1 (пустое произведение) **Рекурсия:** n! = n × (n-1)!
Восклицательный знак для факториала ввёл Кристиан Крамп в 1808 году. До этого писали громоздко.
Чему равно 5!?
Рост факториала
Факториал растёт **невероятно быстро** - быстрее любой экспоненты. Уже 20! превосходит число атомов на Земле.
**Иерархия роста:** log n < n < n² < 2ⁿ < n! < nⁿ Факториал - «суперэкспоненциальный». Алгоритмы с O(n!) - практически невычислимы для n > 15-20.
Быстрый рост делает перебор всех перестановок невозможным даже для небольших n. Это основа сложности многих алгоритмических задач.
Что больше: 10! или 2¹⁰?
Комбинаторный смысл
Факториал возникает естественно при подсчёте **перестановок** - способов упорядочить n объектов.
**Где ещё факториал:** • Ряд Тейлора: eˣ = Σ xⁿ/n! • Вероятности: n! в формулах распределений • Число Эйлера: e = Σ 1/n! • Гамма-функция: Γ(n+1) = n! (обобщение на вещественные)
Факториал - связующее звено между дискретной и непрерывной математикой.
Сколько способов рассадить 4 человека за круглым столом (с учётом поворотов)?
Формула Стирлинга
**Формула Стирлинга** приближает факториал для больших n. Позволяет оценивать n! без вычисления произведения.
**Улучшенная формула:** n! = √(2πn) × (n/e)ⁿ × e^(θ/(12n)) где 0 < θ < 1. С этой поправкой ошибка < 1/(12n) для любого n.
Формула Стирлинга незаменима в статистике, термодинамике, теории информации - везде, где встречаются большие факториалы.
Факториал растёт как экспонента 2ⁿ или nⁿ
Факториал растёт быстрее экспоненты, но медленнее nⁿ
2ⁿ умножает на постоянный множитель 2. n! умножает на растущий множитель n. Поэтому n! ≫ 2ⁿ. Но nⁿ = n×n×...×n (n раз), каждый множитель = n, а в n! множители от 1 до n. Иерархия: 2ⁿ < n! < nⁿ.
Формула Стирлинга даёт n! ≈ √(2πn) × (n/e)ⁿ. Что из этого верно?
Ключевые идеи
- n! = 1 × 2 × ... × n, 0! = 1
- Растёт быстрее экспоненты: n! ≫ 2ⁿ
- Комбинаторика: перестановки, сочетания
- Стирлинг: n! ≈ √(2πn)(n/e)ⁿ
Связанные темы
Факториал связан с комбинаторикой и анализом:
- Умножение — Основа факториала
- Степени — Сравнение роста
- Прогрессии — Произведение членов
Вопросы для размышления
- Почему 0! = 1 - естественное определение?
- Как быстро оценить порядок 1000! без калькулятора?
- Можно ли определить факториал для дробных чисел?