11. Перестановки и факториал
Перестановка — это расстановка всех различных элементов в один ряд. Первым можно поставить любой из , вторым — любой из оставшихся , и так до последнего: всего способов.
Что пригодится из прошлого: размещения без повторений — перестановка есть их частный случай; правило произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Три книги на полке
Три разные книги нужно поставить на полку в ряд. Выпишем все порядки, выбирая по очереди: сначала книгу на первое место, затем на второе, затем на третье.
старт
├── a
│ ├── b ── c → abc
│ └── c ── b → acb
├── b
│ ├── a ── c → bac
│ └── c ── a → bca
└── c
├── a ── b → cab
└── b ── a → cba
На первое место можно поставить любую из трёх книг. На второе — любую из двух оставшихся. На третье — единственную оставшуюся. Всего порядков.
Определение и формула
Перестановкой элементов называют размещение без повторений из элементов по : использованы все элементы, каждый ровно один раз, а порядок важен. Число перестановок равно
Запись читается «эн факториал». Это просто сокращённое обозначение для произведения всех натуральных чисел от до .
Почему
Принято считать, что . Это не произвольное соглашение; вот четыре согласованных объяснения.
- Расставить ноль предметов можно ровно одним способом: ничего не делать, получится пустой ряд. А считает способы расстановки предметов.
- Закон «следующее равно число, умноженное на предыдущее». Для верно ; например, . Подставим : , откуда .
- Формула для сочетаний. Позже мы докажем, что способов выбрать элементов из равно . Способ выбрать ноль элементов один (взять пустой набор). Подставим : ; это равно только при .
- Единица как пустое произведение. Если перемножить ноль чисел, получится нейтральный элемент умножения — единица. Так же .
Как быстро растёт факториал
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5 040 | 40 320 | 362 880 | 3 628 800 | 39 916 800 | 479 001 600 |
Факториал растёт очень быстро. Несколько цифр:
- — это ровно 42 суток в секундах, то есть шесть недель;
- — это уже ;
- колоду из карт можно перетасовать способами — это число из 68 цифр.
Связь размещений и факториалов
Так как , то после первых множителей остаётся :
Например, . Дробь сокращается: общий хвост исчезает.
Приём вычисления. Не считайте большие факториалы целиком, а сокращайте: .
Примеры
1. Рассадка. Пять человек садятся в ряд из пяти стульев: способов.
2. Числа из цифр. Из цифр , использованных по одному разу, получается четырёхзначных чисел: .
3. Двое рядом. Шесть человек садятся в ряд, но и обязаны сидеть рядом. Склеим их в один «блок» : теперь в ряду пять объектов, их можно расставить способами. Внутри блока и можно поменять местами — ещё два способа. Итого . Каждой расстановке, где и стоят рядом, отвечает ровно одна пара «расстановка пяти объектов и порядок внутри блока» — и наоборот; поэтому ничего не потеряно и не посчитано дважды.
Частые ошибки
- . Неверно: .
- . Неверно: . Например, , а .
- . Неверно. Для : , а .
- Считать, что перестановка — это «что-то одно». Это любой порядок всех элементов; их , и они все разные.
Проверь себя
1. Сколькими способами можно выстроить в очередь шесть человек?
Решение
.
2. Вычислите и без калькулятора.
Решение
. : всё остальное сокращается.
3. Сколькими способами можно расположить в ряд пять различных мячей — трёх красных и двух синих? (Цвет не влияет на подсчёт: все мячи разные.)
Решение
Всего пять различных мячей: . Цвета в условии не мешают: мячи различны.
4. Покажите, что при .
Решение
, поэтому при делении на остаётся .
Итог
- Перестановка — расстановка всех различных элементов в ряд: .
- : пустой ряд можно составить единственным способом.
- — размещения выражаются через факториалы.
- Факториалы растут очень быстро; большие считайте сокращением дробей.
