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

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

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

Обозначим число элементов конечного множества А через а множество, состоящее из элементов, назовем -множеством. Например, является -множеством и

Рассмотрим следующую комбинаторную задачу:

Сколько элементов содержится в объединении -множества А и -множества В?

Эта задача имеет однозначное решение лишь в случае, когда множества не пересекаются, т. е. . В этом случае множество содержит элементов (например, если

содержит элементов). Таким образом, справедливо следующее утверждение:

Если множества конечны, причем то

Это очевидное утверждение называют в комбинаторике правилом суммы. Его формулируют также следующим образом:

Если а можно выбрать способами, а способами, причем любой способ выбора а отличается от любого способа выбора то выбор «а или можно сделать способами.

Например, если на тарелке лежат 8 яблок и 6 груш, то один плод можно выбрать способами.

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

Таким образом, число элементов в объединении двух конечных множеств равно сумме чисел элементов в каждом из них, уменьшенной на число элементов в пересечении этих множеств.

Аналогично рассматривается вопрос о числе элементов в объединении нескольких конечных множеств. Если эти множества попарно не пересекаются (т. е. если при то справедливо равенство

легко доказываемое с помощью математической индукции по

Как и при сложнее обстоит дело, если попарные пересечения множеств могут быть не пусты. В этом случае имеет место следующее равенство, обобщающее соотношение (2):

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

Поскольку в равенство (4) входят пересечения множеств оно учитывает, как эти множества перекрываются друг с другом, его называют формулой перекрытий или формулой включений и исключений. Мы приведем доказательство формулы (4) ниже, а сейчас покажем, как ее применяют для решения задач.

Сколько человек участвовало в прогулке, если известно, что 16 из них взяли с собой бутерброды с ветчиной, 24 — с колбасой, 15 — с сыром, 11 — и с ветчиной и с колбасой, 8 — и с ветчиной и с сыром, 12 — и с колбасой и с сыром, бутерброды всех трех видов, а 5 вместо бутербродов взяли с собой пирожки?

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

где через обозначено множество участников, взявших с собой вместо бутербродов пирожки. Найдем т. е. число участников прогулки, взявших с собой один или несколько видов бутербродов. По формуле (4) получаем:

Значит, бутерброды взяли с собой 30 человек, а всего в прогулке участвовали человек.

На рисунке 2 дана схема, графически изображающая условия задачи. Такие схемы называют диаграммами Эйлера — Венна. Они широко применяются для решения самых разнообразных задач, связанных с конечными множествами, математической логикой и т. д. С помощью такой диаграммы можно решить нашу задачу, не прибегая к формуле включений и исключений. Для этого заметим, что область, занумерованная римской цифрой VIII, соответствует множеству а потому содержит 6 элементов. Объединение областей VII и VIII изображает множество и потому содержит 11 элементов. Поскольку в области VIII содержится 6 элементов, а эти области не пересекаются, то в области VII содержится 5 элементов. Аналогично находим, что в области VI содержится 2 элемента, в области элементов. Теперь рассмотрим области, имеющие номера II, VI, VII и VIII. Их объединением является множество А, содержащее по условию 16 элементов. Но объединение областей VI, VII и VIII содержит элементов, а потому на долю области II остается 3 элемента. Так же находим, что область III содержит 7 элементов, а область IV — всего один элемент.

Но объединение областей II, III, IV, V, VI, VII и VIII является множеством Поскольку эти области попарно не пересекаются, то число элементов во множестве С равно Мы снова получили, что т. е. что бутерброды взяли с собой 30 человек. Область I изображает множество людей, захвативших пирожки, а прямоугольник — всех участников прогулки. Так как то общее число участников прогулки равно 35.

Рис. 2