Сочетания

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

Высшая лига

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

На мировой уровень выходят всего три команды. Получается 3 вакантных места. Первое из этих вакантных место может занять любая из 10 команд. Вне зависимости от того, что это за команда, второе место может занять одна из 9 команд, а третье одна из 8 оставшихся. Используем правило умножения:

10 \cdot 9 \cdot 8 = 720

Вот и наш ответ! Элементарно, Ватсон!
Нет. Среди этих 720 результатов отборочных есть, например, и такие:

\begin{array}{} A,B,C & A,C,B \\ B,A,C & B,C,A \\ C,A,B & C,B,A \end{array}

Все эти шесть исходов содержат одни и те же три команды, просто в разном порядке. Но порядок нам не важен! Эти три команды, в каком порядке их не расположи, все равно уже в высшей лиге! Поэтому из всех $3! = 3\cdot 2\cdot 1 = 6$ перестановок этих трех команд нужно оставить одну любую, например A, B, C.

Точно так же любой другой неупорядоченный набор из трех команд имеет 6 дубликатов. Чтобы найти нужные нам уникальные наборы по три команды, нужно все 720 исходов поделить на 6 дубликатов, составляющих каждый набор:

\frac{720}{6} = 120

Итак, всего 120 уникальных троек победителей могут выйти на мировой уровень по результатам региональных отборочных.

Сочетания

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

Как и в случае с размещениями и перестановками, такие комбинации математики выделили в отдельную группу и дали им свое название:

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

Примеры сочетаний

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

\begin{array}{} во & вд & ва \\ & од & оа \\ && да \end{array}

Если вы знакомы с теорией множеств, то знаете, что порядок элементов в нем значения не имеет. Поэтому сочетания по сути являются множествами.

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

«Сочетание из n по k»
«k-сочетание из n»

В примере выше мы искали все сочетания из 4 (букв исходного слова) по 2 (буквам в паре), а в начале статьи все сочетания из 10 (региональных команд) по 3 (местам в высшей лиге).

Перейдем к количеству сочетаний. Их обозначают двумя способами:

C_n^k \quad или \quad \binom{n}{k}

Левая запись больше приближена к другим комбинаторным обозначениям. Буква C означает английское слово combination — «комбинация». Обозначение сочетаний в виде $C_n^k$ используется как у нас, так и за рубежом.

Правая запись тоже активно используется у нас и «там». Для удобства букву C вообще убрали и добавили скобки. Эту запись называют «биноминальным коэффициентом из n по k». А откуда это название взялось вы узнаете в интересной и крайне полезной теме, посвященной биному Ньютона.

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

Число сочетаний

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

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

Для начала представим, что мы как-то нашли все сочетания, то есть все неупорядоченные комбинации и знаем их количество — $C_n^k$ . Каждое из этих сочетаний это комбинация из k элементов.

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

Раз из каждого сочетания (всего их $C_n^k$ ) получается $k!$ размещений, то всего имеем $C_n^k \cdot k!$ разных размещений. Это будет количество всех возможных размещений из n по k, то есть $A_n^k$ :

C_n^k \cdot k! = A_n^k

Делим обе части равенства на $k!$ и получаем искомую формулу:

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

$\blacksquare$

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

Выпишем в ряд все n элементов, из которых мы планируем собирать сочетания:

a_1, \ a_2, \ a_3, \ \ldots, \ a_n

Теперь над каждым элементом поставим либо 0 — не включен в сочетание, либо 1 — включен в сочетание. Например:

\begin{array}{} 0 & 1 & 1 & 0 & \ldots & 0 \\ a_1 & a_2 & a_3 & a_4 & \ldots & a_n \end{array}

Так как сочетания у нас состоят из k элементов, то над элементами мы должны как-то расставить k единиц и соответственно $(n-k)$ нолей. И каждая такая расстановка цифр порождает сочетание.

Количество перестановок этих повторящихся цифр, а значит и количество сочетаний, можно найти по формуле перестановок с повторениями:

C_n^k = P(\ \underbrace{n-k}_{0} \ , \ \underbrace{k}_{1} \ ) = \frac{n!}{(n-k)! \ k!} \\ C_n^k = \frac{n!}{(n-k)! \ k!}

