Принцип включения-исключения
Пусть $A$ — заданное множество и $S$ — множество свойств (множество, элементы которого будут называться свойствами). Каждый элемент из $A$ может обладать некоторыми свойствами из $S$. Другими словами, задана функция, сопоставляющая каждому элементу из $A$ некоторое подмножество множества $S$: $g: A \rightarrow 2^S$. Будем говорить, что элемент $a$ обладает свойствами $g(a)$.
Пусть $T\subseteq S$. Обозначим $f_=(T)$ — число элементов из множества $A$, которые обладают всеми свойствами из $T$ и не обладают свойствами из множества $S\setminus T$; $f_=(T) = \left|\{a: a\in A\textrm, T = g(a)\}\right|$.
$f_\geq(T)$ — число элементов из $A$, которые обладают всеми свойствами из $T$ и, возможно, какими-то еще.
$f_\geq(T) = \left|\{a: a\in A\textrm, T\subseteq g(a)\}\right|$.
Тогда очевидно, что [math]\displaystyle{ f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y). }[/math]
Далее нам бы хотелось найти обратное соотношение. То есть способ находить значение функции $f_=$, зная значения функции $f_\geq$.
Пусть $\varphi: 2^S\rightarrow \mathbb{R}$ — произвольная функция, сопоставляющая каждому подмножеству конечного множества $S$ некоторое вещественное число. Пусть $\psi$ — такая функция из $2^S$ в $\mathbb{R}$, что [math]\displaystyle{ \psi(T) = \sum_{T\subseteq Y\subseteq S} \varphi(Y),\quad \forall T\subseteq S. }[/math]
Тогда [math]\displaystyle{ \varphi(T) = \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \psi(Y),\quad \forall T\subseteq S. }[/math]
Доказательство. Пусть $T\subseteq S$.
Тогда [math]\displaystyle{ \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \psi(Y)= \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \sum_{Y\subseteq Z\subseteq S} \varphi(Z)= }[/math] [math]\displaystyle{ = \sum_{T\subseteq Y\subseteq Z\subseteq S} (-1)^{|Y\setminus T|} \varphi(Z)= \sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{T\subseteq Y\subseteq Z} (-1)^{|Y\setminus T|} = }[/math] [math]\displaystyle{ = \sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{i=0}^{|Z\setminus T|}\sum_{\substack{T\subseteq Y\subseteq Z,\\ |Y|=|T|+i}} (-1)^{|Y\setminus T|} = \sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{i=0}^{|Z\setminus T|} (-1)^{i} \binom{|Z\setminus T|}{i}= \sum_{T\subseteq Z\subseteq S}\varphi(Z)\delta_o(|Z\setminus T|) = \varphi(T). }[/math]
Здесь $\delta_o(n)$ — дельта-функция.
[math]\displaystyle{ \label{equation:include-exclude} f_=(T) = \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} f_\geq(Y). }[/math]
В частности,
[math]\displaystyle{ \label{equation:include-exclude_varnothing} f_=(\varnothing) = \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y). }[/math]
Конспект: Дискретная математика