Факториал: определение и свойства

Факториал — это математическая функция, определённая для неотрицательных целых чисел, равная произведению всех натуральных чисел от 1 до данного числа включительно. Обозначается символом «!» (восклицательный знак), который ставится после числа. Например, факториал числа 5 (записывается как 5!) равен 1 × 2 × 3 × 4 × 5 = 120. Факториал является одной из фундаментальных комбинаторных функций, широко используемой в теории вероятностей, комбинаторике, математическом анализе, теории чисел и информатике. Для числа 0 факториал определён как 0! = 1, что согласуется с комбинаторными и аналитическими свойствами функции.

История

Понятие факториала возникло в связи с задачами комбинаторики, в частности, подсчётом числа перестановок. В древности и средневековье отдельные случаи произведения последовательных чисел встречались в трудах индийских и арабских математиков, но систематического изучения не было. В европейской математике первое известное использование произведения последовательных чисел для подсчёта перестановок приписывается итальянскому математику Фабиано (XIV век) в его работе по коммерческой арифметике, однако обозначение отсутствовало.

В 1677 году английский математик Джон Валлис в трактате «Арифметика бесконечных» (Arithmetica Infinitorum) ввёл обозначение для произведения последовательных чисел, используя символ «∏» (произведение). В 1808 году французский математик Кристиан Крамп в своей работе «Элементы арифметики» (Éléments d’arithmétique universelle) впервые предложил использовать символ «!» для обозначения факториала. Крамп, занимавшийся также комбинаторикой и теорией вероятностей, выбрал этот знак, вероятно, из-за его простоты и наглядности. Обозначение быстро распространилось в математических кругах, и к середине XIX века стало стандартным.

В 1729 году швейцарский математик Леонард Эйлер обобщил факториал на действительные и комплексные числа, введя гамма-функцию Γ(z). Для натуральных чисел n выполняется соотношение: Γ(n+1) = n!. Это обобщение позволило использовать факториал в анализе и теории специальных функций.

Определение

Для натуральных чисел

Для целого неотрицательного числа n факториал определяется рекуррентно:

• 0! = 1 (базовый случай);
• n! = n × (n-1)! для n ≥ 1.

В явном виде для n > 0: n! = 1 × 2 × 3 × … × n = ∏_{k=1}^{n} k.

Для нуля

Определение 0! = 1 мотивировано несколькими соображениями:

• Комбинаторно: число перестановок пустого множества равно 1 (единственный способ — ничего не переставлять).
• Аналитически: гамма-функция Γ(1) = 1, и по свойству Γ(n+1) = n! для n=0 получаем 0! = 1.
• Формально: пустое произведение (произведение без множителей) принимается равным 1.

Обобщение на действительные и комплексные числа

Гамма-функция Эйлера определяется для всех комплексных чисел, кроме неположительных целых: Γ(z) = ∫_{0}^{∞} t^{z-1} e^{-t} dt, Re(z) > 0. Для z = n+1 (n — натуральное) выполняется Γ(n+1) = n!. Гамма-функция является аналитическим продолжением факториала на комплексную плоскость.

Свойства

Основные свойства

1. Рекуррентное соотношение: n! = n × (n-1)!.
2. Симметрия: (n+1)! = (n+1) × n!.
3. Монотонность: функция n! строго возрастает при n ≥ 0.
4. Асимптотика: для больших n справедлива формула Стирлинга:

n! ≈ √(2πn) × (n/e)^n. Эта формула даёт хорошее приближение и широко используется в анализе сложности алгоритмов и статистической физике.

Комбинаторные свойства

• Число перестановок n различных элементов равно n!.
• Число размещений (упорядоченных выборок) k элементов из n равно n! / (n-k)!.
• Число сочетаний (неупорядоченных выборок) k элементов из n равно n! / (k! × (n-k)!), что обозначается как C(n,k) или (n choose k).
• Факториал участвует в формуле бинома Ньютона: (a+b)^n = ∑_{k=0}^{n} C(n,k) a^{n-k} b^k.

Аналитические свойства

