Сочетания

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

Например:
Из 10 программистов нужно отобрать 4 для участия в проекте. Сколькими способами это можно сделать?
$$\mathrm{ n = 10,\ \ \ k=4 }$$ В данном случае, порядок отбора не важен (выборка неупорядоченная); каждый кандидат может войти только один раз в выборку (выборка без повторений). Поэтому рассматриваем неупорядоченные ⟨10,4⟩ –выборки без повторений. Количество способов отбора равно: $$\mathrm{ C_{10}^4=\frac{10!}{6!\ 4!}=\frac{10\cdot 9\cdot 8\cdot 7}{1\cdot 2\cdot 3\cdot 4}=210 }$$ Ответ: 210.

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

Например:
Нужно отобрать 4 программистов для участия в проекте. Многочисленных претендентов можно разделить на две категории: желающих работать удаленно и предпочитающих работу в офисе. Сколько всего комбинаций из любителей офиса и удалёнки может оказаться в выбранной четвёрке? $$\mathrm{ n = 2,\ \ \ k=4 }$$ Порядок отбора не важен; кандидатов из каждой категории может быть несколько или ни одного. Поэтому рассматриваем неупорядоченные ⟨2,4⟩ –выборки с повторениями: $$ \mathrm{ \overline{C}_2^4=\frac{(2+4-1)!}{(2-1)4!}=\frac{5!}{4!}=5 } $$ Всего – 5 комбинаций: OOOO,OOOD,OODD,ODDD,DDDD
где O – любитель офиса; D – любитель удалёнки. Напоминаем, что порядок не важен – важен только состав группы.
Ответ: 5.

п.3. Биномиальные коэффициенты и их свойства

Подробно о биноме – см. §28 справочника для 7 класса.
Для n-й степени бинома справедливо выражение: $$ \mathrm{ (a\pm b)^n=a^n+C_n^1a^{n-1}b\pm C_n^2a^{n-2}b^2+...+C_n^{n-1}b^n } $$ где \(\mathrm{C_n^k}\) – биномиальные коэффициенты, к оторые одновременно являются количествами сочетаний без повторений из n по k: $$ \mathrm{ C_n^k=\frac{n!}{(n-k)!k!} } $$ Таким образом, биномиальные коэффициенты можно определять как с помощью треугольника Паскаля, так и с помощью данной формулы.
Заметим, что в литературе также часто встречается обозначение \(\mathrm{\left(_k^n\right)}\) для биномиальных коэффициентов \(\mathrm{\left(C_n^k\right)}\).

Свойства биномиальных коэффициентов

п.4. Примеры

Пример 1. На столе лежит 10 яблок и 5 груш.
1) Сколькими способами можно выбрать 7 фруктов?
2) Сколькими способами можно выбрать 7 фруктов, чтобы среди них было 3 груши?


1) Всего у нас n = 10 + 5 = 15 фруктов. Нужно выбрать k = 7 фруктов.
Порядок выбора не важен, т.е. выборка неупорядоченная. Находим: $$ \mathrm{ C_n^k=C_{15}^7=\frac{15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}=6435 } $$ Существует 6435 способов выбрать 7 фруктов из 15.

2) Выбираем 4 яблока из 10 и 3 груши из 5.
Для яблок: $$ \mathrm{ C_{10}^4=\frac{10\cdot 9\cdot 8\cdot 7}{1\cdot 2\cdot 3\cdot 4}=210 } $$ Для груш: $$ \mathrm{ C_3^5=C_{5}^2=\frac{5\cdot 4}{1\cdot 2}=10 } $$ По правилу произведения, общее количество способов выбрать 4 яблока и 3 груши: $$ \mathrm{ C_{10}^3\cdot C_{5}^3=210\cdot 10=2100 } $$ Ответ: 1) 6435; 2) 2100.

Пример 2. В кондитерском магазине продаётся 4 вида пирожных. Сколькими способами можно купить 7 пирожных? $$ \mathrm{ n=4,\ \ \ k=7 } $$ Порядок выбора пирожных неважен – выборка неупорядоченная; пирожные одного вида могут повторяться. Значит, находим количество сочетаний с повторениями: $$ \mathrm{ \overline{C}_4^7=C_{7+4-1}^7=C_{10}^7=C_{10}^3=\frac{10\cdot 9\cdot 8}{1\cdot 2\cdot 3}=120 } $$ Ответ: 120

