Сочетания

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

    graph TD
        combination[Сочетание]:::featured -->|Без повторений| cwr[" $\displaystyle C_n^k = \frac{n!}{(n-k)! \ k!}$ "]
        combination -->|С повторениями| cr[" $\displaystyle \bar{C}_n^k = C_{n+k-1}^k$ "]

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

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

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

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

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

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

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

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

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

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

Количество сочетаний обозначается двумя способами:

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

Обозначение слева читается как «сочетания из n по k», а справа как «биноминальный коэффициент из 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$ .

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

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

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

Число сочетаний с повторениями обозначается только одним способом — $\bar{C}_n^k$ .

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

\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