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

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

Статья

Конспект

Задачи

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

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

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

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

Решение

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

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

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

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

Решение

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

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

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

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

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

В группе $G_1$ будут все способы осветить комнату одной зажженной свечой. Таких способа всего 4 — выбрать одну из четырех свечей и зажечь ее.
В группе $G_2$ все способы осветить команту двумя зажженными свечами. Количество способов зажечь две свечи из четырех можно найти прямым перебором. Всего их 6.
В группе $G_3$ все способы осветить команту тремя зажжеными свечами. Так же прямым перебором находим 4 варианта это сделать.
Наконец, в группе $G_4$ все способы осветить комнату всеми четырьмя зажжеными свечами. Такой способ только 1 — зажечь все свечи.

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

G_1 + G_2 + G_3 + G_4 = 4 + 6 + 4 + 1 = 15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Возникновение дубликатов при делении на группы.

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

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

Буквы на показ

Сколькими способами из слова «стройка» можно выбрать согласную или букву, стоящую на четном месте?

Решение

Разделим все способы выбора буквы разделим на две группы:

Группа «Согласные». В нее входят 4 буквы: «с», «т», «р» и «к»
Группа «Четные». В нее входят 3 буквы: «т», «о», «к»

Казалось бы, получили две группы вариантов. Осталось применить правило сложения и получить ответ:

4 + 3 = 7

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

4 + 3 - 2 = 5

Всего 5 способов выбрать из слова «стройка» согласную или четную букву.

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

Проверяйте пересечения!

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

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

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

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

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

Турист находится в городе 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!

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

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

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

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

Источники7

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

Комбинаторика

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 7-е издание, МЦНМО, 2019

Почти идеальная подача теории через жизненные примеры. Интересные задачи. Широчайший охват тем, в том числе и из высшей математики.

3. Команда космического корабля

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

Википедия

Свободная энциклопедия

Комбинаторные принципы

Brilliant

Образовательная платформа по математике и IT

Прекрасный сайт с наглядными пояснениями, хорошими примерами и упражнениями.

Rule of Sum