Сочетания

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

Статья

Конспект

Задачи

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

Таким неупорядоченным комбинациям математики дали свое название: «сочетания из 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

Источники12

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

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

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

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

23. Сочетания без повторений

25. Покупка пирожных

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

27. Генуэзская лотерея

28. "Спортлото"

Финальные задачи к главе II

Пособие по математике для поступающих в вузы

Кутасов А.Д., Пиголкина Т.С., Чехлов В.И., Яковлева Т.Х., 3-е изд., 1988

Примеры и задачи на сочетания