Принцип включения-исключения

Пусть $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]

Рис. 1. [math]\displaystyle{ f_=(Y) }[/math] — элементы ровно с набором свойств [math]\displaystyle{ Y }[/math], а [math]\displaystyle{ f_\geq(T) }[/math] — все элементы, у которых есть все свойства [math]\displaystyle{ T }[/math]. Для двух свойств суммы получаются сложением точных классов: [math]\displaystyle{ f_\geq(\varnothing)=1+2+1+2=6 }[/math], [math]\displaystyle{ f_\geq(\{1\})=2+2=4 }[/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)$ — дельта-функция.

Следствие:

Поскольку $f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y)$, то для любого $T\subseteq S$

[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]

Рис. 2. Обратная формула: [math]\displaystyle{ f_=(T) }[/math] — знакопеременная сумма [math]\displaystyle{ f_\geq(Y) }[/math] по всем [math]\displaystyle{ Y\supseteq T }[/math]. Слева [math]\displaystyle{ T=\varnothing }[/math]: [math]\displaystyle{ 6-4-3+2=1 }[/math]; справа [math]\displaystyle{ T=\{1\} }[/math]: в сумму входят только [math]\displaystyle{ \{1\} }[/math] и [math]\displaystyle{ \{1,2\} }[/math], поэтому [math]\displaystyle{ 4-2=2 }[/math].

Рис. 3. Почему знаки сокращаются: элемент входит в те [math]\displaystyle{ f_\geq(Y) }[/math], для которых [math]\displaystyle{ Y\subseteq g(a) }[/math]. У [math]\displaystyle{ a_1 }[/math] без свойств остаётся только [math]\displaystyle{ +1 }[/math], у остальных элементы со знаками [math]\displaystyle{ +1 }[/math] и [math]\displaystyle{ -1 }[/math] взаимно уничтожаются, поэтому итог равен 1.

Конспект: Дискретная математика