Размещения

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

Самый большой секрет

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

Сами комбинации могут быть представлены по-разному. Где-то это набор цифр на панели, где-то вращающиеся диски с символами, а где-то вообще набор из выступов и впадин, как на обычных ключах.

В жизни, в фильмах, в играх — тысячи их, а идея всюду одна

Предположим, мы хотим получить доступ к телефону. Для его разблокировки нужно ввести пароль из 5 цифр. Какое максимальное количество неудачных попыток мы можем совершить, если будем подбирать пароль наугад?

Мы собираемся составлять комбинации (пароли) размером 5 из 10 элементов (цифр). Важно отметить три свойства, которые характерны для таких комбинаций:

Фиксированный набор цифр
Пароль может состоять только из цифр. Никаких букв и других элементов в нем появится не может.
Порядок цифр в пароле имеет значение
Комбинации 12345 и 54321 хоть и состоят из одинаковых элементов все же являются разными паролями.
Цифры могут повторяться
Ограничений на повторное использование элементов нет. Паролем вполне себе может быть комбинация 22222.

На первое место в пароле можно поставить любую из 10 цифр. Вне зависимости от выбранной первой цифры, на второе место также можно поставить любую из 10 цифр. И так далее. Применяем правило произведения:

10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 10^5 = 100\ 000

Всего 100 тысяч возможных паролей для телефона и в худшем случае $99\ 999$ неудачных попыток его отгадать. Если не отвлекаясь ни на что тратить по 5 секунд на каждую попытку, то на подбор пароля может уйти до 140 часов!

Обратите внимание, что итоговая формула количества паролей свелась к красивой степени $10^5$ . В основании стоит количество цифр, которые можно использовать (10), а показатель равен требуемой длине пароля (5). Удобно...

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

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

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

Давайте обобщим. Есть какой-то фиксированный набор из n видов элементов: (цифр, букв, да чего угодно), причем использовать их можно сколько угодно раз. Распихивая эти элементы в k «вакантных мест» мы получаем комбинации, причем порядок расположения элементов в них имеет значение! Таким комбинациям математики дали название:

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

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

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

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

Когда говорят или пишут о размещениях с повторениями, используют фразы:

«Размещение с повторениями из n по k»
«k-размещение с повторениями из n»

Расшифровывать это можно как «размещение с повторениями из n (типов элементов) по k (вакантным местам)».

Например, размещение из 3 (букв) по 2 (буквы в паре) из примера выше. А задача про замки сводится к поиску размещений с повторениями из 10 (возможных букв на диске) по 5 (этим самым дискам).

Количество всех размещений с повторениями из n по k записывают как $\A^k_n$ . Буква A означает английское слово arrangement — «размещение», «расстановка». Черта сверху означает возможность использования одних и тех же элементов.

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

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

\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

Лучший Новый Год

Таня поставила новогоднюю елку и хочет повесить на нее 7 игрушек. В коробке есть красные, синие и зеленые игрушки. По форме они делятся на круглые и в виде снежинок. Сколькими способами Таня может украсить елку?

Решение

Игрушки различаются по цвету и форме, поэтому сначала найдем все их типы. По правилу произведения всего $3 \cdot 2 = 6$ различных видов игрушек. А на елку Таня хочет повесить 7 игрушек.

Разукрашенную елку можно представить как комбинацию из 7 игрушек. Дальше нужно догадаться, что 1) игрушки могут повторяться, ведь по условию это не запрещено и 2) положение игрушек на елке имеет значение.

Каждая украшенная елка по сути является размещением с повторениями из 6 (игрушек) по 7 (местам на елке). Количество таких размещений можно найти по формуле:

\A_6^7 = 6^7 = 279 \ 936

Выходит, у Тани есть почти 280 тысяч вариантов украсить елку!
Немало...

Абсолютные чемпионы

В международной математической олимпиаде с тремя призовыми местами принимает участие 20 учеников. Сколькими вариантами может определиться тройка победителей?

Вновь у нас есть фиксированный набор элементов (учеников), из которого надо построить упорядоченные комбинации размером 3. Но есть и отличия. Например, один и тот же участник не может одновременно занять 1 и 2 места, получить сразу золотую и серебреную медали. Поэтому повторений в комбинациях на этот раз быть не может!

Первое место может занять любой из 20 участников. Второе место так-то тоже может занять любой участник, кроме того, кто занял первое. Поэтому всего 19 кандидатов. По такой же логике на третье остается место всего 18 кандидатов. Применяем правило произведения:

20 \cdot 19 \cdot 18 = 6\ 840

Почти 7 тысяч возможных троек призеров!

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

Это еще один часто встречающийся вид комбинаций и вы уже догадываетесь, как они называются...

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

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

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

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

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

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

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

Читаются и записываются размещения без повторений так же, как и с повторениями:

«Размещения без повторений из n по k»
«k-размещения без повторений из n»

