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