$\blacksquare$

Списать не получится

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

Решение

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

Нам нужно выбрать 3 учителей из 20. Другими словами, нам нужно составить комбинацию из трех человек. Важно, что порядок выбранных учителей не имеет значения, важен лишь сам факт того, что они состоят в комиссии.

Тогда каждую экзаминационную комиссию можно представить как сочетание из 20 учителей по 3 вакантным местам в комиссии. Находим количество сочетаний по выведенной формуле:

C_{20}^3 = \frac{20!}{17! \cdot 3!} = \frac{18 \cdot 19 \cdot 20}{6} = 1140

Сразу видно, что считать это вручную точно не самая разумная идея...

Для сравнения, если бы порядок учителей в комиссии был важен, нужно было бы считать размещения. Их в 6 раз больше, чем сочетаний: $A_{20}^3 = 6840$ .

Большая игра

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

Решение

В каждом матче друг против друга играют две команды. Их порядок не имеет значения. Получается, что каждый матч можно рассматривать как сочетание из 12 команд по 2 «сторонам» в матче. Найдем их количество с помощью выведенной формулы:

C_{12}^2 = \frac{12!}{(12 - 2)! \ 2!} = \frac{11 \cdot 12}{2} = 66

Так как команды друг против друга играют дважды, то всего на чемпионате будет сыграно $66 \cdot 2 = 132$ матча.

Самый важный ответ

Количество сочетаний $C_n^k$ дает ультимативный ответ на самый базовый вопрос всей комбинаторики — «Сколькими способами из n объектов можно выбрать k объектов?»

Именно поэтому сочетания чаще других встречаются в комбинаторных задачах и других областях математики.

Метод перегородок

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

Каждую покупку будем записывать в виде набора единиц (1) и разделителей (|). Единица означает купленное пирожное, а разделитель означает «переход» к следующему типу пирожных: от песочных к ореховым, от ореховых к чизкейкам и так далее. Рассмотрим два примера:

|11|11|111 \qquad 11|||11111

Первый набор обозначает покупку 0 песочных, 2 ореховых, 2 чизкейков и 3 фруктовых пирожных. Второй: 2 песочных, 0 ореховых, 0 чизкейков и 5 фруктовых.

Получается, любую возможную покупку мы можем «зашифровать» в виде 7 единиц, потому что покупаем 7 пирожных, и 3 разделителей, потому что они образут 4 группы, в которее мы вставляем единицы.

Каждая такая «зашифрованная» покупка по сути является перестановкой с повторениями 7 единиц и 3 разделителей. Найдем количество всех таких перестановок по формуле:

P(7, 3) = \frac{(7+3)!}{7! \ 3!} = 120

Итак, купить 7 пирожных 4 видов с возможными повторениями можно 120 способами!

Сочетания с повторениями

Мы уже знаем про размещения с повторениями и без повторений. У сочетаний точно такое же разбиение. Вводим новое понятие:

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

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

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

\begin{array}{ccc|c} во & вд & ва & вв & оо \\ & од & оа & дд \\ && да & аа \end{array}

Читаются и записываются аналогично:

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

Число сочетаний с повторениями обозначается почти так же, как и обычные сочетания, но над буквой C добавляется черта: $\bar{C}_n^k$ . Отдельного обозначения без буквы C и через скобки не применяется!

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

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

