Факториал

Простой, быстрый и стильный способ записывать и работать с длинными цепочками умножений. А еще вы наконец поймете, почему факториал 0 равен 1.

    graph TD
        root[Цепочка умножений]:::featured --> question{{Начинается с  $1$ ?}}

        question -->|Да| f[Факториал]:::featured
        question -->|Нет| df[Убывающий факториал]:::featured

        f -->|Прямая формула| f-formula[" $\displaystyle n!$ "]
        f -->|Рекуррентная формула| f-recurrent[" $\displaystyle n! = (n-1)! \cdot n$ "]

        df --> df-formula[" $\displaystyle n^{\underline{k}} = \frac{n!}{(n-k)!}$ "]

Для удобной записи и работы с длинными цепочками умножений последовательных чисел был придуман факториал:

Факториал числа n — произведение всех натуральных чисел от 1 до n:

1\cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot n = n!

Примеры факториалов

1! = 1 \qquad 3! = 1\cdot 3\cdot 2 \qquad 5! = 5\cdot 4\cdot 3\cdot 2\cdot 1

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

Рекуррентная формула факториала

n! = (n-1)! \cdot n

Доказательство

Запишем факториал $(n-1)!$ в правой части равенства как цепочку умножений. Получим цепочку умножений чисел с 1 уже вплоть до n. А это и является $n!$ по определению:

(n-1)! \cdot n = 1 \cdot 2 \cdot \ldots \cdot (n-1) \cdot n = n!

$\blacksquare$

Рекуррентная формула позволяет гибко манипулировать самим факториалом, убирая или добавляя в него множители. Это позволяет сильно упростить сложные выражения с факториалами:

Рекуррентная формула в деле

Решите примеры:

а) \ \frac{1001!}{999!} \qquad б) \ \frac{1000! + 999!}{1001!}

Пояснение

Провести вычисления «напрямую» тут невозможно. Сликом большие выходят числа. Поэтому остается только использовать рекуррентную формулу факториала.

Пример а)

Два раза подряд применяем рекуррентную формулу факториала для 1001!. Затем сокращаем:

\frac{1001!}{999!} = \frac{\cancel{999!}\cdot 1000 \cdot 1001}{\cancel{999!}} = 1 \ 001 \ 000

Пример б)

Один раз применяем рекуррентную формулу для левого слагаемого в числителе и дважды для знаменателя:

\frac{1000! + 999!}{1001!} = \frac{999!\cdot 1000 + 999!}{999!\cdot 1000\cdot 1001} = \frac{\cancel{999!}\cdot(1000 + 1)}{\cancel{999!}\cdot 1000\cdot 1001} = \\ = \frac{\cancel{1001}}{1000\cdot \cancel{1001}} = \frac{1}{1000} = 0.001

Часто цепочки умножений не включают в себя единицу. Для произвольных цепочек умножений придумали убывающий факториал:

Убывающий факториал числа n размером k — цепочка умножений из k уменьшающихся на единицу натуральных чисел, начиная с n.

n^{\underline{k}} = \underbrace{n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n- (k-1))}_{k \ множителей}

Примеры убывающих факториалов

100^{\underline{4}} = 100\cdot 99 \cdot 98 \cdot 97 \qquad 11^{\underline{5}} = 11 \cdot 9 \cdot 10 \cdot 7 \cdot 8 \qquad 6^{\underline{4}} = 3\cdot 4\cdot 5\cdot 6

Значение убывающего факториала можно удобным образом выразить через обычные факториалы:

Формула убывающего факториала

n^{\underline{k}} = \frac{n!}{(n-k)!}

Доказательство

Итак, у нас есть убывающий факториал $n^{\underline{k}}$ . По определению он расписывается так:

n^{\underline{k}} = n \cdot (n-1) \cdot \ldots \cdot (n-(k-1))

Добавим недостающие множители, чтобы цепочка шла до единицы. Но лишние множители повлияют на финальный результат! Поэтому, чтобы ничего не поменялось, сразу же и поделим на добавленные лишние множители. Тогда они сократятся друг с другом и ничего не испортят:

n^{\underline{k}} = \frac{ n \cdot \ldots \cdot (n-(k-1)) \cdot \yellow{(n-k) \cdot (n-k-1) \cdot \ldots \cdot 2 \cdot 1} }{\yellow{(n-k)\cdot(n-k-1)\cdot \ldots \cdot 2 \cdot 1}}

Таким добавлением «лишних» множителей мы добились того, что сверху у нас по определению получился факториал числа n, записанный в обратном порядке, а снизу факториал $n-k$ :

n^{\underline{k}} = \frac{n!}{(n-k)!}

$\blacksquare$

Сам по себе 0! не имеет смысла, но он может возникнуть в формулах. По этому все согласились считать 0! = 1, чтобы не ломать красивые формулы.