🔀 Дискретка

Факториал

англ. Factorial

Произведение всех натуральных чисел от 1 до n: 5! = 1·2·3·4·5 = 120; число способов упорядочить n предметов.

Факториал $n!$ — произведение всех натуральных чисел от единицы до $n$ : $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$ . Комбинаторный смысл прямотой: $n!$ — число способов расставить $n$ различных предметов по порядку. Три блюда на обед можно выстроить $3! = 6$ способами: суп-второе-компот, суп-компот-второе и так далее. Первый предмет выбираем из трёх, второй из двух, третий — один остался: $3 \cdot 2 \cdot 1 = 6$ .

n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n, 0! = 1

Равенство $0! = 1$ студенты любят оспаривать, а оно честное: пустое множество упорядочить можно ровно одним способом — «ничего не делать». Есть и алгебраическое обоснование: из $(n + 1)! = (n + 1) \cdot n!$ при $n = 0$ выходит $1! = 1 \cdot 0!$ , значит $0! = 1$ . Факториал растёт стремительно: $10! = 3628800$ , а $20! \approx 2.4 \cdot 1 0^{18}$ — больше, чем секунд в 76 миллиардах лет. Точную скорость описывает формула Стирлинга: $n! \approx 2 π n (\frac{n}{e})^{n}$ .

Факториалы — рабочие лошадки комбинаторики: перестановки $P_{n} = n!$ , размещения $A_{n}^{k} = \frac{n !}{( n - k )!}$ , сочетания $C_{n}^{k} = \frac{n !}{k ! ( n - k )!}$ , биномиальные коэффициенты бинома Ньютона. Разобрать все три формулы на задачах можно в уроке о перестановках, размещениях и сочетаниях и в тренажёре комбинаторики.

Практикум. Сколькими способами расставить пять книг на полке? $5! = 120$ . А если две конкретные должны стоять рядом? Склейте их в один блок: перестановок четырёх объектов $4! = 24$ , внутри блока два порядка — итого $48$ . А если из шести человек выбрать председателя и секретаря? Порядок важен — это размещения: $A_{6}^{2} = \frac{6 !}{4 !} = 30$ . Заметьте, как факториалы сокращаются в дробях: почти вся арифметика комбинаторики живёт на этом сокращении.

Сокращение — главный приём: $\frac{10 !}{8 !} = 10 \cdot 9 = 90$ , и никаких миллионных чисел. Проверьте себя: $\frac{C _{7}^{3} \cdot 3 !}{A _{7}^{2}}$ ? Считайте через формулы и сокращайте, а не вычисляйте факториалы напрямую. Отдельный полюс роста — факториалы в знаменателе: ряд для $e$ содержит $\frac{1}{k !}$ , и именно их стремительный рост заставляет слагаемые обнуляться так быстро, что сумма сходится молниеносно. Обратная сторона — факториальный взрыв в переборных алгоритмах: $13!$ уже превышает миллиард.

Частые вопросы

Почему 0! = 1, а не 0?

Потому что факториал — это число упорядочиваний, а пустое множество упорядочивается одним способом. Плюс рекуррентная проверка: $3! = 3 \cdot 2!$ , $2! = 2 \cdot 1!$ , $1! = 1 \cdot 0!$ — цепочка сходится к $0! = 1$ .

Насколько быстро растёт факториал?

Быстрее любой степенной функции: $10! \approx 3.6$ млн, $15!$ уже триллион с лишним. По Стирлингу $n! \approx 2 π n (n / e)^{n}$ — именно поэтому перебор всех перестановок в задачах оптимизации умирает уже при $n \approx 15$ .

пошагово

Ряд на сходимость

Проверить ряд с факториалом на сходимость

Факториалы в члене ряда — сигнал для признака Даламбера; решатель упростит отношение соседних членов.

Открыть решатель