Изменения

{{Определение|definition='''Формула включения-исключения''' (англ. ''Inclusion-exclusion principle'') {{-- это -}} комбинаторная формула, которая позволяет определить выражающая мощность объединения конечных множеств, если известны их через мощности всех множеств и мощности всех их возможных пересечений.}}

Например, в случае Для случая из двух множеств <texdpi = "140">~A, B</tex> формула включения-исключения имеет следующий вид:

<texdpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</tex>

В силу того, что в сумме <texdpi = "140">~| A | + | B |</tex> элементы пересечения <texdpi = "140">A \cap B</tex> учтены дважды, и то уменьшаем текущее значение суммы на мощность пересечения, чтобы компенсировать это мы вычитаем <tex> | A \cap B |</tex> из правой части формулыкаждый элемент был подсчитан ровно один раз. Справедливость этого рассуждения видна из диаграммы Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае Для случая с большим количеством рассматриваемых множеств <texdpi = "140">~n>2</tex> множеств процесс нахождения количества элементов объединения <tex>A_1 \cup A_2 \cup \ldots \cup A_n</tex> состоит во включении всего, затем исключении лишнего, затем включении в поочередном включений ошибочно исключенного и так далее, то есть в попеременном включении и исключенииисключений ошибочно включенного. Отсюда и происходит название формулы.  Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.

|statement=Пусть <texdpi = "140"> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <texdpi = "140"> | A | = \sum \limits_{I_n I \in 2^N -1} (-1)^{k|I|+1} \Bigleft| \bigcap \limits_{ j \in I_n I} A_j \Bigright| </tex> </center>Причем <texdpi = "140"> I_n N = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} </tex>, то есть некоторый набор индексов множеств(индексы этих множеств не могут превышать число <tex>~n</tex>), пересечение которых мы ищем в текущем слагаемом суммы. За <tex> k </tex> принимаем количество таких индексов в текущем <tex> I_n </tex>, Здесь за <texdpi = "140"> j 2^N - 1 </tex> индекс текущего множества (причем обозначим множество всех непустых подмножеств <texdpi = "140"> j \in I_n N </tex>), которое будет входить в пересечение в текущем слагаемом. 

Будем доказывать теорему, опираясь на метод математической индукцииПриведем два разноплановых доказательства теоремы.

Пусть <tex>~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем'''I. Для случая <tex>~l=1</tex> и <tex>~l=2</tex> теорема, очевидно, вернаКомбинаторное доказательство теоремы. Таким образом, <tex>~l=2</tex> {{---}} база индукции. '''

Предположим, что для Рассмотрим некоторый элемент <texdpi = "140">~lx \in \bigcup \limits_{i=1}^{n-}A_i </tex>. Пусть <tex dpi = "140"> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex> теорема верна, то есть равенство выполняется. Докажем, что равенство истинно для Тогда найдем число вхождений элемента <texdpi = "140">~l=nx </tex> в правую часть формулы.

Пусть <tex> A </tex>{{---}} пересечение <tex>~n</tex> множеств. Тогда очевидноДокажем, что <texdpi = "140"> A = \bigcup sum \limits_{ij =10}^{nt}A_i = \Bigg( {\bigcup \limits_{i=1}^{n-1}A_i} \Bigg) \cup A_n </tex>. Пусть <tex> B = \bigcup \limits_{i=1}^j {n-1t \choose j}A_i = 0</tex>

Тогда исходя из предположения индукции имеемТаким образом, что <texdpi = "140"> | B | k = {t \choose 0} - \sum \limits_{I_j = 0}^{n-1}t} (-1)^{|I_{n-1}|+j = 1} \Big| \bigcap \limits_{ j \in I_{n-0 = 1} } A_j \Big| </tex>, то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана.

Кроме тогоПусть <tex dpi = "130">~l</tex> {{---}} это количество множеств, так как формула верна для мощность пересечения которых мы ищем. Для случая <texdpi = "130">~l=21</tex> равенство обращается в тривиальное (из базы индукции), то верно равенство <texdpi = "130"> | A | = | B | + | A_n A_1| </tex> {{--- | B \cap A_n |}} истинно). Для случая <tex dpi = "130"x>~l=2</tex>справедливость теоремы пояснена выше. То найдем мощность множества Таким образом, <texdpi = "130">~ B \cap A_n l=2</tex>{{---}} база индукции.

Найдем <tex dpi = "130">~| B \cap A_n |</tex>:  Очевидно, что <tex dpi = "130"> 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) (**)</tex>  Опираясь на предположение индукции и равенство <tex dpi = "130"> (**) </tex> имеем, что <tex dpi = "130"> |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| </tex>  Подставим полученные значения в <tex dpi = "130">(*)</tex>:  <tex dpi = "130"> | 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)</tex> <tex dpi = "130"> =| 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) </tex>  Докажем, что <tex dpi = "130"> | 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) </tex> <tex dpi = "130"> = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> Равенство справедливо, потому что все наборы <tex dpi = "130"> I \in 2^N </tex> можно разбить на две группы : # <tex dpi = "130"> I \in 2^{N'} </tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс <tex dpi = "130"> n </tex>, а будут все различные варианты индексов остальных множеств, т.е. <tex dpi = "130"> I \in 2^{N'}</tex>.# <tex dpi = "130">\{n\} \cup I</tex>, где <tex dpi = "130">I \in N'</tex> Аналогично предыдущему, только в наборе будет индекс <tex dpi = "130"> n </tex>. Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит , равенство истинно и <tex dpi = "130">|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> .Таким образом, для <texdpi = "130">~l=n</tex> мы доказали, что равенство верно. Значит , индукционный переход доказанверен, то есть теорема доказана.