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