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

Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых, соответственно, правилами суммы и произведения.

Правило суммы выражает вполне очевидный факт: если и – два непересекающихся конечных множества, то число элементов, содержащихся в объединении этих множеств, равно сумме чисел элементов в каждом из них.

Если обозначить число элементов конечного множества через , то правило суммы запишется следующим образом: , если и не имеют общих элементов.

Обычно правило суммы формулируют следующим образом: если элемент может быть выбран способами, а элемент – способами, то один из этих элементов можно выбрать способами.

Обобщение правила суммы на любое число множеств не менее очевидно: если – попарно непересекающиеся конечные множества, то .

Задачи, которые можно решить применением одного лишь правила суммы, тривиальны. Для решения более сложных задач используется также и правило произведения.

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

Более корректно правило произведения можно сформулировать в виде теоремы.

Теорема. Пусть имеется , , групп элементов, причем –я группа содержит элементов, . Выберем из каждой группы по одному элементу. Тогда общее число способов, которыми можно произвести такой выбор, равняется

.

Доказательство. Теорема доказывается методом индукции.

Пусть . Обозначим через различные значения элемента , а через – различные значения элемента . Если выбрано значение элемента , то можно составить различные пары, содержащие этот элемент. Это справедливо и для любого другого значения элемента . Таким образом, всего можно составить различные пары, т.е. для правило выполняется.

Предположим, что оно выполняется для групп из элементов. Тогда любую группу ( ) можно рассматривать как пару элементов . Первый элемент этой пары, по предположению индукции, может быть выбран способами; при любом из них элемент может быть выбран способами. Таким образом, число различных групп ( ) будет равно .