В основе решения большинства комбинаторных задач лежат два правила: правило суммы и правило произведения.
Туриста заинтересовали 5 маршрутов в Карелии и 7 маршрутов на Кавказе. Выясним, сколькими способами он может организовать свой отпуск, имея время только на один маршрут. Поскольку всего имеется $5+7=12$ различных маршрутов, то один из них можно выбрать 12 способами.
Правило суммы можно обобщить для трёх и более множеств. Например, если множества $A$, $B$ и $C$ состоят соответственно из $m$, $k$ и $n$ элементов, причём ни у каких двух из этих множеств нет общих элементов, то выбор «$a$ или $b$ или $c$» можно осуществить $m+k+n$ способами. Подвигай ползунки справа и посмотри, как меняется общее число маршрутов.
Обратимся снова к примеру с выбором маршрутов. Если у туриста есть время на два маршрута и он хочет побывать сначала в Карелии, а затем на Кавказе, то он может организовать свой отдых 35 способами. Действительно, если выбрать один маршрут в Карелии, то парой к нему может быть любой из семи кавказских маршрутов. Так как маршрутов в Карелии пять, то количество пар (маршрут в Карелии; маршрут на Кавказе) равно $7\cdot5=35$.
Правило произведения также естественно обобщается: если элемент $a$ можно выбрать $m$ способами, после каждого такого выбора элемент $b$ можно выбрать $k$ способами и после того, как выбраны элементы $a$ и $b$, элемент $c$ можно выбрать $n$ способами, то выбор «$a$ и $b$ и $c$» можно осуществить $mkn$ способами.
Из класса, в котором учатся 28 человек, надо выбрать трёх дежурных — по одному на каждый из трёх этажей школы. Каким количеством способов это можно сделать?
Ответ: 19 656 способов.
Сколько натуральных делителей имеет число 2000?
Имеем: $2000=2^4\cdot5^3$. Тогда любой делитель данного числа имеет вид $2^m\cdot5^k$, где $m$ и $k$ — целые числа, удовлетворяющие условиям $0\le m\le4$, $0\le k\le3$. Количество делителей данного числа равно количеству наборов, которые можно составить из чисел $m$ и $k$ в указанном порядке.
Число $m$ можно выбрать 5 способами, число $k$ — 4 способами. Следовательно, по правилу произведения такой набор можно выбрать $5\cdot4=20$ способами. Поэтому число 2000 имеет 20 делителей.
Для защиты информации на компьютере используют пароль — последовательность букв и цифр длиной от трёх до пяти символов (пароль может содержать несколько одинаковых символов). Сколько различных паролей можно придумать, используя 26 строчных букв английского алфавита и 10 цифр?
В качестве первого символа можно выбрать любую букву или любую цифру — получаем 36 вариантов. Аналогично для второго и третьего символов существует по 36 вариантов выбора. Применяя правило произведения, получаем, что существует $36^3$ разных паролей длиной в три символа. Аналогично паролей из четырёх символов — $36^4$, а из пяти символов — $36^5$.
Применяя правило суммы, получаем, что общее количество паролей равно $36^3+36^4+36^5$.