Теория: Перестановки без повторений
Задачи комбинаторики, связанные с подсчетом числа возможных вариантов расположения элементов некоторого набора в определенном порядке, приводят к понятию упорядоченного множества.
- Перестановкой из $n$ элементов называется любое упорядоченное множество, в которое входят по одному разу все $n$ различных элементов данного множества.
При нахождении числа перестановок принципиально важно, чтобы все элементы исходного множества были различными. Наличие неразличимых элементов исключает применение классической формулы. Если среди элементов оказываются тождественные объекты, то их взаимная перемена мест не приводит к появлению нового упорядоченного множества (например, при смене позиций двух тождественных предметов общий вид ряда и структура расположения элементов остаются неизменными). По этой причине классическая формула применяется только к множествам, состоящим из уникальных элементов.
Вывод формулы на основе правила умножения
Формулу для подсчета числа перестановок можно вывести с помощью математического правила умножения, если представить процесс последовательного заполнения $n$ свободных мест элементами множества:
- На первое место можно выбрать любой из $n$ имеющихся элементов.
- На второе место можно поместить один из оставшихся $(n - 1)$ элементов.
- На третье место выбирается один из $(n - 2)$ элементов, и так далее.
- Для последнего, $n$-го места остается строго один элемент.
По правилу умножения общее число способов выбора для всех позиций равно произведению количества вариантов для каждого места. Это число обозначают символом $P_n$ (от латинского permutatio — перестановка) и записывают в порядке возрастания множителей:
$$P_n = 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n - 2) \cdot (n - 1) \cdot n$$
Произведение первых $n$ натуральных чисел называют факториалом числа $n$. Для его обозначения используется математический символ $n!$. Таким образом, формула для нахождения числа перестановок имеет вид:
$$P_n = n!$$
Примеры решения задач
Рассмотрим несколько распространенных типов задач на перестановки, которые наглядно иллюстрируют применение этой формулы.
Задача 1 (Составление чисел из заданных цифр). Сколько различных четырехзначных чисел можно составить из цифр 2, 4, 6 и 8 при условии, что цифры в записи одного числа не должны повторяться?
Поскольку в условии дан набор из 4 уникальных элементов, которые нужно распределить по 4 позициям без дублирования, мы имеем дело с перестановкой из 4 элементов. Подставим $n = 4$ в формулу факториала:
$$P_4 = 4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$$
Из данного набора цифр можно составить ровно 24 уникальных четырехзначных числа.
Задача 2 (Распределение мест на финише). В финальном забеге соревнований участвуют 6 спортсменов. Сколькими способами они могут распределить между собой места на финише?
В этой задаче требуется распределить 6 человек по 6 позициям (местам). Так как спортсмены уникальны и один человек не может занять два места одновременно, применим формулу перестановок для $n = 6$:
$$P_6 = 6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$$
Существует ровно 720 различных вариантов того, в каком порядке бегуны могут пересечь финишную черту.
Задача 3 (Упорядочивание предметов). На полку необходимо расставить 3 разные книги — по математике, по физике и по химии. Требуется определить, сколькими способами можно это сделать.
Так как количество элементов $n = 3$, подставим данное значение в формулу факториала:
$$P_3 = 3! = 1 \cdot 2 \cdot 3 = 6$$
Существует ровно 6 уникальных вариантов расстановки. Полный список всех возможных последовательностей взаимного расположения книг выглядит следующим образом:
- Математика, Физика, Химия
- Физика, Математика, Химия
- Химия, Физика, Математика
- Математика, Химия, Физика
- Физика, Химия, Математика
- Химия, Математика, Физика
С увеличением количества элементов во множестве число возможных вариантов расстановки растет очень стремительно. Если для 3 элементов существует всего 6 вариантов, для 4 элементов их количество возрастет до 24, для 5 элементов составит 120, а для 6 элементов — уже 720 вариантов.