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



             

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


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

N
предметов, некоторые из которых обладают свойствами
\alpha _1,\alpha _2,\ldots \alpha _n
. При этом каждый предмет может либо не обладать ни одним из этих свойств, либо обладать одним или несколькими свойствами. Обозначим через
N(\alpha _i \alpha _j \ldots \alpha _k )
количество предметов, обладающих свойствами
\alpha _i,\alpha _j ,\ldots,\alpha _k
(и быть может, еще некоторыми из других свойств). Если нужно взять предметы, не обладающие некоторым свойством, то эти свойства пишем со штрихом. Например, через
N(\alpha _1 \alpha _2 \alpha _4'
) обозначено количество предметов, обладающих свойствами
\alpha _1,\alpha _2
, но не обладающих свойством
\alpha _4
(вопрос об остальных свойствах останется открытым). Число предметов, не обладающих ни одним из указанных свойств, обозначается по этому правилу через
N(\alpha _1' \alpha _2' \ldots \alpha _n')
. Общий закон состоит в том, что

 \begin{gathered} N(\alpha _1' \alpha _2' \ldots \alpha _n' ) = N - N(\alpha _1 ) - N(\alpha _2 ) - \ldots - N(\alpha _n ) + N(\alpha _1 \alpha _2 ) + \\ + N(\alpha _1 \alpha _3 ) + \ldots + N(\alpha _1 \alpha _n ) +\ldots+ N(\alpha _{n - 1} \alpha _n ) - N(\alpha _1 \alpha _2 \alpha _3 ) - \ldots - \\ -N(\alpha _{n - 2} \alpha _{n - 1} \alpha _n + \ldots + ( - 1)^n N(\alpha _1 \alpha _2 \ldots \alpha _n ). \end{gathered}

(6.3)

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

\alpha _1,\alpha _2,\ldots,\alpha _n
(без учета их порядка), причем знак + ставится, если число учитываемых свойств четно, и знак
-
, если это число нечетно. Например,
N(\alpha _1 \alpha _3 \alpha _6 \alpha _8 )
входит со знаком +, а
N(\alpha _3 \alpha _4 \alpha _{10} )
со знаком
-
. Формулу 6.3 называют формулой включений и исключений - сначала исключаются все предметы, обладающие хотя бы одним из свойств
\alpha _1,\alpha _2,\ldots,\alpha _n
, потом включаются предметы, обладающие, по крайней мере, двумя из этих свойств, затем исключаются имеющие, по крайней мере, три и т.д.




Содержание  Назад  Вперед