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

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

Формулировка и математическая запись

В наиболее общей форме правило суммы формулируется для конечных множеств. Пусть имеется набор попарно непересекающихся (дизъюнктных) множеств \(A_1, A_2, \dots, A_k\). Тогда количество элементов в объединении этих множеств равно сумме количеств элементов каждого из них:

\[ |A_1 \cup A_2 \cup \dots \cup A_k| = |A_1| + |A_2| + \dots + |A_k|. \]

Если же множества пересекаются, правило суммы в таком виде неприменимо — в этом случае необходимо использовать принцип включения-исключения, который учитывает пересечения.

В прикладных задачах правило суммы часто формулируют для выбора одного из нескольких вариантов: если есть \(n\) способов совершить действие X и \(m\) способов совершить действие Y, причём эти действия не могут произойти одновременно, то совершить либо X, либо Y можно \(n + m\) способами.

История

Принцип, лежащий в основе правила суммы, был известен ещё в древности. Первые систематические комбинаторные задачи встречаются в трудах древнегреческих математиков, таких как Евклид и Архимед, однако чёткая формулировка правила суммы как отдельного комбинаторного принципа появилась значительно позже. В XVII веке, с развитием теории вероятностей (Блез Паскаль, Пьер де Ферма, Христиан Гюйгенс), комбинаторные правила, включая правило суммы, начали активно использоваться для подсчёта вероятностей в азартных играх. В XVIII—XIX веках комбинаторика оформилась как самостоятельная дисциплина, и правило суммы стало одним из её базовых положений, наряду с правилом произведения. В современной математике оно входит в стандартный курс дискретной математики и комбинаторики.

Отличие от правила произведения

Правило суммы часто путают с правилом произведения, хотя они описывают принципиально разные ситуации.

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

Пример: в меню есть 3 супа и 4 салата. Если посетитель хочет заказать или суп, или салат (но не оба), то количество вариантов равно \(3 + 4 = 7\) (правило суммы). Если же посетитель хочет заказать и суп, и салат, то количество вариантов равно \(3 \times 4 = 12\) (правило произведения).

Примеры применения

Пример 1: Выбор книги

На полке стоят 5 книг по математике, 3 книги по физике и 2 книги по химии. Сколькими способами можно выбрать одну книгу? Поскольку книги по разным предметам — это непересекающиеся множества, применяем правило суммы: \(5 + 3 + 2 = 10\) способов.

Пример 2: Маршруты

Из города A в город B можно добраться тремя автобусными маршрутами, двумя железнодорожными и одним авиарейсом. Сколькими способами можно доехать из A в B? Так как виды транспорта взаимоисключают друг друга (поездка осуществляется одним видом), количество способов равно \(3 + 2 + 1 = 6\).

Пример 3: Цифры и буквы

Сколько существует трёхзначных чисел, начинающихся на цифру 1 или на цифру 9? Первая цифра может быть либо 1, либо 9 — это два взаимоисключающих случая. Для каждого из них количество вариантов оставшихся двух цифр (от 00 до 99) равно 100. По правилу суммы: \(100 + 100 = 200\) чисел.

Пример 4: Вероятность

В урне 5 белых, 3 чёрных и 2 красных шара. Какова вероятность вытащить белый или красный шар? Количество благоприятных исходов (белый или красный) равно \(5 + 2 = 7\) (правило суммы). Общее количество исходов — 10. Вероятность: \(7/10 = 0.7\).

Обобщение: принцип включения-исключения

Если множества пересекаются, простое сложение приводит к двойному счёту общих элементов. Для двух пересекающихся множеств A и B правило суммы принимает вид:

\[ |A \cup B| = |A| + |B| - |A \cap B|. \]

Для трёх и более множеств формула усложняется — это и есть принцип включения-исключения. Правило суммы является его частным случаем при отсутствии пересечений.

Применение в информатике и программировании

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

Ограничения

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

См. также

• Правило произведения
• Комбинаторика
• Принцип включения-исключения
• Мощность множества

Источники

• Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
• Андерсон Дж. Дискретная математика и комбинаторика. — М.: Вильямс, 2004.
• Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988.