Математика 9 класс 9-М-7

§3. Сочетания

В некоторых задачах при выборе kk элементов из nn не важен порядок их выбора – важно лишь множество выбранных элементов.

Определение

Всякий выбор неупорядоченных kk элементов из множества, состоящего из nn элементов, называется сочетанием из nn элементов по kk элементов. Количество сочетаний из nn элементов по kk обозначается через CnkC_n^k.

Символ CnkC_n^k читается, как «цэ из nn по kk» или «число сочетаний из nn по kk». Буква CC происходит от французского слова «Combinaison» – «сочетание».

Неупорядоченные kk элементов из множества, состоящего из nn элементов, соответствуют kk-элементному подмножеству выбранных элементов исходного nn-элементного множества. Поэтому количество сочетаний из nn элементов по kk можно трактовать как количество kk-элементных подмножеств nn-элементного множества.

Прежде, чем мы получим формулу для числа сочетаний в общем случае, выведем её в частном примере.

Пример 7

Сколькими способами можно разыграть среди `20` спортсменов три призовых места?

Решение

Этот пример очень похож на пример 4. Отличие заключается лишь в том, что здесь `3` выбранных спортсмена, занявшие призовые места, неупорядочены.

Вспомним правило произведения. Фраза «Если объект a1a_1 можно выбрать n1n_1 способами…» означает, что объекты выбираются упорядоченно, поэтому из правила произведения посчитать количество способов выбора трёх призеров из `20` участников нельзя.

Однако, можно упорядочить трёх выбранных спортсменов, разыграв среди них золотую, серебряную и бронзовую медали. И, зная количество способов разыграть между 20-ю спортсменами `3` призовых места, посчитать количество способов разыграть между этими спортсменами комплект медалей.

Действительно, пусть количество способов выбрать `3` призовых места из `20` участников равно mm. Разыграем среди этих призёров золотую, серебряную и бронзовую медали. Количество способов разыграть `3` медали среди трёх участников (количество перестановок из трёх элементов) равно 3!=63! = 6. Заметим, что в итоге среди `20` участников были разыграны золотая, серебряная и бронзовая медали.

С одной стороны, по правилу произведения количество способов разыграть медали среди `20` участников равняется m× 3!m \times  3!. С другой стороны, это количество уже было подсчитано ранее в примере 4, и оно равно

A203=20·19·18=6840A_{20}^3 = 20 \cdot 19 \cdot 18 = 6840.

Отсюда, m= A203/3!=(20·19·18)/6=1140m = A_{20}^3/3! = (20 \cdot 19 \cdot 18)/6 = 1140.

m=A2033!=1140m = \dfrac{A_{20}^3}{3!} = 1140.

ОТВЕТ

`1140`.

Для нахождения формулы CnkC_n^k в общем случае ещё раз воспользуемся приёмом, описанным в решении предыдущего примера. Рассмотрим все сочетания (неупорядоченные наборы) из nn элементов по kk элементов. Таких наборов будет CnkC_n^k. Чему равняется данное число, мы пока ещё не знаем, однако, если каждый набор из kk элементов упорядочить (k!k! способов), то получится упорядоченный набор kk элементов из nn элементов – размещение. Таким образом, по правилу произведения получаем, что

Cnk×k!=Ank,C_n^k \times k! = A_n^k,

откуда

Cnk=n(n-1)...(n-k+1)k!=n!k!(n-k)!C_n^k = \dfrac{n(n-1)\: ... \: (n-k+1)}{k!} = \dfrac{n!}{k!(n-k)!}.

Эта формула верна в том числе для k=0k = 0 и k=nk = n (напомним, 0!=10! = 1). Действительно, выбрать 0 элементов из nn (Cn0C_n^0) или выбрать сразу всё множество из nn элементов, не упорядочивая последние (CnnC_n^n), можно только одним способом, т. е.

Cn0=Cnn=n!0!n!=n!n!0!=1C_n^0 = C_n^n = \dfrac{n!}{0!n!}=\dfrac{n!}{n!0!} = 1.

Вид формулы CnkC_n^k и равенство Cn0 =CnnC_n^0 = C_n^n наталкивают на мысль, что Cn1 =Cnn1C_n^1 = C_n^{n−1}, Cn2=Cnn2C_n^2 = C_n^{n−2} и в общем случае Cnk =Cnn-kC_n^k = C_n^{n-k}. Это действительно так:

Cnn-k=n!(n-k)!(n-(n-k))!=n!k!(n-k)!=CnkC_n^{n-k} = \dfrac{n!}{(n-k)!(n-(n-k))! } = \dfrac{n!}{k!(n-k)!} = C_n^k.