Количество всех размещений без повторений обозначается $A^k_n$ , так же как и с повторениями, но без верхней черты. Так как каждый множитель уменьшается на единицу, коротко через степень записать число таких размещений не выйдет. Формула получается чуть сложнее:

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

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

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

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

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

A^k_n = \underbrace{n \cdot (n-1) \cdot (n-2) \ldots}_{k \ множителей}

Обратите внимание на то, как выглядит формула при разных k:

\begin{align*} &A^2_n = n \cdot (n-1) \\ &A^3_n = n \cdot (n-1) \cdot (n-2) \\ &A^4_n = n\cdot (n-1) \cdot (n-2) \cdot (n-3) \end{align*}

Замечаем, что в последнем множителе из n всегда вычитается число, которое на единицу меньше k:

1 при $k=2$
2 при $k=3$
3 при $k=4$

В общем виде последний множитель формулы можно записать как $n - (k-1)$ :

A^k_n = n \cdot (n-1) \cdot \ldots \cdot (n - (k-1))

Если мы раскроем скобки в последнем множителе, то получим доказываемую формулу:

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

$\blacksquare$

Несмотря на свой немного странный вид эта формула обозначает элементарный алгоритм — «последовательно умножай и уменьшай множители на 1, пока их количество не станет равно размеру комбинации». Опробуем такой подход на нескольких примерах:

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

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

Решение

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

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

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

Семейный ужин

Семья собирается поужинать. За обеденным столом есть 5 свободных мест. Сколькими различными способами эти места могут занять 4 человека?

Решение

Многие могут попытаться начать решать эту задачу «естественным» путем — попробовать посчитать способы рассадить людей по местам. Но этим способом задачу быстро не решить.

Горадо проще будет, если «сменить перспективу» — не людей рассаживать по местам, а наоборот, назначать места людям! В этом случае комбинации мы будем составлять не из 4 человек по 5 местам, а из 5 мест по 4 человекам!

С такой точки зрения каждая комбинация по сути будет являться размещением без повторений из 5 свободных мест по 4 членам семьи. Число таких размещений находим по формуле:

A^4_5 = 5 \cdot 4 \cdot 3 \cdot 2 = 120

Всего 120 способов рассадить 4 человека.

Формула через факториалы

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

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

A^k_n = n^{\underline{k}} = \frac{n!}{(n-k)!}

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

У нас уже есть доказанная формула в виде цепочки умножений уменьшающихся на 1 множителей.

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

Допишем эту цепочку умножений до самого конца, до 1. Чтобы не нарушить правильность формулы нам нужно разделить на все, что мы добавили. Тогда все добавленное лишнее друг с другом сократится и никак на финальный результат не повлияет.

A^k_n = \frac{ n \cdot \ldots \cdot (n-k + 1) \cdot \overbrace{(n-k) \cdot (n-k-1) \cdot \ldots \cdot 2 \cdot 1}^{Добавили} }{ \underbrace{(n-k) \cdot (n-k-1) \cdot \ldots \cdot 2 \cdot 1}_{Скомпенсировали} }

Формула по-прежнему выдает правильные результаты (все лишнее сокращается друг с другом), но сверху и снизу получились красивые и короткие факториалы:

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

$\blacksquare$

Опробуем новый вид формулы в деле:

Архитектор чисел

Сколько двузначных чисел можно составить из цифр 1, 2, 4,7, 8,9 при условии, что каждую цифру можно использовать только один раз?

Решение

Каждое двузначное число можно рассматривать как комбинацию без повторений из 6 цифр по 2 «позициям в числе». Для нахождения всех таких размещений используем формулу через факториалы:

A^2_6 = \frac{6!}{(6 - 2)!} = \frac{6!}{4!} = \frac{720}{24} = 30

Всего из 6 цифр, причем любых, кроме 0, можно составить 30 двузначных чисел.

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

Простое умножение...

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

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

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

Так и тут. Мы нашли особый вид комбинаций — размещения, к которым можно свести целый класс комбинаторных задач. И решать эти задачи теперь можно по щелчку пальцев с помощью готовых формул!

За рубежом

Если вы захотите поискать материалы про размещения на англоязычных ресурсах, то будете сильно удивлены отсутствием информации. Термином «размещение» и обозначением $A^k_n$ там практически не пользуются. Но это не потому что там все глупые :)

Вместо них там используют понятие permutation — «перестановка», которое и выполяет роль размещений. Мы еще поговорим об этом в соответствующей теме.

Размещения в жизни

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

Семафор или общение через сигналы

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

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

Во времена Французской Революции механик Клод Шапп изобрел удобный для использования семафор. Прибор распологался на вершине башен и напоминал большие часовые циферблаты: одна длинная вращающаяся «стрелка», на обеих концах которой закреплены вращающиеся «стрелки» поменьше.

Найдем, сколько уникальных сигналов можно изобразить с помощью этого устройства. Основная стрелка может принимать горизонтальное или вертикальное положение. Маленькие стрелки могут вращаться вокруг своей оси с шагом в 45 градусов, но не перекрывая собой главную стрелку. Значит, каждая маленькая стрелка занимает одно из 7 положений.

