- Сочетания из $m$ элементов по $n$ элементов;
- Свойства сочетаний;
- Применение формулы числа сочетаний при решении задач.
- Знать, что такое сочетания из $m$ элементов по $n$ элементов;
- Знать вывод формулы для числа сочетаний из $m$ элементов по $n$ элементов;
- Знать свойства сочетаний;
- Уметь применять формулу для числа сочетаний из $m$ элементов по $n$элементов при решении задач.
- Формула перестановки из $n$ элементов.
- Формула числа размещений из $m$ элементов по $n$ элементов.
- Вычислить $\frac{A_{10}^{6} - A_{10}^{5}}{A_{10}^{5} - A_{10}^{4}}$.
- Сколькими способами можно составить трехцветный полосатый флаг из горизонтальных полос, если есть материал пяти разных цветов?
В комбинаторике термином «соединения» называют три вида комбинаций, которые составляются из некоторого числа различных элементов, принадлежащих одному и тому же множеству. Мы уже познакомились с двумя видами соединений — перестановками и размещениями. В них важен порядок размещения элементов. Если же порядок не важен, то мы будем говорить о сочетаниях.
Сочетаниями из $m$ элементов по $n$ элементов в каждом $\left(n \leq m\right)$ называются такие соединения, каждое из которых содержит $n$ элементов, взятых из данных $m$ различных элементов, и которые отличаются одно от другого по крайней мере одним элементом.
Обозначается число всевозможных сочетаний из $m$ элементов по $n$ элементов $C_{m}^{n}$ и читают «цэ из эм по эн».
Выведем формулу для вычисления числа всевозможных сочетаний из $m$элементов по $n$ элементов, т. е. для $C_{m}^{n}$, $n \leq m$.
Пусть есть $m$ различных элементов. Из них образуем соединения из $n$ элементов без учета порядка их расположения. Из каждого такого соединения с помощью перестановки его элементов можно получить $P_{n} = n !$ соединений, которые отличаются друг от друга только порядком расположения элементов. Таким образом получим все размещения из $m$ элементов по $n$ элементов, число которых равно $A_{m}^{n}$. Таких соединений по правилу произведения будет $C_{m}^{n} \times P_{n}$, т. е. $C_{m}^{n} \times P_{n} = A_{m}^{n}$, откуда $C_{m}^{n} = \frac{A_{m}^{n}}{P_{n}}$. Зная, что $A_{m}^{n} = \frac{m !}{( m - n ) !}$, $P_{n} = n !$, получим $C_{m}^{n} = \frac{m !}{n ! ( m - n ) !}$.
Сочетания из $m$ элементов по $n$ элементов $( n \leq m )$ вычисляют по формулам
$C_{m}^{n} = \frac{m !}{n ! ( m - n ) !}$ (1)
$C_{m}^{n} = \frac{A_{m}^{n}}{P_{n}}$ (2)
Свойства сочетаний
1. $C_{m}^{n} = C_{m}^{m - n}$
Доказательство.
Применим формулу (1) к левой и правой частям выражения
$C_{m}^{n} = \frac{m !}{n ! ( m - n ) !}$,
$C_{m}^{m - n} = \frac{m !}{( m - m + n ) ! ( m - n ) !} = \frac{m !}{n ! ( m - n ) !}$.
Таким образом $C_{m}^{n} = C_{m}^{m - n}$, что и требовалось доказать.
2. $C_{m}^{n} + C_{m}^{n + 1} = C_{m + 1}^{n + 1}$ (рекуррентное свойство).
Доказательство.
К левой части равенства применим формулу (2):
$C_{m}^{n} + C_{m}^{n + 1} = \frac{A_{m}^{n}}{P_{n}} + \frac{A_{m}^{n + 1}}{P_{n + 1}} = \frac{m ( m - 1 ) . . . ( m - ( n - 1 ) )}{n !} + \frac{m ( m - 1 ) . . . ( m - ( n - 1 ) ) ( m - n )}{( n + 1 ) !} =$
$= \frac{m ( m - 1 ) . . . ( m - ( n - 1 ) ) ( n + 1 ) + m ( m - 1 ) . . . ( m - ( n - 1 ) ) ( m - n )}{( n + 1 ) !} =$
$= \frac{m ( m - 1 ) . . . ( m - ( n - 1 ) ) ( n + 1 + m - n )}{( n + 1 ) !} = \frac{( m + 1 ) m ( m - 1 ) . . . ( m - ( n - 1 ) )}{( n + 1 ) !} = \frac{A_{m + 1}^{n + 1}}{P_{n + 1}} = C_{m + 1}^{n + 1}$ .
Пример 1
Вычислить $C_{16}^{14} + C_{16}^{15}$.
Решение
Применим свойство 2, получим $C_{16}^{14} + C_{16}^{15} = C_{17}^{15}$, что по формуле (1) будет равно
$\frac{17 !}{15 ! \times 2 !} = \frac{16 \times 17}{1 \times 2} = 8 \times 17 = 136$.
Ответ: $136$.
Пример 2
В классе учатся 15 мальчиков и 8 девочек. Для дежурства по школе нужно выделить четверых мальчиков и трех девочек. Сколькими способами это можно сделать?
Решение
Выбрать четыре мальчика из 15 можно $C_{15}^{4}$ способами, трех девочек из 8 — $C_{8}^{3}$ способами. Так как при каждом выборе мальчиков можно $C_{8}^{3}$ способами выбрать девочек, то выбрать четверых мальчиков и трех девочек можно $C_{15}^{4} \times C_{8}^{3}$ способами.
$C_{15}^{4} \times C_{8}^{3} = \frac{15 !}{4 ! \times 11 !} \times \frac{8 !}{3 ! \times 5 !} = \frac{12 \times 13 \times 14 \times 15 \times 6 \times 7 \times 8}{1 \times 2 \times 3 \times 4 \times 1 \times 2 \times 3} = 76 440$.
Ответ: $76 440$ способов.
Пример 3
Из колоды, содержащей 36 карт, выбирают 2 карты червовой масти и 3 карты пиковой масти. Сколькими способами можно это сделать?
Решение
В колоде из 36 карт будет по 9 карт разных мастей. Поэтому выбрать 2 карты червовой масти из 9 можно $C_{9}^{2}$ способами, а 3 карты пиковой масти из 9 можно $C_{9}^{3}$ способами. Тогда сделать необходимый выбор можно $C_{9}^{2} \times C_{9}^{3}$ способами.
$C_{9}^{2} \times C_{9}^{3} = \frac{9 ! \times 9 !}{2 ! \times 7 ! \times 3 ! \times 6 !} = 3 024$.
Ответ: $3 024$ способа.
Упражнение
1. В магазине есть шоколадки 6 видов по одной цене. У Маши денег хватит только на 4 шоколадки. Сколькими способами Маша может купить 4 шоколадки разных видов?
2. В вазе лежат 15 конфет, 9 из которых шоколадные, а остальные карамель. Сколькими способами можно выбрать 5 шоколадных и 2 карамельных конфеты?
3. В классе 30 человек, из них 4 отличника. Сколькими способами можно разбить класс на два класса по 15 человек, чтобы количество отличников в каждом из них было одинаковым?
4. В фирме работает директор и 10 сотрудников. Надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если:
а) директор фирмы должен ехать в командировку;
б) директор фирмы должен остаться?
Контрольные вопросы
1. Какое число больше $A_{8}^{3}$ или $C_{8}^{4}$?
2. Сформулируйте определение числа сочетаний из $m$ элементов по $n$ элементов.
3. Запишите формулу для вычисления числа сочетаний из $m$ элементов по $n$ элементов.
Упражнение
1. $15$.
2. $1 890$.
3.$C_{4}^{2} \times C_{26}^{13}$.
4. а) $210$. б) $252$.
