2.3. Правило (принцип) включения – исключения

Формулировка правила (принципа) включения - исключения  применительно к двум множествам объектов: если некоторый объект a можно выбрать M способами, а другой объект b можно выбрать N способами, причем способы выбора объектов a, b могут совпадать (одним и тем же способом может быть выбран как объект a, так и объект b), то выбор либо a, либо b можно осуществить M + N – K способами, где K – число совпадений.

Из формулировки следует - данное правило является более общим по сравнению с правилом сложения: оно применимо в ситуациях, когда множество A способов выбора объекта  a пересекается с множеством B способов выбора объекта   b, т.е. полное множество C = A + B способов выбора этих объектов невозможно представить в виде разбиения S = { A,B } (A∙B = Ø). В соответствии с формулировкой искомое число | C | способов можно найти по формуле

| C | = | A + B | = | A | + | B | - | AB |. (2.8)

Обоснование (интерпретация) правила.  Класс комбинаторных задач, решение которых сводится к использованию записанного равенства, можно сформулировать следующим образом:

Пусть имеется множество U объектов (предметов), некоторые из которых обладают свойствами α, β. При этом каждый конкретный предмет может либо не обладать ни одним из этих свойств, либо обладать каким-то одним свойством, либо обоими вместе. Требуется ответить на вопрос: какое число предметов из заданного множества обладает хотя бы одним из указанных свойств ?

Если обозначить множество предметов, обладающих свойством α, через A, а множество предметов, обладающих свойством β, через B, то для множества C предметов, обладающих хотя бы одним из этих свойств, будет справедливо равенство (2.8). В этом равенстве | AB | - мощность пересечения множеств A, B, определяющая число предметов, обладающих обоими свойствами.

Замечание. Характерной особенностью рассматриваемого класса задач является то, что формулировки решаемых (исследуемых) в них вопросов могут быть совершенно разными. Так, если среди всего множества предметов U имеются такие, которые не обладают свойствами α, β, а общее число предметов Nо = |U| известно, то вполне уместен (корректен) вопрос: какое число предметов из заданного множества не обладает ни одним из свойств ? В соответствии с формулировкой необходимо найти не мощность множества С, а мощность его дополнения (отрицания), т.е. число предметов, составляющих множество U \ С (множество U выполняет роль универсального множества). Ясно, что в данном случае искомое число будет равно |U \С|=Nо-| С | (см. пример 2.6).

Обобщение правила  включения – исключения: если полное множество W способов выбора из множества U объектов (предметов), обладающих определенными свойствами из заданного набора k уникальных свойств, представлено в виде объединения (суммы) k подмножеств

W = A + B + C + ... + G + H + L,

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

(2.9)

Выражение (2.9) получило название формулы включений и исключений . Его правая часть содержит знакочередующиеся слагаемые, что как раз и характеризует суть правила включения – исключения (см. пример 2.7): сначала включается (подсчитывается) общее число способов выбора предметов, обладающих хотя бы одним свойством; затем из полученного исключается число предметов, обладающих по крайней мере двумя свойствами; далее включается число предметов, удовлетворяющих не менее чем трем свойствам и т.д.