Перестановки: сколько способов расставить объекты
💻 Информатика · 5 класс
Что такое перестановки
Перестановка — это один из способов расставить несколько разных объектов в ряд по порядку. Когда мы спрашиваем «сколькими способами можно расставить предметы», мы считаем число перестановок. Такие задачи учат перебирать варианты по порядку и не пропускать ни одного.
Например, три книги можно поставить на полку по-разному: какая будет первой, какая второй, какая третьей. Каждый новый порядок — это отдельная перестановка. Подобные задачи решает раздел математики о подсчёте вариантов; в информатике это помогает понять, как перебирать возможности и не сбиться.
Перебор вариантов по порядку
Чтобы не запутаться, варианты перебирают по дереву: сначала выбираем первый объект, потом — второй из оставшихся, потом — последний. Так мы точно учтём все способы и ни один не повторим.
Возьмём три буквы: А, Б, В. Запишем все способы поставить их в ряд:
АБВ АВБ
БАВ БВА
ВАБ ВБАПолучилось 6 разных рядов. Это и есть все перестановки трёх букв. Заметьте, как удобно идти по порядку: сначала все ряды, где первая буква А, потом где первая Б, потом где первая В.
Как растёт число способов
Чем больше объектов, тем больше способов их расставить. Число способов быстро увеличивается.
| Сколько объектов | Сколько способов | Как считаем |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 · 2 |
| 3 | 6 | 1 · 2 · 3 |
| 4 | 24 | 1 · 2 · 3 · 4 |
| 5 | 120 | 1 · 2 · 3 · 4 · 5 |
Видно, что от четырёх объектов получается уже 24 способа, а от пяти — целых 120. Перебрать их вручную трудно, и тут на помощь приходит правило подсчёта.
Правило. Чтобы найти число перестановок, перемножают все числа от 1 до количества объектов. Для трёх объектов это 1 · 2 · 3 = 6.Почему перемножают
На первое место можно поставить любой из 3 объектов. На второе — любой из 2 оставшихся. На третье — последний, оставшийся 1. Перемножаем выборы: 3 · 2 · 1 = 6. Получается то же самое число способов, что мы насчитали перебором по дереву.
Где это пригодится
- Сосчитать, сколькими способами встать в очередь.
- Узнать, сколько вариантов кода из разных цифр.
- Перебрать все маршруты обхода нескольких точек.
Частые ошибки. Ученики при переборе повторяют один и тот же ряд дважды или пропускают вариант. Поэтому перебирают строго по порядку. Ещё забывают: если объекты одинаковые, разных рядов будет меньше.
Кратко о главном
- Перестановка — это способ расставить разные объекты в ряд.
- Все варианты перебирают по порядку, чтобы ничего не пропустить.
- Число способов равно произведению чисел от 1 до количества объектов.
- На первое место — любой объект, на второе — из оставшихся, и так далее.
- Для трёх объектов получается
1 · 2 · 3 = 6способов.