Глава
Теория
Сочетание — это выбор объектов без учёта порядка. Если порядок выбора не является частью ответа, то последовательный подсчёт обычно создаёт переучёт. Число способов выбрать \(k\) объектов из \(n\) обозначается \(\binom{n}{k}\).
В олимпиадной комбинаторике сочетания важны не только как формула. Они помогают кодировать объекты: выбрать позиции единиц, выбрать вершины многоугольника, выбрать границы прямоугольника, выбрать элементы подмножества или выбрать места для разделителей.
Если объект полностью задаётся набором выбранных элементов, используйте сочетания. Если объект задаётся позициями специальных символов, выбирайте позиции. Если условие “не подряд”, попробуйте сначала записать выбранные числа \(a_1<\cdots Если формула выглядит алгебраически, попробуйте задать вопрос: что именно считает левая часть, и что считает правая?
Примеры
Команда не зависит от порядка выбора.
Задача. Сколькими способами можно выбрать \(3\) учеников из \(8\)?
Если выбирать по порядку, получим \(8\cdot7\cdot6\), но каждая команда из трёх учеников посчитана \(3!\) раз. Поэтому ответ \(8\cdot7\cdot6/3!=56\).
Комментарий. Это и есть \(\binom{8}{3}\).
Иногда проще выбрать тех, кто не входит.
Задача. Сколькими способами можно выбрать \(4\) книги из \(10\), если одна заданная книга должна быть выбрана?
Заданная книга уже выбрана. Остаётся выбрать ещё \(3\) книги из остальных \(9\). Ответ \(\binom{9}{3}=84\).
Комментарий. Не нужно отдельно рассматривать место заданной книги.
Метод дополнения сокращает перебор случаев.
Задача. Из \(5\) мальчиков и \(4\) девочек выбирают команду из \(3\). Сколько команд содержат хотя бы одну девочку?
Всего команд \(\binom{9}{3}=84\). Команд без девочек: \(\binom{5}{3}=10\). Значит нужных \(84-10=74\).
Комментарий. Слова “хотя бы” часто зовут дополнение.
Одно и то же множество можно посчитать по наличию специального элемента.
Задача. Докажите \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Выбираем \(k\)-элементное подмножество из \(n\)-элементного множества и фиксируем один элемент \(x\). Либо \(x\) не выбран: тогда выбираем все \(k\) элементов из остальных \(n-1\). Либо \(x\) выбран: тогда надо выбрать ещё \(k-1\) из остальных \(n-1\). Получаем тождество.
Комментарий. Это доказательство лучше запоминается, чем формула.
Разделители кодируют распределение.
Задача. Сколько положительных решений имеет \(x+y+z=10\)?
Положим сначала по \(1\) в каждую переменную. Остаётся распределить \(7\) единиц между \(3\) переменными. Это задаётся двумя разделителями среди \(9\) позиций, значит \(\binom{9}{2}=36\).
Комментарий. Можно также думать о строке из единиц и двух перегородок.
Сдвиг убирает обязательные промежутки.
Задача. Сколько \(3\)-элементных подмножеств \(\{1,\ldots,10\}\) не содержат соседних чисел?
Пусть выбраны \(a_1
Комментарий. Это стандартная техника для запрета соседства.
Разбиение по типу выбранных объектов.
Задача. Сколько команд из \(4\) человек можно выбрать из \(6\) мальчиков и \(5\) девочек так, чтобы в команде было ровно \(2\) девочки?
Выбираем \(2\) девочки из \(5\) и \(2\) мальчика из \(6\). Эти выборы независимы. Ответ \(\binom{5}{2}\binom{6}{2}=10\cdot15=150\).
Комментарий. Типичная задача на выбор из двух групп.
Сочетания помогают понимать размер слоёв.
Задача. Почему среди \(7\) подмножеств четырёхэлементного множества найдутся два, одно из которых содержится в другом?
Все \(16\) подмножеств можно разбить на \(6\) цепочек по включению, например так: одна длинная цепочка от \(\varnothing\) до всего множества, три цепочки длины \(3\) и две одиночные пары среднего слоя. Тогда по принципу Дирихле \(7\) выбранных подмножеств попадут в одну цепочку, а в цепочке любые два сравнимы.
Комментарий. Это preview будущих идей о цепях и антицепях.
Задачи
Сколькими способами можно выбрать \(2\) учеников из \(5\)?
Порядок выбора не важен.
Упорядоченно можно выбрать \(5\cdot4=20\) способами, но каждая пара посчитана дважды. Ответ \(10\).
Сколько непустых подмножеств имеет множество из \(4\) элементов?
Все подмножества минус пустое.
Всего \(2^4=16\) подмножеств. Пустое одно, значит непустых \(15\).
Сколько \(3\)-элементных подмножеств имеет множество из \(7\) элементов?
Это \(\binom{7}{3}\).
Получаем \(\binom{7}{3}=7\cdot6\cdot5/3!=35\).
Объясните, почему \(\binom{10}{3}=\binom{10}{7}\).
Выбор \(3\) элементов определяет \(7\) невыбранных.
Каждому выбору \(3\) элементов соответствует выбор \(7\) элементов, которые не вошли. Это взаимно однозначное соответствие, значит числа равны.
Сколько двоичных строк длины \(6\) содержат ровно две единицы?
Выберите позиции двух единиц.
Нужно выбрать \(2\) позиции из \(6\). Ответ \(\binom{6}{2}=15\).
Из \(5\) девочек и \(4\) мальчиков выбирают команду из \(3\), в которой ровно \(2\) девочки. Сколько вариантов?
Выберите девочек и мальчика независимо.
Девочек выбираем \(\binom{5}{2}=10\) способами, мальчика \(4\) способами. Всего \(40\).
Из \(5\) девочек и \(4\) мальчиков выбирают команду из \(4\). Сколько команд содержат не менее двух девочек?
Разберите \(2,3,4\) девочки.
Получаем \(\binom{5}{2}\binom{4}{2}+\binom{5}{3}\binom{4}{1}+\binom{5}{4}=10\cdot6+10\cdot4+5=105\).
Сколько диагоналей имеет выпуклый \(12\)-угольник?
Выберите пару вершин и вычтите стороны.
Любые две вершины задают отрезок: \(\binom{12}{2}=66\). Из них \(12\) сторон. Значит диагоналей \(66-12=54\).
В группе \(10\) учеников, среди них \(3\) отличника. Сколькими способами выбрать команду из \(4\), чтобы в ней был хотя бы один отличник?
Все команды минус команды без отличников.
Всего \(\binom{10}{4}=210\). Без отличников выбираем \(4\) из оставшихся \(7\): \(\binom{7}{4}=35\). Ответ \(175\).
Сколько \(3\)-элементных подмножеств множества \(\{1,2,\ldots,10\}\) не содержат соседних чисел?
Используйте сдвиг \(b_i=a_i-(i-1)\).
Пусть \(a_1
Сколько неотрицательных решений имеет \(x+y+z=8\)?
Используйте \(8\) единиц и \(2\) перегородки.
Строка состоит из \(8\) единиц и \(2\) перегородок, всего \(10\) символов. Выбираем позиции перегородок: \(\binom{10}{2}=45\).
Сколько положительных решений имеет \(x+y+z=10\)?
Сначала вычтите по \(1\) из каждой переменной.
Пусть \(x'=x-1\), \(y'=y-1\), \(z'=z-1\). Тогда \(x'+y'+z'=7\), где переменные неотрицательны. Ответ \(\binom{9}{2}=36\).
Докажите комбинаторно, что \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
Зафиксируйте один специальный элемент.
Считаем \(k\)-элементные подмножества \(n\)-элементного множества. Специальный элемент либо не выбран: \(\binom{n-1}{k}\), либо выбран: \(\binom{n-1}{k-1}\). Сумма этих двух непересекающихся случаев даёт все подмножества.
Докажите, что число способов выбрать \(3\) человека из \(m\) мальчиков и \(n\) девочек равно \(\binom{m}{3}+\binom{m}{2}\binom{n}{1}+\binom{m}{1}\binom{n}{2}+\binom{n}{3}\).
Разбейте по числу мальчиков в команде.
Команда из \(3\) человек может содержать \(3,2,1,0\) мальчиков. Эти случаи не пересекаются. В каждом случае выбираем нужное число мальчиков и девочек, получая указанную сумму.
Сколько \(6\)-элементных подмножеств \(\{1,\ldots,12\}\) не содержат соседних чисел?
Используйте формулу сдвига для \(k=6\).
Для выбранных \(a_1<\cdots
Сколько \(4\)-элементных подмножеств \(\{1,\ldots,20\}\) содержат хотя бы одно число, кратное \(5\)?
Вычтите подмножества без кратных \(5\).
Всего \(\binom{20}{4}=4845\). Чисел, не кратных \(5\), \(16\), значит подмножеств без кратных \(5\): \(\binom{16}{4}=1820\). Ответ \(4845-1820=3025\).
Из \(6\) мальчиков и \(5\) девочек выбирают команду из \(5\). Сколько команд имеют больше мальчиков, чем девочек?
Возможны \(3,4,5\) мальчиков.
Считаем случаи: \(3\) мальчика и \(2\) девочки: \(\binom{6}{3}\binom{5}{2}=200\); \(4\) мальчика и \(1\) девочка: \(\binom{6}{4}\binom{5}{1}=75\); \(5\) мальчиков: \(\binom{6}{5}=6\). Итого \(281\).
На окружности отмечены \(9\) точек. Сколько треугольников с вершинами в этих точках можно построить?
Любые три точки на окружности образуют треугольник.
Нужно выбрать \(3\) вершины из \(9\). Ответ \(\binom{9}{3}=84\).
Сколько решений в неотрицательных целых числах имеет \(x+y+z=12\), если \(x\ge2\), \(y\ge3\)?
Замените \(x'=x-2\), \(y'=y-3\).
Пусть \(x'=x-2\), \(y'=y-3\). Тогда \(x'+y'+z=7\), все переменные неотрицательны. Число решений равно \(\binom{9}{2}=36\).
Есть \(10\) красных и \(8\) синих шаров. Сколькими способами выбрать \(5\) шаров, чтобы красных было не менее \(3\)?
Разберите \(3,4,5\) красных.
Случаи: \(3\) красных и \(2\) синих: \(\binom{10}{3}\binom{8}{2}=3360\); \(4\) красных и \(1\) синий: \(\binom{10}{4}\binom{8}{1}=1680\); \(5\) красных: \(\binom{10}{5}=252\). Итого \(5292\).
Докажите комбинаторно тождество \(C(r,r)+C(r+1,r)+\cdots+C(n,r)=C(n+1,r+1)\).
Считайте \((r+1)\)-элементные подмножества по наибольшему элементу.
Рассмотрим все \((r+1)\)-элементные подмножества множества \(\{1,\ldots,n+1\}\). Их \(C(n+1,r+1)\). Если наибольший элемент равен \(t+1\), где \(r\le t\le n\), то остальные \(r\) элементов выбираются из первых \(t\) элементов: \(C(t,r)\) способов. Суммируя по \(t\), получаем левую часть.
Сколько \(5\)-элементных подмножеств \(\{1,\ldots,15\}\) содержат число \(1\) и не содержат соседних чисел?
Если \(1\) выбран, число \(2\) запрещено.
После выбора \(1\) нужно выбрать ещё \(4\) числа из \(\{3,\ldots,15\}\) без соседства. Это отрезок длины \(13\). Число способов выбрать \(4\) несоседних элементов из \(13\) равно \(\binom{13-4+1}{4}=\binom{10}{4}=210\).
Из \(8\) мальчиков и \(7\) девочек выбирают команду из \(6\). Сколько команд имеют хотя бы \(2\) мальчиков и хотя бы \(2\) девочек?
Разберите количество мальчиков: \(2,3,4\).
Возможны только \(2\) мальчика и \(4\) девочки, \(3\) и \(3\), \(4\) и \(2\). Получаем \(\binom{8}{2}\binom{7}{4}+\binom{8}{3}\binom{7}{3}+\binom{8}{4}\binom{7}{2}=28\cdot35+56\cdot35+70\cdot21=4410\).
Докажите, что среди любых \(7\) подмножеств множества \(\{1,2,3,4\}\) найдутся два, одно из которых содержится в другом.
Разбейте все \(16\) подмножеств на \(6\) цепочек по включению.
Достаточно разбить все подмножества на \(6\) цепочек, потому что тогда \(7\) выбранных подмножеств по принципу Дирихле попадут в одну цепочку дважды. Например, можно взять цепочки: \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\); \(\{2\}\subset\{2,3\}\subset\{2,3,4\}\); \(\{3\}\subset\{1,3\}\subset\{1,3,4\}\); \(\{4\}\subset\{1,4\}\subset\{1,2,4\}\); одиночные цепочки \(\{2,4\}\) и \(\{3,4\}\). В одной цепочке любые два множества сравнимы по включению.
Лестницы