Анна Малкова
Теория вероятностей дает ответ на вопрос о том, с какой вероятностью произойдет то или иное событие.
Комбинаторика дает ответ на вопрос: «Сколькими способами можно что-либо сделать?»
Основные понятия комбинаторики: перестановки, размещения, сочетания. Но начнем мы не с формул, а с простых примеров. А к формулам постепенно придем.
1. В отряде космонавтов 7 человек одинаковой квалификации. Сколькими способами можно выбрать из них 2 космонавтов для экспедиции к далеким планетам?
Решение:
Задача на перебор вариантов. Присвоим космонавтам номера, от 1 до 7. Выпишем пары участников по возрастанию:
|
12, 13, 14, 15… 17 23, 24, 25… 27 … 56, 57 67
|
Очевидно, что пара 12 – то же самое, что пара 21, те же первый и второй космонавты.
В математике такая пара называется неупорядоченной, то есть порядок элементов в ней не важен.
Всего 21 способ.
Ответ: 21
2. В отряде космонавтов 7 человек одинаковой квалификации. Сколькими способами можно выбрать из них 2 космонавтов: Командира корабля и Бортинженера для экспедиции к далеким планетам?
Решение:
Очевидно, в 2 раза больше способов, чем в предыдущей задаче. В каждой паре есть 2 способа выбрать Командира и Бортинженера.
Такие пары, где важен порядок элементов, называются упорядоченными.
Можно рассуждать и по-другому: Командира можно выбрать 7 способами, Бортинженера 6 способами, всего \(6\cdot 7 = 42\) способа.
Ответ: 42
3. В отряде космонавтов 7 человек одинаковой квалификации. Сколькими способами можно выбрать из них 3 космонавтов: Командира корабля, Бортинженера и Исследователя для экспедиции к далеким планетам?
Решение:
«Одинаковой квалификации» - значит, каждый может быть или Командиром, или Бортинженером, или Исследователем.
Рассуждаем аналогично. Командира можем выбрать 7 способами, Бортинженера – 6 способами, Исследователя – 5 способами.
Всего \(7\cdot 6\cdot5 = 210\) способов.
Можно сказать, что это количество упорядоченных 3-элементных подмножеств из 7-элементного множества.
Ответ: 210
Интересно, сколькими способами можно выбрать 4 элемента из 7? Например, из того же отряда космонавтов – выбрать Командира корабля, Бортинженера, Исследователя и Навигатора?
\(7\cdot 6 \cdot 5 \cdot 4\) способа.
А сколькими способами можно выбрать 5 элементов из 7 (тех же и Астробиолога)?
\(7 \cdot 6\cdot 5 \cdot 4\cdot 3\) способа.
Эти рассуждения нам пригодятся для введения понятий «размещения» и «сочетания».
Факториал
n! (читается: эн факториал) – это произведение натуральных чисел от 1 до n включительно. Например,
\(6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\).
По определению, \(0! = 1\).
Перестановки
4. В вертолете 7 мест для пассажиров. Сколькими способами 7 пассажиров могут занять эти места?
Решение:
Рассуждаем так же, как в задачах про космонавтов.
Первый пассажир может занять любое из 7 мест. Второй – любое из 6 оставшихся. Третий – любое из 5, четвертый – любое из 4… И наконец, последний пассажир занимает оставшееся место, для него всего один вариант.
Значит, количество способов равно \(7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 7! = 5040\) способов.
Это число перестановок из 7 элементов.
Число перестановок из n элементов обозначается \(P_n\).
\(P_n=n!\)
5. Сколькими способами можно составить список из 25 учеников класса, среди которых нет однофамильцев?
Решение:
Рассуждаем так же, как в предыдущей задаче. На первое место можно поместить любого из 25, это 25 способов. На второе – любого из 24 оставшихся, на третье – любого из 23…
Всего получится \(25! = 15 511 210 043330 985 984 000 000\) способов.
Ответ: \(25! = 15 511 210 043330 985 984 000 000\) способов.
6. Сколько различных паролей можно составить из 10 цифр при условии, что цифры в пароле не повторяются?
Ответ: \(10! = 3628800\) способов.
Размещения
Вернемся к задаче про космонавтов.
Выбирая четырех космонавтов из семи, мы рассуждаем так.
Первый: 7 способов,
Второй: 6 способов,
Третий: 5 способов,
Четвертый: 4 способа.
И получили, что количество способов выбрать 4 упорядоченных элемента из 7
равно \( 7 \cdot 6 \cdot 5 \cdot 4\).
Можно сказать, что мы разделили 7! на 3! и получили это количество способов.
\(7 \cdot 6 \cdot 5 \cdot 4 = \frac{7!}{3!}=\frac{7!}{(7-4)!}\) способов.
Это число размещений из 7 элементов по 4 элемента.
Пусть имеется множество, содержащее n элементов. Произвольный упорядоченный набор, составленный из \( k\) различных элементов данного множества, называется размещением из n элементов по \( k\) элементов.
\(A_{n}^{k}=\frac{n!}{(n-k)!} \)
Также можно записать: \( A_{n}^{k}=n\cdot (n-1)(n-2)...\cdot (n-k+1).\)
А число размещений из \(n \) элементов по \(n \) – это число перестановок из \(n \) элементов.
7. В 11-м классе изучается 12 различных предметов. Сколькими способами можно составить расписание на пятницу, если этот день должно быть 8 различных уроков?
Решение:
Число таких способов равно числу размещений из 12 по 8.
\(A_{12}^{8}=\frac{12!}{(12-8)!}==\frac{12!}{4!} \) способов.
В данном случае важен порядок уроков.
Сочетания
8. У Андрея 12 учебников по разным предметам. В пятницу у Андрея 8 различных уроков, и для каждого нужен учебник. Сколько существует способов принести в школу 8 из 12 учебников?
Решение:
В этом случае не важно, в каком порядке учебники лежат в портфеле. Количество способов станет в 8! раз меньше. В этом случае мы говорим о неупорядоченных наборах элементов. Количество таких неупорядоченных наборов по 8 элементов, выбранных из 12-элементного множества, называется числом сочетаний из 12 по 8.
Произвольный неупорядоченный набор, составленный из \(k\) различных элементов данного множества, называется сочетанием из \(n\) элементов по \(k\) элементов.
Формула для числа сочетаний из \(n\) по \(k\):
\(С_{n}^{k}=\frac{n!}{k!(n-k)!} \).
Вернемся к первой задаче про космонавтов.
В отряде космонавтов 7 человек одинаковой квалификации. Сколькими способами можно выбрать из них 2 космонавтов для экспедиции к далеким планетам?
Теперь мы можем решить ее без всякого перебора вариантов. Количество способов здесь – это число сочетаний из 7 по 2.
\(С_{n}^{k}=\frac{7!}{2!(7-2)!}= \frac{7!}{2!(5)!}=\frac{7\cdot 6\cdot5\cdot4\cdot3\cdot2\cdot1}{2\cdot1\cdot5\cdot4\cdot3\cdot2\cdot1}=\frac{7\cdot 6}{2}=21\)
Ответ: 21
