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

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

Перестановка — расположение всех данных элементов в определённом порядке, при котором каждый элемент используется ровно один раз. Например, ABC и BAC — разные перестановки букв A, B и C. Это определение помогает понять, какие задачи можно решать с помощью факториала.

Число перестановок — количество различных порядков, в которых можно расположить заданные элементы. Для n различных элементов его обозначают Pₙ. Такая величина нужна, когда требуется не перечислить варианты, а быстро узнать их общее число.

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

Факториал нуля — специальное значение 0! = 1. Оно нужно, чтобы общие правила вычислений сохранялись и для выражений, где после выбора элементов не остаётся ни одного. Поэтому запись с нулевым факториалом не является ошибкой.

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

Перестановки рассматривают для различных элементов, потому что одинаковые объекты не создают нового различимого порядка. Если две одинаковые книги поменять местами, внешне расстановка не изменится. Поэтому формула Pₙ = n! считает именно варианты для элементов, которые можно отличить друг от друга.

Представим n пустых мест и начнём заполнять их слева направо. На первое место можно поставить любой из n элементов, а после этого остаётся n − 1 элемент для второго места. Затем выбор продолжается: для третьего места остаётся n − 2 варианта, пока для последнего места не останется ровно один.

Выборы выполняются последовательно: сначала определяется первый элемент, затем второй и так далее. Каждому варианту первого выбора соответствует n − 1 вариантов второго, каждому получившемуся варианту — ещё n − 2 варианта третьего. По правилу умножения общее число порядков равно произведению n · (n − 1) · … · 2 · 1.

Это произведение записывают короче: Pₙ = n!. Например, P₃ = 3! = 3 · 2 · 1 = 6, а P₅ = 5! = 5 · 4 · 3 · 2 · 1 = 120. Чтобы найти конкретное значение, достаточно раскрыть факториал и выполнить умножение.

При добавлении нового элемента к набору из n − 1 элементов он может занять любое из n мест. Для каждого прежнего порядка возникают n новых порядков, поэтому Pₙ = n · Pₙ₋₁. Так, P₄ = 4 · P₃ = 4 · 6 = 24, что совпадает с 4!.

Число перестановок различных элементов

В таблице число элементов сопоставлено с количеством всех возможных порядков. Для конкретного значения n нужно найти строку или вычислить факториал самостоятельно. Последняя строка показывает общее правило, применимое к любому натуральному n.

Например, если объектов четыре, ответ берут из строки n = 4: P₄ = 24. Таблица также помогает проверить вычисление, выполненное по формуле.

Разбор задач

Задача 1. Расстановка книг

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

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

Ответ: 24 способа.

Задача 2. Пятизначные числа

Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4 и 5, используя каждую цифру один раз? Первая цифра не может быть нулём, но нуля среди данных цифр нет. Значит, каждое число получается перестановкой всех пяти цифр.

1. На первое место можно поставить любую из 5 цифр.
2. На следующие места последовательно остаётся 4, 3, 2 и 1 вариант.
3. Получаем P₅ = 5 · 4 · 3 · 2 · 1 = 5! = 120.

Ответ: 120 чисел.

Задача 3. Два ученика рядом

Сколькими способами можно рассадить 6 учеников в ряд, если два заданных ученика должны сидеть рядом? Объединим этих учеников в один блок, потому что внутри ряда они занимают соседние места. Тогда вместе с блоком получаем 5 объектов: блок и ещё 4 ученика.

1. Пять объектов можно переставить P₅ = 5! способами.
2. Внутри блока два заданных ученика могут сидеть в двух порядках: первый-второй или второй-первый.
3. По правилу умножения число рассадок равно 5! · 2 = 120 · 2 = 240.

Ответ: 240 способов.

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

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

Складывать варианты вместо умножения. Последовательные выборы мест не складываются, потому что каждый выбор первого места сочетается с несколькими выборами второго. Для проверки спросите себя, образует ли каждый первый вариант пары со всеми допустимыми следующими вариантами.

Путать n! с n · n. Факториал содержит все множители от 1 до n, а не два одинаковых множителя. Распишите n! хотя бы один раз: например, 4! = 4 · 3 · 2 · 1, а не 4 · 4.

Считать одинаковые элементы различными. Обмен двух одинаковых предметов не создаёт нового видимого порядка, поэтому прямое применение n! завысит ответ. Перед вычислением убедитесь, что все элементы действительно различимы и в условии разрешено считать их разными.

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

До изучения перестановок нужны правило произведения, натуральные числа и умение записывать длинные произведения с помощью многоточия. Правило произведения объясняет, почему число вариантов на разных шагах перемножается. Запись произведений помогает перейти от n · (n − 1) · … · 1 к факториалу.

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

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

• Перестановка использует все данные элементы ровно один раз.
• Порядок элементов в перестановке важен.
• Число перестановок n различных элементов обозначают Pₙ.
• Основная формула: Pₙ = n!.
• n! = 1 · 2 · 3 · … · n.
• 0! = 1.
• При добавлении нового элемента выполняется равенство Pₙ = n · Pₙ₋₁.