Правила комбинаторики

Правило суммы и правило произведения, дерево вариантов, факториал

Что изучает комбинаторика

Комбинаторика — раздел математики, изучающий способы подсчёта числа возможных комбинаций объектов, удовлетворяющих определённым условиям (без непосредственного перечисления всех этих комбинаций). Комбинаторные методы лежат в основе теории вероятностей: чтобы найти вероятность события, часто требуется подсчитать число благоприятных и общее число исходов, а для этого нужны именно комбинаторные формулы.

Правило суммы

Правило суммы: если объект A можно выбрать m способами, а объект B — n способами, причём эти способы взаимно исключают друг друга (выбор объекта A и выбор объекта B не могут произойти одновременно), то выбор «A или B» можно сделать m+n способами.

Пример. В классе 15 мальчиков и 12 девочек. Сколькими способами можно выбрать одного дежурного (любого пола)? Ответ: 15+12=27 способами, поскольку каждый ученик — либо мальчик, либо девочка, и эти варианты не пересекаются.

Правило произведения

Правило произведения: если объект A можно выбрать m способами, и после каждого такого выбора объект B можно выбрать n способами (независимо от того, какой конкретно вариант A был выбран), то пару «A и B» можно выбрать m·n способами. Это правило обобщается на любое число последовательных выборов: если этапов k, и на i-м этапе есть nᵢ вариантов, общее число комбинаций равно произведению n₁·n₂·…·n_k.

$N = n_{1} \cdot n_{2} \cdot \dots \cdot n_{k}$

Пример 1: применение правила произведения

Условие. Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры в числе не повторяются?

Решение. Первую цифру можно выбрать 5 способами, после этого вторую — из оставшихся 4 цифр, а третью — из оставшихся 3:

$N = 5 \cdot 4 \cdot 3 = 60$

Дерево вариантов

Для наглядного представления всех комбинаций, особенно в задачах с небольшим числом вариантов, используют дерево вариантов — граф, в котором каждая ветвь на определённом уровне соответствует одному из возможных выборов на очередном этапе, а путь от корня до листа — одной полной комбинации. Число листьев дерева равно общему числу комбинаций, что даёт наглядное обоснование правила произведения: на каждом уровне число ветвей умножается на число вариантов следующего этапа.

Пример 2: комбинирование правил суммы и произведения

Условие. В меню кафе — 4 вида супа, 6 видов горячего и 3 вида напитка. Клиент выбирает либо суп и горячее, либо горячее и напиток (по одному из каждой указанной категории). Сколько существует способов сделать заказ?

Решение. Способов «суп + горячее»: 4·6=24 (правило произведения). Способов «горячее + напиток»: 6·3=18. Эти два варианта заказа взаимно исключают друг друга (клиент выбирает один из двух вариантов формата заказа), поэтому применяем правило суммы:

$N = 24 + 18 = 42$

Факториал

Число способов расположить n различных объектов в ряд (упорядочить их все) находят по правилу произведения: первый объект можно выбрать n способами, второй — оставшимися (n−1) способами, и так далее до последнего, единственно возможного варианта. Произведение n·(n−1)·(n−2)·…·2·1 называют факториалом числа n и обозначают n!:

$n! = n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot 2 \cdot 1$

По определению полагают 0!=1 (это соглашение удобно для единообразия последующих формул комбинаторики). Факториал растёт чрезвычайно быстро: 5!=120, 10!=3628800, а уже 15! превышает триллион.

Пример 3: расположение объектов в ряд

Условие. Сколькими способами можно расставить на полке 6 различных книг?

Решение. Число способов равно 6!:

$6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$

Задачи с ограничениями

Многие комбинаторные задачи содержат дополнительные условия (например, два конкретных объекта должны стоять рядом, или, наоборот, не должны стоять рядом), для решения которых часто удобно «склеить» два объекта в один составной (если они должны быть рядом) или, наоборот, сначала посчитать общее число вариантов без ограничения, а затем вычесть число «запрещённых» вариантов.

Пример 4: задача с условием «рядом»

Условие. Сколькими способами можно расставить в ряд 5 различных книг так, чтобы две конкретные книги стояли рядом?

Решение. «Склеим» две нужные книги в один составной объект — тогда нужно расставить в ряд уже 4 объекта (составной объект и 3 оставшиеся книги), что даёт 4! способов. Но внутри составного объекта две книги можно расположить ещё 2 способами (местами поменять). По правилу произведения:

$N = 4! \cdot 2 = 24 \cdot 2 = 48$

Типичные ошибки

Наиболее частая ошибка — перепутать, когда следует применять правило суммы, а когда правило произведения: правило суммы используется, когда выбор совершается «или-или» (варианты взаимно исключают друг друга и не образуют последовательные этапы одного и того же процесса), а правило произведения — когда выбор совершается «и-и», то есть представляет собой последовательность независимых этапов одного процесса. Вторая распространённая ошибка — не учитывать (или, наоборот, ошибочно учитывать) условие неповторяемости объектов при выборе, когда оно есть или отсутствует в условии задачи.

Краткий словарь терминов

Правило суммы — число способов выбрать «A или B» равно сумме числа способов выбрать каждый из вариантов по отдельности, если варианты взаимно исключают друг друга.

Правило произведения — число способов последовательно выбрать несколько объектов равно произведению числа вариантов на каждом этапе.

Факториал — n! = n·(n−1)·…·2·1 — число способов упорядочить n различных объектов; 0!=1 по определению.

Дерево вариантов — графическое представление всех возможных комбинаций в виде ветвящейся структуры.

Заключение

Два базовых правила комбинаторики — правило суммы и правило произведения — лежат в основе всех более сложных комбинаторных формул, изучаемых в следующей статье (перестановки, размещения, сочетания). Умение правильно распознать, какое из правил применимо в конкретной задаче, а также аккуратный учёт дополнительных условий и ограничений — ключевые навыки для успешного решения комбинаторных задач.