Размещения

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

    graph TD
        arrangement[Размещение]:::featured -->|Без повторений| awr[" $\displaystyle A_n^k = \frac{n!}{(n-k)!}$ "]
        arrangement -->|С повторениями| ar[" $\displaystyle \bar{A}_n^k = n^k$ "]

Многие задачи сводятся к тому, что есть n видов элементов, из которых надо сформировать комбинации размером k, причем порядок следования элементов имеет значение.

Таким комбинациям решили дать общее название: «размещения из n по k» — из n (элементов) по k (вакантным местам). В зависимости от того, допустимо ли повторение элементов, размещения разделяют на два типа:

Размещение с повторениями — упорядоченная комбинация размером k, составленная из элементов n видов. Элементы можно использовать повторно.

Примеры размещений с повторениями

Из трех букв слова «кот» можно составить 9 размещений с повторениями по две буквы:

\begin{array}{} кк & оо & тт & ко & ок & от & то & кт & тк \end{array}

Размещение без повторений — упорядоченная комбинация размером k, составленная из элементов n видов. Элементы используются один раз.

Примеры размещений без повторений

Из трех букв слова «кот» можно составить 6 размещений без повторениями по две буквы:

\begin{array}{} ко & ок & от & то & кт & тк \end{array}

Обратите внимание, что в списке нет размещений «кк», «оо» и «тт», так как повторное использование одних и тех же элементов не допускается!

Формулы для вычисления количества размещений с повторениями и без них очень похожи. С повторениями это цепочка из k умножений числа n на само себя. Без повторений это цепочка из k умножений уменьшающихся на единицу множителей, начиная с числа n:

Число размещений с повторениями

\A^k_n = n^k

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

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

Есть n способов выбрать первый элемент этой комбинации, вне зависимости от этого выбора еще n способов выбрать второй элемент и так далее для всех k элементов в комбинации. В таких условиях можно использовать правило произведения:

\A^k_n = \underbrace{n \cdot n \cdot \ldots \cdot n}_{k \ раз} = n^k

$\blacksquare$

Исторический момент

Максим сдает тест по истории. Тест состоит из 10 вопросов, к каждому из которых надо выбрать один из 3 вариантов ответов (а, б или в) и занести их в специальный бланк. Сколькими способами Максим может заполнить бланк ответов?

Решение

Бланк ответа можно представить как комбинацию из 10 ответов. Замечаем, что 1) разные вопросы могут иметь одинаковую букву ответа и 2) каждый ответ связан с номером вопроса.

Каждый заполненный бланк ответов по сути является размещением с повторениями из 3 (букв ответов) по 10 (вопросам). Количество таких размещений можно найти по формуле:

\A_3^{10} = 3^{10} = 59\ 049

Число размещений без повторений

A_n^k = n \cdot (n-1) \cdot \ldots \cdot (n-k+1)

A_n^k = \frac{n!}{(n-k)!}

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

Смотрите доказательства верхнего и нижнего равенств в статье.

Товары по акции

На кассе в продуктовом магазине есть 6 мест для товаров по акции. Сколькими способами можно заполнить эти места, если по акции продаются 10 товаров?

Решение

Каждый способ разложить товары на кассе можно считать за размещение без повторений из 10 товаров по 6 местам. Число таких размещений находим по формуле:

A^6_{10} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151 \ 200

Больше 150 тысяч способов выставить товары по акции!