Практика
Сколькими способами можно выбрать \(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\}\). В одной цепочке любые два множества сравнимы по включению.