90
правок
Изменения
Нет описания правки
'''Формула включения{{---}}исключения''' {{---}} это комбинаторная формула, которая позволяет определить мощность объединения конечных множеств, если известны их мощности и мощности всех их возможных пересечений.
[[Файл:пересечение двух множеств.svg.png|thumb|right|Случай для двух множеств]]
Например, в случае двух множеств <tex>~A, B</tex> формула включения{{---}}исключения имеет вид:
<center>
<tex> | A \cup B | = | A | + | B | - | A \cap B |</tex>
</center>
В сумме <tex>~| A | + | B |</tex> элементы пересечения <tex>A \cap B</tex> учтены дважды, и , чтобы компенсировать это , мы вычитаем <tex> | A \cap B |</tex> из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.
Таким же образом и в случае <tex>~n>2</tex> множеств процесс нахождения количества элементов объединения <tex>A_1 \cup A_2 \cup \ldots \cup A_n</tex> состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
{{Теорема
|statement=Пусть <tex> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения{{---}}исключения: <center> <tex> | A | = \sum \limits_{I_n } (-1)^{k+1} \Big| \bigcap \limits_{ j \in I_n } A_j \Big| </tex> </center>
Причем <tex> I_n = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} </tex>, то есть некоторый набор индексов множеств(индексы этих множеств не могут превышать число <tex>~n</tex>), пересечение которых мы ищем в текущем слагаемом суммы. За <tex> k </tex> принимаем количество таких индексов в текущем <tex> I_n </tex>, за <tex> j </tex> индекс текущего множества (причем <tex> j \in I_n </tex>), которое будет входить в пересечение в текущем слагаемом.
