Спирина, М.С. Дискретная математика

При решении комбинаторных задач в первую очередь будем применять два важных и полезных правила: правило суммы и пра­ вило произведения. Правило суммы. Обозначим число элементов конечного мно­ жества А через п(А). Как известно из подразд. 1.2, чтобы найти число элементов в объединении непересекающихся множеств А и В, надо их сложить. То есть, если множества А и В конечны и А П В = 0 , то я (Л и В) = л(Л) + п(В). На практике будем применять другой вариант этого правила: пусть элемент а можно выбрать к способами, а элемент р — т способами, причем, если любой способ выбора а отличается от любого способа выбора р (независим), то выбор «а или р» можно сделать к + т способами. Например, если в группе 16 юношей и 14 девушек, то преподаватель может вызвать к доске одного уча­ щегося 16 + 14 = 30 способами. Если два множества пересекаются и имеют общие элементы, то количество элементов в их объединении можно найти по фор­ муле п(А[] В) = п(А) + п(В) - п(АГ\В) . Круги Эйлера помогают увидеть, что пересечение А П В содер­ жит одни и те же элементы дважды, поэтому необходимо убрать лишние п(АГ\В) (рис. 1.17, а). Задача 1. Сколько человек в группе занимается спортом, если 9 человек занимаются лыжами и плаванием, а 12 человек — пла­ ванием и волейболом, причем в секцию по плаванию ходят 4 че­ ловека из группы (рис. 1.17, б)? Решение. Имеем: п(А) = 9, п(В) = 12, п(АГ\В) = 4, л (/Щ В) = = п(А) + п(В) - п(АГ)В) = 9 + 12 - 4 = 17. Правило суммы для трех множеств имеет вид (рис. 1.17, в) n(A\ JB\ JC) =n(A) +n(B) +n ( Q - n ( A ( ] B ) - n ( A r \ C ) - n ( B r \ C ) + + п(АПВГ\С) . О ; Как можно объяснить эту формулу с помощью кругов Эйлера? Напомним, что ключевое слово для применения правила сум­ мы — слово или. Рис. 1.17. Схемы, иллюстрирующие правило суммы для объединения множеств: а — для двух множеств; б — к задаче 1; в — для трех множеств 46