• Гамма-функция Γ(z) имеет полюса в точках z = 0, -1, -2, ….
• Для отрицательных целых чисел факториал не определён, но гамма-функция позволяет рассматривать дробные и комплексные значения.
• Производная гамма-функции связана с дигамма-функцией ψ(z) = Γ'(z)/Γ(z).

Делимость и теория чисел

• Теорема Вильсона: p — простое число тогда и только тогда, когда (p-1)! ≡ -1 (mod p).
• Степень простого числа в факториале: показатель степени простого числа p в разложении n! на простые множители равен сумме:

v_p(n!) = ∑_{k=1}^{∞} ⌊n/p^k⌋. Эта формула (формула Лежандра) позволяет вычислять, сколько раз p входит в n!.

• Факториал n! делится на все целые числа от 1 до n, поэтому n! является общим кратным чисел 1, 2, …, n.

Применение

Комбинаторика и теория вероятностей

Факториал является основой для подсчёта числа комбинаторных объектов: перестановок, размещений, сочетаний, разбиений. В теории вероятностей факториал используется в формуле биномиального распределения, распределения Пуассона, гипергеометрического распределения.

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

• Разложение в ряды: экспонента e^x = ∑_{n=0}^{∞} x^n / n!.
• Тригонометрические функции: sin x = ∑_{n=0}^{∞} (-1)^n x^{2n+1} / (2n+1)!, cos x = ∑_{n=0}^{∞} (-1)^n x^{2n} / (2n)!.
• Гамма-функция и её обобщения используются в интегральном исчислении, теории вероятностей (распределение хи-квадрат, t-распределение Стьюдента).

Информатика

• Анализ сложности алгоритмов: число операций в алгоритмах перебора (например, задача коммивояжёра полным перебором) пропорционально n!.
• Факториал используется в комбинаторных алгоритмах (генерация перестановок, сочетаний).
• Вычисление факториала — классическая задача для демонстрации рекурсии и итерации.

Физика и статистика

• В статистической физике факториал появляется в формуле Больцмана для энтропии: S = k ln W, где W — число микросостояний, часто выражаемое через факториалы.
• В квантовой механике — при подсчёте числа состояний систем частиц (бозонов и фермионов).

Вычисление

Рекурсивный и итеративный методы

Простейший способ вычисления n! — последовательное умножение от 1 до n (итеративный) или рекуррентное применение определения (рекурсивный). Для n до 20 результат помещается в 64-битное целое число (20! ≈ 2.43×10^18). Для больших n используются алгоритмы с плавающей точкой (например, формула Стирлинга) или библиотеки длинной арифметики.

Приближённые методы

Для больших n (n > 100) точное вычисление n! становится ресурсоёмким, поэтому применяют логарифмическую формулу Стирлинга: ln(n!) ≈ n ln n - n + 0.5 ln(2πn). Эта формула даёт относительную погрешность менее 1% уже при n=10.

Таблица значений

Интересные факты

• Факториал 0! = 1 является единственным случаем, когда произведение пустого множества равно 1.
• Символ «!» для факториала был предложен Кристианом Крампом в 1808 году. До этого использовались различные обозначения, например, символ «∏» или просто запись «1·2·3·…·n».
• Число 10! = 3 628 800 равно количеству секунд в 42 днях (с точностью до 0,1%).
• Факториал 70! превышает число атомов в наблюдаемой Вселенной (≈ 10^80).
• В программировании факториал часто используется как тестовая задача для рекурсии, хотя итеративный подход эффективнее.

Критика и ограничения

• Факториал быстро растёт: уже при n=20 значение превышает 2×10^18, что вызывает проблемы с переполнением в стандартных целочисленных типах данных.
• Для нецелых и отрицательных чисел факториал не определён, что ограничивает его применение в анализе без использования гамма-функции.
• В некоторых контекстах (например, в комбинаторике) использование факториала может быть заменено на мультиномиальные коэффициенты или другие комбинаторные функции, что упрощает вычисления.

Источники

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
• Эйлер Л. Введение в анализ бесконечных. — М.: Физматлит, 1961.
• Крамп К. Éléments d’arithmétique universelle. — Париж, 1808.
• Абрамовиц М., Стиган И. Справочник по специальным функциям. — М.: Наука, 1979.