Комбинаторика: перестановки, размещения, сочетания
Теория
Правило произведения. Если первый выбор можно сделать $m$ способами, а после него второй выбор $n$ способами, то оба выбора вместе можно сделать $m\cdot n$ способами. Пример: из 3 рубашек и 2 пар брюк получается $3\cdot 2=6$ комплектов.
Перестановки. Число способов расставить $n$ разных предметов в ряд равно$$n!=1\cdot 2\cdot 3\cdot\ldots\cdot n.$$Пример: 4 книги на полке можно расставить $4!=24$ способами. По определению $0!=1$.
Размещения. Из $n$ разных предметов выбирают $k$ и ставят их по порядку. Число способов$$A_n^k=n\cdot(n-1)\cdot\ldots\cdot(n-k+1),$$всего $k$ множителей. Пример: золото, серебро и бронзу среди 10 бегунов можно распределить $A_{10}^3=10\cdot 9\cdot 8=720$ способами.
Сочетания. Если порядок выбранных предметов не важен, число способов равно$$C_n^k=\frac{A_n^k}{k!}=\frac{n!}{k!\,(n-k)!}.$$Пример: двух дежурных из 5 учеников можно выбрать $C_5^2=\dfrac{5\cdot 4}{2}=10$ способами.
Полезные равенства:$$C_n^0=C_n^n=1,\quad C_n^1=n,\quad C_n^k=C_n^{n-k}.$$Пример: $C_{20}^{18}=C_{20}^2=\dfrac{20\cdot 19}{2}=190$.
Как выбрать формулу. Если места или роли разные, порядок важен, берём размещения. Если важен только состав группы, берём сочетания. Когда выбор идёт из разных групп, числа способов перемножаем. Пример: 2 мальчиков из 5 и 1 девочку из 4 можно выбрать $C_5^2\cdot 4=40$ способами.
Разобранный пример
В классе 6 мальчиков и 5 девочек. Для концерта нужно выбрать 3 мальчиков и 2 девочек. Сколькими способами это можно сделать?
1) Порядок внутри группы не важен, поэтому считаем сочетания.
2) Мальчиков выбираем$$C_6^3=\frac{6\cdot 5\cdot 4}{1\cdot 2\cdot 3}=20$$способами.
3) Девочек выбираем$$C_5^2=\frac{5\cdot 4}{2}=10$$способами.
4) По правилу произведения:$$20\cdot 10=200.$$
Ответ: 200.
Тренировка
Сколькими способами можно рассадить 5 гостей на 5 стульев, стоящих в ряд?
В столовой есть 4 первых блюда и 6 вторых. Сколько разных обедов из одного первого и одного второго блюда можно составить?
В футбольном турнире 10 команд. Каждая команда сыграла с каждой по одному матчу. Сколько всего матчей было сыграно?
В классе 12 учеников. Нужно выбрать старосту, его заместителя и казначея. Сколькими способами это можно сделать?
Сколько чётных четырёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры в числе не повторяются?
Из 10 учеников нужно выбрать 3 человек на олимпиаду. Азиз и Бобур не должны попасть в тройку вместе. Сколькими способами можно выбрать тройку?