Схема возможных положений маленьких стрелок телеграфа Шаппа

Любое возможное положение маленьких стрелок можно представить как размещение с повторениями из 7 положений по 2 стрелкам. Посчитаем количество таких размещений:

\A_7^2 = 7^2 = 49

Всего 49 уникальных сигналов можно передать, когда основная стрелка телеграфа расположена горизонтально. Если ее расположить вертикально, то добавится еще 49 сигналов. Итак, с помощью телеграфа Шаппа можно подать 98 различных сигналов! Каждому сигналу можно присвоить свою букву, цифру и еще останутся свободные сигналы для наиболее часто используемых слов!

Присвоить сигналам буквы и можно передавать сообщения!

Телеграф Шаппа был довольно практичным и применялся в широких масштабах. Проводились многокилометровые «телеграфные линии» состоящие из ряда башен с этими семафорами на крыше. Своими блестящими победами Наполеон немало обязан оптическому телеграфу, с помощью которого он имел возможность быстро передавать свои распоряжения на большие расстояния.

Семафор Шаппа использовался почти до середины 19-го века, вплоть до появления электрического телеграфа. В 1805 году, из-за проблем со здоровьем и депрессии от обвинений в плагиате своего главного изобретения, Шапп лишил себя жизни.

Азбука Морзе

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

В отличие от оптических телеграфов с их большим количеством передаваемых знаков, с помощью электричества можно передать только два вида сигнала: «есть ток» и «нет тока». Как же всего двумя сигналами передавать буквы и цифры?

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

Комбинируя различными способами «точки» и «тире» можно обозначать буквы, цифры и прочее. Буквы, которые используются часто, обозначаются одним знаком: «Е» одной точкой « • », а «Т» одним тире « — ». Редко встречающиеся буквы обозначаются большим количеством знаков. Так буква «Э» обозначается аж пятью знаками « • • — • • ». Такой способ кодирования сообщений получил название «Азбука Морзе».

Сколько букв можно обозначить с помощью «точек» и «тире»? Ответ на этот вопрос дает формула размещений с повторениями. Используя только один знак получим размещение с повторениями из 2 типов знаков по 1 количеству знаков:

\A_2^1 = 2^1 = 2

Это как раз те самые буквы «Е» и «Т». Продолжим увеличивать количество знаков:

\A^2_2 = 2^2 = 4 \qquad \A_2^3 = 2^3 = 8 \qquad \A_2^4 = 2^4 = 16

По правилу суммы всего можно обозначить 2 + 4 + 8 + 16 = 30 букв, используя не более 4 знаков. Но букв 33, а ведь еще нужно как-то обозначать знаки препинания и цифры!

Четырех знаков не хватает, поэтому добавили еще и пятый. Это еще $\A_2^5 = 32$ дополнительных обозначений, что в сумме дает уже 30 + 32 = 62. Этого количества хватит с запасом.

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

Множество металлических литер, из которых собираются слова и предложения

Таким хитрым способом Морзе удалось подобрать оптимальные комбинации знаков для своей азбуки еще до появления теории информации, которую в 40-х годах построил американский ученый Клод Шеннон.

Отобразить невообразимое

Из 19-го века переходим в наше время. Многие сегодняшние технологии для людей из предыдущих примеров выглядели бы как самая настоящая магия. Повсеместное распространение получили компьютеры самых разных видов: ПК, ноутбуки, смартфоны, консоли... Даже у лампочек уже есть «цифровые мозги»!

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

Изображение глаза, которое состоит из множества пикселей

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

Посчитаем, сколько разных цветов может сымитировать пиксель, способный менять яркость каждого канала 256 способами, где яркость 1 означает черный цвет, а 256 — самый яркий цвет канала: яркий красный, яркий зеленый или яркий синий.

Каждый цвет пикселя можно представить как размещение с повторениями из 256 степеней яркости по 3 каналам:

\A_{256}^3 = 256^3 = 16 \ 777 \ 216

Подумать только! Мельчайший элемент монитора — пиксель — может принять один из почти 17 миллионов цветов!

В 2023 году самым популярным разрешением экранов было разрешение Full HD: $1920 \times 1080$ . Это означает, что в ширину в экран укладываются 1920 пикселей, а в высоту 1080. Получается, что такие экраны состоят чуть более чем из 2 миллионов пикселей!

Сколько же изображений могут отобразить такие экраны? Каждое изображение можно представить как размещение с повторениями из $\approx 17$ миллионов цветов по $\approx 2$ миллионам пикселей на экране.

\A_{17 \ 000 \ 000}^{2 \ 000 \ 000} = 17 \ 000 \ 000^{2 \ 000 \ 000}

Это невообразимо огромное число! В одной только его записи больше 14 миллионов цифр! Поражает сам факт того, что любой среднебюджетный смартфон или монитор способен отобразить любое изображение из этого числа!