Область математики, которая занимается подсчётом комбинаций, образованных по определённому правилу из элементов конечного множества, называют комбинаторикой. В основе решения большинства комбинаторных задач лежат два правила.
Туриста заинтересовали 5 маршрутов в Карелии и 7 маршрутов на Кавказе. Если у него есть время на один маршрут, то выбрать его можно 5 + 7 = 12 способами.
Правило суммы. Если множество A состоит из m элементов, а множество B — из k элементов, причём эти множества не имеют общих элементов, то выбор «a или b», где a ∈ A, b ∈ B, можно осуществить m + k способами.
Если у туриста есть время на два маршрута и он хочет побывать сначала в Карелии, а затем на Кавказе, то к каждому из пяти карельских маршрутов парой может быть любой из семи кавказских. Всего 7 · 5 = 35 способов.
Правило произведения. Если элемент a можно выбрать m способами и после каждого такого выбора элемент b можно выбрать k способами, то выбор «a и b» в указанном порядке можно осуществить mk способами.
Оба правила обобщаются на три и более множества.
Пример 1. Из класса, в котором учатся 28 человек, надо выбрать трёх дежурных — по одному на каждый из трёх этажей школы. Дежурного по первому этажу можно выбрать 28 способами, по второму — 27, по третьему — 26. Всего 28 · 27 · 26 = 19 656 способов.
Пример 2. Сколько натуральных делителей имеет число 2000? Имеем 2000 = 2⁴ · 5³. Любой делитель имеет вид 2^m · 5^k, где 0 ≤ m ≤ 4, 0 ≤ k ≤ 3. Число m можно выбрать 5 способами, число k — 4 способами. Значит, делителей 5 · 4 = 20.
Пример 3. Пароль — последовательность букв и цифр длиной от трёх до пяти символов, символы могут повторяться. Сколько разных паролей можно придумать из 26 букв и 10 цифр? Паролей из трёх символов 36³, из четырёх — 36⁴, из пяти — 36⁵. По правилу суммы всего 36³ + 36⁴ + 36⁵ паролей.