Комбинаторные алгоритмы для программистов

          

Формула включений и исключений


Пусть имеется

Формула включений и исключений
предметов, некоторые из которых обладают свойствами
Формула включений и исключений
. При этом каждый предмет может либо не обладать ни одним из этих свойств, либо обладать одним или несколькими свойствами. Обозначим через
Формула включений и исключений
количество предметов, обладающих свойствами
Формула включений и исключений
(и быть может, еще некоторыми из других свойств). Если нужно взять предметы, не обладающие некоторым свойством, то эти свойства пишем со штрихом. Например, через
Формула включений и исключений
) обозначено количество предметов, обладающих свойствами
Формула включений и исключений
, но не обладающих свойством
Формула включений и исключений
(вопрос об остальных свойствах останется открытым). Число предметов, не обладающих ни одним из указанных свойств, обозначается по этому правилу через
Формула включений и исключений
. Общий закон состоит в том, что

Формула включений и исключений

(6.3)

Здесь алгебраическая сумма распространена на все комбинации свойств

Формула включений и исключений
(без учета их порядка), причем знак + ставится, если число учитываемых свойств четно, и знак
Формула включений и исключений
, если это число нечетно. Например,
Формула включений и исключений
входит со знаком +, а
Формула включений и исключений
со знаком
Формула включений и исключений
. Формулу 6.3 называют формулой включений и исключений - сначала исключаются все предметы, обладающие хотя бы одним из свойств
Формула включений и исключений
, потом включаются предметы, обладающие, по крайней мере, двумя из этих свойств, затем исключаются имеющие, по крайней мере, три и т.д.



Содержание раздела