Конспект урока: А.С. Пушкин. «Няне». Пролог к «Руслану и Людмиле»

Сочетания и их свойства

План урока

Сочетания из $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$ элементов в каждом $(n \leq m)$ называются такие соединения, каждое из которых содержит $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

Вычислить $С_{16}^{14} + С_{16}^{15}$ .

Решение

Применим свойство 2, получим $С_{16}^{14} + С_{16}^{15} = С_{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 можно $С_{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$ .

Сочетания и их свойства

План урока

Сочетания из $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$ элементов $C_{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

Вычислить $С_{16}^{14} + С_{16}^{15}$ .

Решение

Применим свойство 2, получим $С_{16}^{14} + С_{16}^{15} = С_{17}^{15}$ , что по формуле (1) будет равно

$\frac{17!}{15! \times 2!} = \frac{16 \times 17}{1 \times 2} = 8 \times 17 = 136$ .

Ответ: $136$ .

Пример 2

Решение

Ответ: $76 440$ способов.

Пример 3

Решение

$C_{9}^{2} \times C_{9}^{3} = \frac{9! \times 9!}{2! \times 7! \times 3! \times 6!} = 3 024$ .

Ответ: $3 024$ способа.

Упражнение

а) директор фирмы должен ехать в командировку;

б) директор фирмы должен остаться?

Контрольные вопросы

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$ .

Конспект урока: Сочетания и их свойства

Элементы комбинаторики и теории вероятностей