Размещения

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

Статья

Конспект

Задачи

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

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

Размещение с повторениями

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

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

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

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

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

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

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

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

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

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

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

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

\bar{A}^k_n = n^k

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

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

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

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

$\blacksquare$

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

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

Решение

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

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

\bar{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 тысяч способов выставить товары по акции!

Источники13

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

Комбинаторика

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 7-е издание, МЦНМО, 2019

Почти идеальная подача теории через жизненные примеры. Интересные задачи. Широчайший охват тем, в том числе и из высшей математики.

5. Размещения с повторениями

6. Секретный замок

7. Системы счисления и передача информации

8. Вокруг ЭВМ

9. Морской семафор

10. Точки—тире телеграфные

18. Первенство по футболу

19. Размещения без повторений

Википедия

Свободная энциклопедия

Optical telegraph

На русскоязычной и англоязычной страницах есть разная полезная информация