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

Формула включения-исключения — комбинаторная формула, выражающая мощность объединения конечных множеств через мощности и мощности всех их возможных пересечений.

Случай для двух множеств

Для случая из двух множеств [math]A, B[/math] формула включения-исключения имеет следующий вид:

[math] | A \cup B | = | A | + | B | - | A \cap B |[/math]

В силу того, что в сумме [math]| A | + | B |[/math] элементы пересечения [math]A \cap B[/math] учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера—Венна для двух множеств, приведенной на рисунке справа.

Для случая с большим количеством рассматриваемых множеств [math] n [/math] процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.

Теорема:

Пусть [math] A = \bigcup \limits_{i=1}^{n}A_i [/math] , тогда по формуле включения—исключения: [math] | A | = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| [/math] Причем [math] N = \{ 1,2, \ldots ,n \} [/math]. Здесь за [math] 2^N [/math] обозначим множество всех непустых подмножеств [math] N [/math].

Доказательство:

[math]\triangleright[/math]

Приведем два разноплановых доказательства теоремы. I. Комбинаторное доказательство теоремы. Рассмотрим некоторый элемент [math] x \in \bigcup \limits_{i=1}^{n}A_i [/math]. Пусть [math] x \in \bigcap \limits_{j=1}^{t}A_{i_j} [/math]. Тогда найдем число вхождений элемента [math] x [/math] в правую часть формулы. [math]k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} + (-1) {t \choose 0} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} [/math][math] = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} [/math] Докажем, что [math] \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0[/math] В силу того, что [math] (1 + (-1)) ^ t = {t \choose 0} 1^t (-1)^0 + {t \choose 1} 1 ^ {t - 1} (-1) ^ 1 + \ldots + {t \choose t} 1^0 (-1)^t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}[/math], имеем [math] 0 = (1 + (-1)) ^ t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}[/math], то равенство доказано. Таким образом, [math] k = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j = 1 - 0 = 1[/math], то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана. II. Доказательство теоремы по индукции. Пусть [math]~l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]~l=1[/math] равенство обращается в тривиальное ([math] |A| = |A_1| [/math] — истинно). Для случая [math]~l=2[/math] справедливость теоремы пояснена выше. Таким образом, [math]~l=2[/math] — база индукции. Предположим, что для [math]~l=n-1[/math] равенство верно. Докажем, что равенство истинно для [math]~l=n[/math] Пусть [math] A [/math] — объединение [math]~n[/math] множеств. Очевидно, что [math] A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n [/math]. Пусть [math] B = \bigcup \limits_{i=1}^{n-1}A_i [/math]; [math]N' = \{ 1,2, \ldots ,n-1 \} [/math]. Исходя из предположения индукции, имеем, что [math] | B | = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| [/math] Кроме того, так как формула верна для [math]~l=2[/math] (из базы индукции), то верно равенство [math] | A | = | B | + | A_n | - | B \cap A_n | (*)[/math]. Найдем [math]~| B \cap A_n |[/math]: Очевидно, что [math] B \cap A_n = \left( \bigcup \limits_{i=1}^{n-1}A_i \right) \cap A_n = \bigcup \limits_{i=1}^{n-1} \left( A_i \cap A_n \right) (**)[/math] Опираясь на предположение индукции и равенство [math] (**) [/math] имеем, что [math] |B \cap A_n| = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} \left( A_j \cap A_n \right) \right| = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| [/math] Подставим полученные значения в [math](*)[/math]: [math] | A | = | A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| \right) - \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right)[/math] [math] =| A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| \right) + \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+2} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right) [/math] Докажем, что [math] | A_n |+\left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| \right) + \left( \sum \limits_{I \in 2^{N'}} (-1)^{|I|+2} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right) [/math] [math] = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| [/math] Равенство справедливо, потому что все наборы [math] I \in 2^N [/math] можно разбить на две группы : [math] I \in 2^{N'} [/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math], а будут все различные варианты индексов остальных множеств, т.е. [math] I \in 2^{N'}[/math]. [math]\{n\} \cup I[/math], где [math]I \in N'[/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math]. Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и [math]|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| [/math] . Таким образом, для [math]~l=n[/math] мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.

[math]\triangleleft[/math]