\bar{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{(n-1)! \ k!}

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

Обобщим метод перегородок из примера с пирожными.

Будем составлять комбинации из единиц (1) и разделителей (|). Единица означает, что мы взяли элемент, а тип этого элемента определяется положением разделителей. Пример:

111||1|11

Данная комбинация означает, что мы взяли 3 элемента первого типа, 0 элементов второго типа, 1 элемент третьего типа и 2 элемента четвертого типа.

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

Тип \ 1 \underset{Разд. \ 1}{|} Тип \ 2 \underset{Разд. \ 2}{|} \ldots \underset{Разд. \ n-1}{|} Тип \ n

Каждую расстановку $n-1$ разделителей типов и k единиц можно рассматривать как перестановку с повторениями. Найдем количество таких перестановок по формуле:

\bar{C}_n^k = P(n-1, k) = \frac{(n-1+k)!}{(n-1)! \ k!} = \ldots

Теперь в скобках в знаменателе дроби добавим и сразу вычтем k. Результат не поменяется, зато теперь выражение имеет вид формулы сочетаний из $n-1+k$ по k:

\ldots = \frac{(\blue{n-1+k})!}{(\blue{n-1 +k}-k) \ k!} = C_{n-1+k}^k

\bar{C}_n^k = C_{n+k-1}^k

$\blacksquare$

Мелочь, а приятно!

Около кассы магазина продаются открытки 10 видов. Сколькими способами можно купить 12 открыток для поздравлений?

Решение

Из условия задачи ясно, что мы можем покупать одинаковые виды открыток (12 штук разных видов никак не набрать). Покупаем их мы разом, поэтому порядок не имеет значение. Значит, каждую такую покупку можно рассматривать как сочетание с повторениями из 10 видов открыток по 12 «вакантным местам» в корзине.

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

\bar{C}_{10}^{12} = C_{10 + 12 - 1}^{12} = \frac{(10+12-1)!}{(10 - 1)! \ 12!} = 293 \ 930

Великий маг

Волшебник Инвокер может управлять сферами стихий трех видов: огня, жизни и скорости. Каждый набор сфер позволяет ему создать заклинание. Например, призванные в любом порядке сферы «Жизнь, скорость, скорость» призывают разрушительное торнадо.

Инвокер

Игра Dota 2, Valve

Сколько разных заклинаний может сотворить Инвокер, используя наборы из трех сфер? А сколько мог бы сотворить, если бы умел составлять наборы из пяти сфер?

Решение

Имеем три вакантных места. Их можно заполнить сферами трех разных видов, причем сферы могут повторяться и порядок их расположения роли не играет. Значит, каждый набор из трех сфер по сути является сочетанием с повторениями из 3 видов сфер по 3 вакантным местам.

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

\bar{C}_3^3 = C_{3 + 3 - 1}^3 = \frac{(3+3-1)!}{(3-1)! \ 3!} = \frac{5!}{2! \ 3!} = 10

Выходит, используя наборы из трех сфер Инвокер может создать 10 разных заклинаний. Для наборов из 5 сфер решение аналогичное, только вакантных мест уже 5:

\bar{C}_3^5 = C_{3+5-1}^5 = \frac{(3+5-1)!}{(3 - 1)! \ 5!} = \frac{7!}{2! \ 5!} = 21

Итак, $\bar{C}_3^3 = 10$ заклинаний для наборов из трех сфер и $\bar{C}_3^5 = 21$ заклинаний для наборов из пяти сфер.

Сочетания в жизни

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

Флажный семафор

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

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

Флажок может находиться в одной из 8 позиций: вниз/вверх, вправо/влево и еще четыре диагональные позиции. Всего флажка два, они одинаковые и не могут занимать одну и ту же позицию.

Сколько всего различных сигналов можно передать используя флажный семафор? 8 возможных положений каждого флажка, два флага в одном и том же положении быть не могут, а порядок флажков не имеет значения.

Значит, сигналы двумя флажками можно рассматривать как сочетания из 8 возможных положений по 2 флажкам. Найдем количество таких сочетаний:

C_8^2 = \binom{8}{2} = \frac{8!}{(8-2)! \ 2!} = \frac{8!}{6! \ 2!} = 28

Если добавить к этим 28 сигналам еще варианты, когда оба флажка опущены ровно вниз и оба подняты вверх, получим всего 30 сигналов. Этого как раз почти хватит, чтобы каждому сигналу назначить свою букву русского алфавита. Похожие буквы, такие как «И, Й», «Е, Ё, Э» и «Ь,Ъ» объединяют в группы и выдают по одному сигналу на группу.

Тогда 29 сигналов идут на буквы (и группы букв), и остается еще один сигнал для обозначения разделения слов — пробела.

Помимо букв положениям флажков можно назначать цифры или даже какие-то условные сигналы (например «Отступаем!»). Чередуя эти положения можно передавать короткие сообщения:

Математика лотереи

Лотерея — популярная азартная игра. Правила у всех лотерей свои, но примерная суть такая: люди покупают недорогие билеты с числом или числами, а в день розыгрыша выясняется, оказались ли купленные «числа» пустышками или выигрышными. Хочешь увеличить свои шансы на выигрыш? Покупай больше билетов!

Сейчас поговорим про «Генуэзскую лотерею», которая была очень популярна в прошлом, а ее аналоги (например лото) проводится даже в наши дни. Участники покупали билеты с одним, двумя, тремя, четырьмя или пяти числами от 1 до 90. В день розыгрыша из мешка вынимали 5 жетонов также с числами от 1 до 90. Если числа на билете участника совпадают с числами на вынутых жетонах, то участник получал денежный приз.

Пускай числа на жетонах оказались следующими: 1, 20, 44, 56, 89. Тогда участник с билетом (20, 44) получит выигрыш, а участник с билетом (1, 56, 70) не получит ничего, ведь числа 70 среди выигрышных нет!

Лотерейные билеты для американской лотереи Power Ball

Выигрышный билет с одним числом приносил в 15 раз больше своей стоимости. С двумя числами — в 270 раз больше. С тремя — в 5500 раз. С четырьмя — в $75 \ 000$ раз. А с пятью вообще в $1 \ 000 \ 000$ раз!

Казалось бы, вытаскивают целых 5 чисел, а всего их не особо много — 90. Не так уж и сложно угадать 2 или 3 цифры и неплохо подзаработать! Возможно, стоит купить билет и проверить свою удачу? Примерно так думают многие участники лотерей.

Мы уже решили множество задач и знаем, как легко в комбинаторике из небольших чисел могут получиться огромные! Посчитаем общее число исходов лотереи. Вытаскиваются 5 чисел от 1 до 90. Их порядок не имеет значение и повторяться они не могут. Тогда каждый вариант розыгрыша это сочетание из 90 чисел по 5 выигрышным жетонам:

C_{90}^5 = \frac{90!}{85! \ 5!} = 43 \ 949 \ 268

Предположим, что участник купил билет с одним числом, на котором написано 52. Значит, во время розыгрыша надо, чтобы точно вынули число 52 и еще любые четыре числа из 89 оставшихся. То есть среди всех $C_{90}^5$ исходах лотереи выиграет он в $C_{89}^4$ случаях:

C_{89}^4 = \frac{89!}{85! \ 4!} = 2 \ 441 \ 626

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

\frac{C_{89}^4}{C_{90}^5} = \frac{89!}{85! \ 4!} \cdot \frac{85! \ 5!}{90!} = \frac{5}{90} = \frac{1}{18}

Это означает, что если игрок будет много и регулярно покупать билеты с одним числом, то в среднем выигрывать он будет один раз из 18, и то не факт! Но уловка состоит в том, что даже в случае выигрыша он отобьет лишь стоимость 15 билетов!

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

Определение «выигрышных» чисел во время розыгрыша

В этот момент большая часть участников понимает, что потратили деньги впустую

С одним числом понятно, а как обстоят дела с билетами на 2, 3 и более чисел? Давайте посчитаем! Если купить билет с двумя числами, то остальные 3 из оставшихся 88 чисел могут быть любыми. Всего $C_{88}^3$ выигрышных вариантов. Посчитаем шансы:

\frac{C_{88}^3}{C_{90}^5} = \frac{88!}{85! \ 3!} \cdot \frac{85! \ 5!}{90!} = \frac{4 \cdot 5}{89 \cdot 90} = \frac{2}{801}

В среднем из 801 купленных билетов с двумя числами только 2 билета окажутся удачными. Но выигрыш с этих двух билетов покроет стоимость лишь 540 билетов, а организаторы останутся в плюсе на 261 билет! Получается, покупать билеты с двумя числами еще менее выгодно, чем с одним числом.

Чем больше чисел на билете — тем меньше шансов выиграть. В крайнем случае, когда на билете 5 чисел, шанс выиграть буквально один к 44 миллионам! А приз покроет стоимость только миллиона билетов!

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

Гораздо приятнее будет на эти деньги взять себе чашечку горячего какао с пирожным. Они принесут вам удовольствие в $100 \%$ случаев. ☕ 🍰 😌