Правило сложения

Базовые примеры

Во время решения комбинаторных задач не раз и не два будет вставать вопрос: как определить количество способов взять один объект из нескольких групп объектов? Отличной иллюстрацией такого вопроса служит следующий пример:

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

Группируй и складывай

В базовых примерах нам уже дали разбитые на группы объекты и оставалось только их сложить. Сейчас рассмотрим более сложный пример, в котором группы придется выделять нам самим.

Имеется канделябр с четырьмя разными свечами. Нам нужно осветить комнату, то есть зажечь хотя-бы одну свечу (можно и больше). Сколько есть способов осветить команту?

Разделим все способы осветить комнату на группы по количеству зажженных свечей:

• В группе $G_1$ будут все способы осветить комнату одной зажженной свечой. Таких способа всего 4 — выбрать одну из четырех свечей и зажечь ее.

• В группе $G_2$ все способы осветить команту двумя зажженными свечами. Количество способов зажечь две свечи из четырех можно найти прямым перебором. Всего их 6.

• В группе $G_3$ все способы осветить команту тремя зажжеными свечами. Так же прямым перебором находим 4 варианта это сделать.

• Наконец, в группе $G_4$ все способы осветить комнату всеми четырьмя зажжеными свечами. Такой способ только 1 — зажечь все свечи.

    graph TD
        root{{Способы освещения команты}} -->|$1$ свечой| g1["$G_1 = 4$"]:::featured
        root -->|$2$ свечами| g2["$G_2 = 6$"]:::featured
        root -->|$3$ свечами| g3["$G_3 = 4$"]:::featured
        root -->|$4$ свечами| g4["$G_4 = 1$"]:::featured

Итак, мы все способы осветить комнату разбили на группы по количеству зажженных свечей. По отдельности нашли количество способов в каждой группе. Чтобы найти ответ на задачу, осталось только сложить способы во всех группах:

Всего 15 способов осветить команту при помощи канделябра с четырьмя свечами!

Правило сложения

Мы рассмотрели достаточно примеров, чтобы обнаружить закономерность. Отвлекаясь от смысла, мы все возможные варианты разбиваем удобным нам образом на группы. А потом просто складываем количество способов в этих группах. Так и получаем искомое количество способов!

Принцип «группируй и складывай» лежит в основе всей комбинаторики. Он простой, понятный и встречается настолько часто, что математики дали ему отдельное название:

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

Так как комбинаторика тесно связана с теорией множеств, то группы из правила сложения очень часто называют классами. В рамках данного учебника никакой разницы нет. Используйте то название, которое вам больше нравится.

Проблема дубликатов

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

• Не может быть одновременно черного и белого платья.

• Не может яблоко быть апельсином или бананом.

• Не может способ осветить комнату 2-мя свечами равняться способу осветить ее 3-мя свечами.

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

Нас интересуют два класса объектов: «Кубики» и «Синие игрушки». Посчитаем, сколько объектов лежат в каждой из этих групп. Кубик можно выбрать 6 способами. Синюю игрушку можно выбрать 8 способами (3 кубика и 5 шариков). Выходит, выбор «Кубик или синяя игрушка» можно сделать 6 + 8 = 14 способами! Элементарно, Ватсон!

Но это неправильный ответ. Дело в том, что группы «Кубик» и «Синяя игрушка» пересекаются друг с другом, потому что в магазине есть 3 игрушки, которые одновременно являются и кубиком, и синей игрушкой. Три этих кубика есть в группе «Кубик», но эти же три кубика есть и в группе «Синяя игрушка». Когда мы сложили эти две группы, мы лишний раз учли эти три кубика.

Для получения правильного ответа достаточно вычесть эти три кубика, которые мы учли лишний раз: 6 + 8 - 3 = 11. Всего 11 способов выбрать «Кубик или синюю игрушку».

Вот еще один наглядный пример задачи, в которой возникает проблема дубликатов:

В более сложных задачах вам часто придется самостоятельно выделять классы для правила сложения и следить за тем, чтобы они не пересекались! Не забывайте выполнять проверку на пересечения!

Цепочка действий

Не всегда правило сложения можно применить так легко и просто, как в уже рассмотренных примерах. Иногда нужно догадаться, как его надо использовать. Если все было бы тривиально, математика была бы слишком скучной, не так ли?

Вот пример такой «нестандартной» задачи:

Точечное путешествие

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

Решение от «конца к началу»

Так напрямую перебрать все варианты мы не можем, надо придумать что-то еще. Попробуем вести рассуждения не с начальной точки A, а с точки назначения — E.

Попасть в E можно только из точек B, C и D, причем только одним способом (одной дорогой) из каждой. Значит, каждый способ попасть, например, в B автоматом является способом попасть и в E! Если в B можно попасть, условно, 5-ю способами, то это сразу дает 5 способов попасть и в E.

Такие же рассуждения справедливы и для точек C и D. Получается, все маршруты в E можно разбить на 3 класса. В первом классе предпоследней точкой будет B, во втором C, а в третьем D. Плюс еще и в том, что эти классы не пересекаются, ведь маршруты в них уникальные, со своей предпоследней точкой.

Итак, вопрос о попадании в точку E сводится к вопросу о всех способах попасть в «точку B ИЛИ точку C ИЛИ точку D». А на такие вопросы можно ответить с помощью правила суммы! Введем обозначение $S_E$, которое обозначает количество способов попасть в точку E. Тогда:

$$S_E = S_B + S_C + S_D$$

Для точки D можно применить те же рассуждения, что и для точки E. Тогда получится, что $S_D = S_B + S_C$. Итоговая формула для E будет выглядеть так:

$$S_E = S_B + S_C + \underbrace{S_B + S_C}_{S_D}$$

Попасть из A в B можно одним способом, то есть $S_B = 1$. Попасть из A в C можно двумя способами (напрямую и через B), то есть $S_C = 2$. Тогда:

$$S_E = 1 + 2 + 1 + 2 = 6$$

Всего 6 разных маршрутов из A в E!

Решение от «начала к концу»

В решении «от конца к началу» мы показали, что количество способов попасть в очередную точку равно сумме количеств способов попасть в предыдущие точки. Этот важный вывод позволяет просто двигаться от начала к концу и проставлять рядом с каждой точкой количество способов в нее попасть:

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

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