01. Перестановки: порядок и число вариантов
Как описать порядок, в котором вышли пронумерованные шары из коробки? Если шаров , каждый имеет номер от до , а повторно вынуть один и тот же шар нельзя. Запись результатов по порядку и приводит нас к перестановкам.
Перестановка — это список с фиксированным порядком
Обозначим множество номеров через
Определение 22.1. Перестановка чисел — это упорядоченный список
в котором каждое число из встречается ровно один раз. Число стоит на -м месте. Например, и — перестановки чисел из . А не подходит: число повторено, а числа нет.
Слово упорядоченный важно. Списки и содержат одни и те же числа, но это разные перестановки. Две перестановки и равны только тогда, когда совпадают числа на каждом месте:
Перестановка как список отвечает на вопрос «в каком порядке записаны числа?». Позже появится двухстрочная подстановка, которая отвечает на другой вопрос — «какому числу сопоставлено данное число?».
Сколько существует перестановок
Для первого места можно выбрать любое из чисел. После этого для второго остаётся чисел, для третьего — и так далее. На последнее место остаётся ровно одно число. По правилу умножения число вариантов равно
Знак читают « факториал». Например, перестановок чисел ровно . При есть один список , что согласуется с .
Утверждение 22.1. Количество всех перестановок чисел равно . Доказательство — последовательный выбор элементов по местам, который мы только что разобрали. Каждый возможный список получается ровно одним таким выбором, поэтому ни один вариант не потерян и ни один не посчитан дважды.
Проверь себя
- Сколько перестановок можно составить из чисел ? Почему варианты не повторяются при подсчёте?
- Является ли перестановкой чисел ?
- Равны ли перестановки и ?
Показать решение
1. . Каждый выбор числа для очередного места задаёт один определённый список, поэтому при таком подсчёте повторов нет.
2. Нет: число записано дважды, а число отсутствует.
3. Нет: уже на втором месте стоят разные числа ( и ). Для равенства должны совпадать все места.