Однако, можно доказать, что Cnn-k=CnkC_n^{n-k} = C_n^k, не выписывая формул. Достаточно понять, что эти формулы имеют одинаковый комбинаторный смысл. Действительно, выбор подмножества из kk элементов однозначно определяет выбор оставшегося подмножества из $$(n − k)$$ элементов. Также в примере 7 количество способов разыграть `3` призовых места среди `20` спортсменов равняется количеству способов отсеять `(20-3) = 17` оставшихся.

Перед решением примеров выпишем формулы для числа сочетаний при k=0,1,2,3k = 0,\: 1, \:2,\: 3 в явном виде:

$$C_n^0 = 1,\:\:\: C_n^1 = n,\:\:\: C_n^2 = \dfrac{n(n-1)}{2},\:\:\: C_n^3 = \dfrac{n(n-1)(n-23)}{6}$$.

Пример 8

Какое максимальное число точек пересечения может быть у nn различных прямых?

Решение

Заметим, что каждые `2` прямые дадут не более одной точки пересечения. Если никакие `2` прямые не параллельны и никакие `3` прямые не пересекаются в одной точке, то каждым `2` прямым будет соответствовать ровно одна точка пересечения, и количество таких точек равно числу способов выбора неупорядоченной пары из двух прямых, т. е. Cn2C_n^2.

ОТВЕТ

Cn2=n(n-1)2C_n^2 = \dfrac{n(n-1)}{2}.

Пример 9

Сколько различных слов можно получить, переставляя буквы в слове «математика».

Решение

Пусть количество таких слов равняется mm. Если бы все буквы были различны, то это количество равнялось бы `10!` в соответствии с числом перестановок. Но в нашем слове буквы «т», «м» встречаются `2` раза, а буква «а» – `3` раза.

Сделаем эти буквы различными, приписав одинаковым буквам нижние индексы. Для начала трём одинаковым буквам `«"a"»` припишем разные индексы (`«"а"_1»`, `«"а"_2»` и `«"а"_3»` соответственно) – число слов теперь будет равняться m×3!m \times 3!. Затем сделаем «разными» буквы «т» и «м».

Теперь, в слове «м1а1т1ем2а2т2ика3\text{м}_1\text{а}_1\text{т}_1\text{е}\text{м}_2\text{а}_2\text{т}_2\text{и}\text{к}\text{а}_3» все буквы действительно будут различны, и при перестановке букв получится m×3!×2!×2!=10!m \times 3! × 2! × 2! = 10! различных слов.

ОТВЕТ

10!3!2!2!=10!24=151200\dfrac{10!}{3!2!2!} = \dfrac{10!}{24} = 151200.

Пример 10

Сколькими способами можно расселить `12` студентов в трёхместные комнаты №1, №2, №3, №4 студенческого общежития?

Решение

Решим эту задачу двумя способами.

Первый способ.

Выберем трёх студентов для поселения в комнату №1. Количество способов такого выбора равняется C123C_{12}^3. Осталось `9` непоселённых студентов; троих из них поселим в комнату №2 C93C_9^3 способами. Ещё `3` из `6` студентов будут жить в комнате №3 C63C_6^3 способами, оставшиеся же студенты будут жить в комнате №4. По правилу произведения получаем число C123C93C63=369600C_{12}^3 C_9^3 C_6^3 = 369600.

Второй способ:

При поселении в комнаты раздадим студентам карточки с номерами их комнат. Далее поставим студентов в ряд (например, по алфавиту) и попросим их показать свои карточки. Таким образом, количество способов расселения студентов равно количеству 12-цифирных номеров, которые можно получить из карточек `«1»`, `«2»`, `«3»`, `«4»`, по три карточки каждого вида. Аналогично примеру `9`, получим ответ:

12!3!3!3!3!=369600\dfrac{12!}{3!3!3!3!} = 369600.

ОТВЕТ

C123C93C63=369600C_{12}^3 C_9^3 C_6^3 = 369600.

Вернёмся к количествам сочетаний и сформулируем их основные арифметические свойства.

свойства

1. Cnk=Cnn-kC_n^k = C_n^{n-k}, если 0kn0 \leq k \leq n;

2. Cn+1k+1=Cnk+1+CnkC_{n+1}^{k+1} = C_n^{k+1} + C_n^k, если 0k+1n0 \leq k+1 \leq n;

3. Cn0+Cn1+Cn2+...+Cnn=2nC_n^0 + C_n^1 + C_n^2 + \: ... \: + C_n^n = 2^n


Первое свойство уже было сформулировано и доказано ранее. К свойствам 2 и 3 мы перейдём, когда познакомимся со вторым основным правилом комбинаторики – правилом суммы.