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

Научимся грамотно менять элементы местами и с этими знаниями откроем тайну Сатурна, расшифруем секретные послания ученых и разгадаем загадки Галилея.

    graph TD
        permutation[Перестановка]:::featured -->|Без повторений| pwr[" $\displaystyle P_n = n!$ "]
        permutation -.->|С повторениями $^*$ | pr[" $\displaystyle P_{n_1, \ \ldots, \ n_k} = \frac{n!}{n_1! \ \ldots \ n_k!}$ "]

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

Перестановка из n элементов — упорядоченная комбинация размером n, составленная с использованием элементов всех n видов.

Примеры перестановок

Все перестановки из цифр 1 и 3:

(1, 3) \qquad (3, 1)

Все перестановки из букв a, b и c:

(a,b,c) \quad (b,a,c) \quad (c,a,b) \\ (a,c,b) \quad (b,c,a) \quad (c,b,a)

Перестановки — частный случай размещений без повторений из n элементов по n вакантным местам ( $A_n^n$ ), то есть когда размещении задействованы все имеющиеся элементы!

Число перестановок

P_n = n!

Через размещения

Так как перестановки являются лишь частным случаем размещений без повторений, то для подсчета их количества будут работать соответствующие формулы, например факториальная:

P_n = A^n_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!

$\blacksquare$

Если вас смущает, что факториал нуля вдруг оказался равен 1, этот вопрос подробно и понятно рассматривался в теме про факториалы. Обязательно ознакомьтесь!

Через правило умножения

Можно доказать формулу и по старинке. Есть n вакантных мест. На первое место можно поставить любой из n элементов. Вне зависимости от сделанного выбора, на второе место можно поставить $n-1$ элементов и так далее. Значит, мы можем применить правило умножения:

P_n = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 = n!

$\blacksquare$

На передовой науки

В научной конференции принимают участие 9 ученых. Они по порядку выступают со своими докладами. Сколькими способами организатор конференции может составить расписание этих докладов?

Решение

Выступить должен каждый ученый, значит в каждом варианте расписания (комбинация) участвуют все элементы (ученые). Сами же расписания отличаются только порядком докладов. Значит, каждое расписание по сути своей есть перестановка. Найдем их количество с помощью выведенной формулы:

P_9 = A_9^9 = 9! = 362 \ 880

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

Число перестановок с повторениями

Пускай n элементов разбиты на k групп дубликатов: в первой группе $n_1$ одинаковых элементов, во второй $n_2$ одинаковых элементов, ..., в k-той $n_k$ одинаковых элементов.

Количество уникальных перестановок из этих элементов рассчитывается по формуле:

P(n_1, \ n_2, \ \ldots, \ n_k) = \frac{n!}{n_1! \ n_2! \ \ldots \ n_k!}

Доказательство

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

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

Наша задача — выделить среди этой кучи перестановок уникальные, которые мы будем называть шаблонами и найти количество их дубликатов, которые эти самые шаблоны и составляют.

Возьмем какую-нибудь уникальную перестановку (шаблон), например такую, в которой элементы из своих групп стоят рядом друг с другом.

\underbrace{aa \ldots a}_{\small n_1} \ \ \underbrace{bb \ldots b}_{\small n_2} \ \ldots \ \underbrace{cc \ldots c}_{\small n_k}

Элементы первой группы можно свободно менять местами друг с другом $n_1!$ способами. Так как элементы этой группы одинаковые, то такие «новые» перестановки шаблон никак не меняют. По такой же логике между собой можно менять местами элементы второй группы $n_2!$ способами, да хоть k-ой группы $n_k!$ способами, и от этих перестановок сам шаблон останется точно таким же.

Итак, одинаковые элементы первой группы можно расставить $n_1!$ способами. Вне зависимости от выбранной расстановки элементов первой группы, одинаковые элементы второй группы можно расставить $n_2!$ способами и так далее. По правилу умножения находим все способы составить шаблон:

n_1! \cdot n_2! \cdot \ldots \cdot n_k!

Можно рассмотреть какой-нибудь другой шаблон, например, когда элементы первых двух групп идут попарно:

ab \ ab \ldots ab \ \ldots \ cc\ldots c

Все те же рассуждения можно применить и к нему, а значит его тоже можно составить $n_1! \cdot \ldots \cdot n_k!$ способами. Да и вообще, любой шаблон можно составить этим одинаковым количеством способов.

Получается, что среди всех $n!$ перестановок каждое уникальное расположение элементов (шаблон) всегда представлено в виде $n_1!\cdot\ldots\cdot n_k!$ одинаковых перестановок.

Если мы поделим число всех перестановок на количество одинаковых перестановок, образующих шаблон, мы получим общее число шаблонов, то есть общее число уникальных перестановок:

P(n_1, \ n_2, \ \ldots, \ n_k) = \frac{n!}{n_1! \ n_2! \ \ldots \ n_k!}

$\blacksquare$

Математика всему голова!

Сколько различных слов можно составить из букв слова «математика»?

Решение

Разделим все буквы в слове «математика» на группы одинаковых букв:

Три буквы «а»
По две буквы «м» и «т»
Все остальные буквы в единственном экземпляре

Найдем количество перестановок с повторениями по выведенной формуле:

P(3,\ 2,\ 2,\ 1,\ 1,\ 1) = \frac{10!}{3! \ 2! \ 2! \ 1! \ 1! \ 1!} = 151 \ 200

Не путайте «размещения с повторениями» и «перестановки с повторениями»!

В размещениях с повторениями мы можем неограниченное количество раз использовать один и тот же элемент.

В перестановках с повторениями каждый элемент ипользуется только один раз, но среди самих элементов могут быть дубликаты в разных количествах!