§ 3. Перестановки

Определения и обозначения

Перестановка — упорядоченное расположение всех элементов данного конечного множества. Каждый элемент используется ровно один раз: если есть буквы A, B и C, нельзя пропустить одну из них или повторить другую. Это определение помогает понять, какие варианты следует считать: переставляем весь набор и учитываем порядок элементов.

Факториал натурального числа n — произведение всех натуральных чисел от 1 до n; его записывают n!. Например, 4! = 1·2·3·4. Такая запись сокращает длинное произведение и позволяет компактно выражать число способов упорядочить несколько элементов.

Число перестановок n различных элементов — количество способов расположить все эти элементы в порядке; его обозначают Pₙ. Например, P₃ означает число возможных порядков для трёх разных объектов. Это обозначение связывает понятие перестановки с конкретной задачей подсчёта вариантов.

Как это устроено

Чтобы составить перестановку, будем заполнять места по очереди. На первое место можно поставить любой из n элементов, поэтому есть n вариантов; после выбора один элемент уже занят, и на второе место остаётся n − 1 вариант. Затем остаётся n − 2 элемента, а для последнего места — один. Важно, что выборы идут последовательно и для каждого уже выбранного элемента возможности следующего шага сокращаются.

По правилу произведения число всех последовательных вариантов равно произведению числа возможностей на каждом шаге: n·(n − 1)·…·2·1. Именно это произведение называют факториалом n и записывают n!. Поэтому число перестановок n различных элементов равно Pₙ = n!. Формула работает, потому что каждый полный набор выборов задаёт один порядок всех элементов, и ни один возможный порядок не пропускается.

Факториалы соседних чисел удобно связывать друг с другом. По определению (n + 1)! = (n + 1)·n·(n − 1)·…·1, а часть n·(n − 1)·…·1 равна n!. Значит, (n + 1)! = (n + 1)·n!: при переходе к следующему факториалу достаточно умножить предыдущий на новое число. Это упрощает вычисления, например 6! = 6·5!.

Для нуля принимают соглашение 0! = 1. Оно согласуется с равенством n! = n·(n − 1)!, если подставить n = 1: тогда 1! = 1·0!, а поскольку 1! = 1, получаем 0! = 1. Кроме того, такое соглашение позволяет единообразно записывать многие формулы комбинаторики.

Перестановка отличается от выбора нескольких элементов тем, что в ней используются все элементы набора. Например, если из пяти учеников нужно выбрать троих, считать 5! нельзя: это число упорядочивает всех пятерых. Если же всех пятерых рассаживают в ряд, применима формула перестановок. В обоих случаях порядок может иметь значение, но сначала нужно проверить, все ли элементы участвуют.

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

Сначала определите, какой объект описан в задаче: факториал или количество перестановок. Если нужно расположить все n различных элементов, можно сразу использовать Pₙ = n!, а затем вычислить факториал. Для проверки полезно развернуть запись n! в произведение чисел от n до 1.

Разбор задач

Задача 1. Сколькими способами можно расставить на полке 4 различные книги? Здесь требуется занять все места четырьмя книгами, а порядок на полке меняется. Значит, нужно посчитать перестановки четырёх элементов.

1. Для первой позиции выбираем любую из четырёх книг, поэтому есть 4 варианта. После этого выбранная книга уже не может занять другое место. На второй позиции остаётся 3 варианта.
2. Для третьей позиции остаются 2 книги, а для последней — 1. Перемножаем числа вариантов: 4·3·2·1 = 4! = 24. Ответ: 24 способа.

Задача 2. Сколькими способами могут занять места в ряд 6 учеников? Каждый ученик занимает одно место, и все шестеро должны оказаться в ряду. Поэтому рассаживание задаёт перестановку шести различных элементов.

1. На первое место можно посадить любого из 6 учеников, на второе — одного из оставшихся 5. Дальше число вариантов последовательно равно 4, 3, 2 и 1. Такой подсчёт охватывает все возможные рассадки.
2. По правилу произведения получаем 6·5·4·3·2·1 = 6! = 720. Ответ: 720 способов.

Задача 3. Сколькими способами можно расположить в ряд 8 участников, если два заданных участника должны стоять рядом? Эти двое могут поменяться местами, но не могут разойтись по разным частям ряда. Поэтому удобно временно считать их одним общим блоком.

1. Объединяем двух заданных участников в блок. Вместе с шестью остальными участниками получаем 7 объектов, которые можно расположить 7! способами. Этот подсчёт учитывает места блока, но пока не учитывает порядок двух людей внутри него.
2. Внутри блока участники могут стоять в двух порядках: сначала первый, затем второй или наоборот. Умножаем число расположений объектов на 2: 7!·2 = 5040·2 = 10 080. Ответ: 10 080 способов.

Типичные ошибки

• Учитывать только варианты для первого места. Так поступают, когда замечают n возможностей на старте и останавливаются на этом шаге. Но после выбора первого элемента оставшиеся тоже можно расположить разными способами. Проверьте, что перемножены варианты для всех мест, а не только для первого.
• Использовать n! при выборе лишь нескольких элементов. Факториал считает расположения всех n элементов, поэтому его легко применить по привычке, увидев число n в условии. Уточните, требуется ли расставить весь набор или выбрать только часть. Если часть элементов не используется, задача не является простой перестановкой всего набора.
• Не учитывать значение порядка. Иногда одинаковый набор букв принимают за один вариант независимо от расположения. Однако ABC и BAC задают разные порядки. Проверьте, меняется ли результат задачи при перестановке элементов: если да, эти варианты нужно считать отдельно.
• Считать 0! нулём или оставлять его неопределённым. Это может показаться естественным из-за числа 0, но факториал нуля задают по соглашению. Используйте 0! = 1: такое значение согласуется с формулой для соседних факториалов и необходимо в комбинаторных формулах. Перепроверьте, не подставили ли вы ноль вместо единицы.

Связь с другими темами

Подсчёт перестановок опирается на правило произведения: если выбор выполняется по шагам, общее число вариантов равно произведению числа возможностей на каждом шаге. Именно поэтому для перестановки последовательно перемножают n, n − 1 и далее до 1. Перестановки помогают решать задачи о расположении людей и предметов в порядке. Они также служат основой для изучения размещений, сочетаний и биномиальных коэффициентов, где меняются условия выбора и учёта порядка.

Что запомнить

• Перестановка использует все данные элементы ровно по одному разу.
• Порядок элементов в перестановке важен.
• n! = n·(n − 1)·…·2·1.
• 0! = 1.
• Число перестановок n различных элементов равно Pₙ = n!.
• При подсчёте перестановок можно последовательно выбирать элементы на каждое место.