Перестановки
Подсчёт упорядоченных расположений — где каждая позиция имеет значение
1. Что такое перестановка?
Перестановка — это упорядоченное расположение объектов. Ключевая идея в том, что порядок имеет значение.
Главная идея: Если вы расположите те же объекты в другой последовательности, вы получите другую перестановку.
Рассмотрим множество $\{A, B, C\}$. Сколькими способами можно расставить все три буквы в ряд?
| № | Расположение |
|---|---|
| 1 | A B C |
| 2 | A C B |
| 3 | B A C |
| 4 | B C A |
| 5 | C A B |
| 6 | C B A |
Существует 6 перестановок. Обратите внимание, что ABC и BAC содержат одни и те же буквы, но считаются отдельно, потому что порядок различается.
Интересный факт: «Кодовый замок» правильнее было бы называть замком с перестановками — порядок ввода цифр абсолютно важен! Ввести 3-7-1 — это не то же самое, что 1-3-7.
2. Функция факториала
Факториал неотрицательного целого числа $n$, записываемый как $n!$, — это произведение всех натуральных чисел от $1$ до $n$:
$$ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 $$
Он показывает количество способов расставить $n$ различных объектов в ряд.
Часто встречающиеся значения факториала
| $n$ | $n!$ | Вычисление |
|---|---|---|
| 0 | 1 | (по определению) |
| 1 | 1 | $1$ |
| 2 | 2 | $2 \times 1$ |
| 3 | 6 | $3 \times 2 \times 1$ |
| 4 | 24 | $4 \times 3 \times 2 \times 1$ |
| 5 | 120 | $5 \times 4 \times 3 \times 2 \times 1$ |
| 6 | 720 | $6!$ |
| 10 | 3,628,800 | $10!$ |
| 20 | 2,432,902,008,176,640,000 | $20!$ — больше 2 квадриллионов! |
Почему $0! = 1$? Это не случайность — существует ровно один способ расположить ноль объектов: ничего не делать. Это также обеспечивает согласованность формул, например $P(n,0) = \frac{n!}{n!} = 1$.
⚠️ Факториалы растут невероятно быстро! $20!$ уже превышает 2 квадриллиона. Этот взрывной рост объясняет, почему даже простые задачи на подсчёт могут давать огромные числа.