Главная > Индукция. Комбинаторика
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

<< Предыдущий параграф Следующий параграф >>
Оглавление