Пример 3. Рота состоит из 3 офицеров, 6 сержантов и 15 рядовых. Сколькими способами можно выбрать из них отряд, состоящий из 1 офицера, 2 сержантов и 5 рядовых?

По всем трём множествам делаем неупорядоченную выборку (т.е., сочетания) без повторений.
Выбираем офицеров: \(\mathrm{C_3^1=\frac31=3}\)
Выбираем сержантов: \(\mathrm{C_6^2=\frac{6\cdot 5}{1\cdot 2}=15}\)
Выбираем рядовых: \(\mathrm{C_{15}^6=\frac{15\cdot 14\cdot 13\cdot 12\cdot 11}{1\cdot 2\cdot 3\cdot 4\cdot 5}=3003}\)
По правилу произведения, отряд можно выбрать:
\(\mathrm{3\cdot 15\cdot 3003=135135}\) способами.
Ответ: 135135.

Пример 4. Найдите сумму
a) \(\mathrm{C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6}\)
По свойству суммы \(\mathrm{\sum_{k=0}^6C_6^k=2^6}\). Получаем: $$ \mathrm{ C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6=\sum_{k=0}^6C_6^k-C_6^0=2^6-1=64-1=63 } $$
б) \(\mathrm{C_n^1+6C_n^2+6C_n^3}\) $$ \mathrm{ C_n^1=n,\ \ C_n^2=\frac{n(n-1)}{2},\ \ C_n^3=\frac{n(n-1)(n-2)}{6} } $$ Получаем \begin{gather*} \mathrm{ C_n^1+6C_n^2+6C_n^3=n+6\cdot \frac{n(n-1)}{2}+6\cdot \frac{n(n-1)(n-2)}{6}=}\\ \mathrm{ =n(1+3(n-1)+(n-1)(n-2))=n(3n-2+n^2-3n+2)=n^3 } \end{gather*} Ответ: а) 63; б) n³.

Пример 5. Рассчитайте все \(\mathrm{C_{10}^k}\) по рекуррентной формуле \(\mathrm{C_{n}^k=\frac{n-k+1}{k}C_n^{k-1}}\).
Постройте график \(\mathrm{C_{10}^k(k)}\). Сделайте выводы.

Начальное значение \(\mathrm{C_{10}^0=1}\).

k \(\mathrm{C_{10}^k}\) 0 $$\mathrm{ C_{10}^0=1 }$$ 1 $$\mathrm{ C_{10}^1=\frac{10-1+1}{1}C_{10}^0=10 }$$ 2 $$\mathrm{ C_{10}^2=\frac{10-2+1}{2}C_{10}^1=45 }$$ 3 $$\mathrm{ C_{10}^3=\frac{10-3+1}{3}C_{10}^2=120 }$$ 4 $$\mathrm{ C_{10}^4=\frac{10-4+1}{4}C_{10}^3=210 }$$ 5 $$\mathrm{ C_{10}^4=\frac{10-5+1}{5}C_{10}^4=252 }$$ 6 $$\mathrm{ C_{10}^6=\frac{10-6+1}{6}C_{10}^5=210 }$$ 7 $$\mathrm{ C_{10}^7=\frac{10-7+1}{7}C_{10}^6=120 }$$ 8 $$\mathrm{ C_{10}^6=\frac{10-8+1}{8}C_{10}^7=45 }$$ 9 $$\mathrm{ C_{10}^9=\frac{10-9+1}{9}C_{10}^8=10 }$$ 10 $$\mathrm{ C_{10}^{10}=\frac{10-10+1}{10}C_{10}^9=1 }$$

На графике видно симметрию коэффициентов: \(\mathrm{C_{10}^k=C_{10}^{10-k}}\).
Т.к. n = 10 – чётное, максимальный коэффициент при \(\mathrm{k=\frac{n}{2}=5,\ \ C_{10}^5=252}\).
Можем также проверить свойство суммы: \(\mathrm{\sum_{k=0}^{10}C_{10}^k=1024=2^{10}}\).