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

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

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

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

Вечернее платье

Настя собирается в театр и пытается выбрать подходящее платье. У нее есть 3 черных и 2 белых платья. Сколько у нее вариантов выбрать одно платье для театра?

Решение

Все платья разбиты на 2 группы или класса: черные и белые. У Насти есть 3 способа выбрать одно черное платье (взять одно из трех) и 2 способа выбрать одно белое платье (взять одно из двух). Всего получается 3 + 2 = 5 способов выбрать платье для театра, то есть совершить выбор «черное или белое платье».

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

Фрукты на закуску

На столе лежит 5 яблок, 3 апельсина и 8 бананов.
Сколько существует способов выбрать хоть какой-то из этих фруктов?

Решение

У нас есть три группы фруктов: яблоки, апесльины и бананы. Есть 5 способов выбрать себе яблоко, 3 способа выбрать апельсин и 8 вариантов выбрать банан. Тогда суммарно имеем 5+3+8 = 16 вариантов выбрать хоть какой-то фрукт. Еще можно сказать, что у нас есть 16 вариантов выбрать «Яблоко или Апельсин или Банан».

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

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

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

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

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

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

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

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

    graph TD
        root{{Способы освещения команты}} -->|11 свечой| g1["G1=4G_1 = 4"]:::featured
        root -->|22 свечами| g2["G2=6G_2 = 6"]:::featured
        root -->|33 свечами| g3["G3=4G_3 = 4"]:::featured
        root -->|44 свечами| g4["G4=1G_4 = 1"]:::featured

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

G1+G2+G3+G4=4+6+4+1=15G_1 + G_2 + G_3 + G_4 = 4 + 6 + 4 + 1 = 15

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

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

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

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

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

Если объект из группы A можно выбрать a способами, а объект из группы B можно выбрать b способами, то выбрать хоть какой-то объект из этих групп можно a+ba+b способами.

Другими словами, выбор «A или B» можно сделать a+ba+b способами.

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

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

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

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

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

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

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

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

Обманчивые детские игрушки

В магазине детских игрушек есть 6 кубиков, 3 из которых синего цвета и 5 шариков синего цвета. Матвей хочет себе либо кубик, либо игрушку любой формы, но обязательно синюю. Сколькими способами его мама может совершить покупку?

Нас интересуют два класса объектов: «Кубики» и «Синие игрушки». Посчитаем, сколько объектов лежат в каждой из этих групп. Кубик можно выбрать 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». А на такие вопросы можно ответить с помощью правила суммы! Введем обозначение SES_E, которое обозначает количество способов попасть в точку E. Тогда:

SE=SB+SC+SDS_E = S_B + S_C + S_D

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

SE=SB+SC+SB+SCSDS_E = S_B + S_C + \underbrace{S_B + S_C}_{S_D}

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

SE=1+2+1+2=6S_E = 1 + 2 + 1 + 2 = 6

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

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

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

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

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

Превью