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

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

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

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

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

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

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

Таким же образом и в случае [math]~n\gt 2[/math] множеств процесс нахождения количества элементов объединения [math]A_1 \cup A_2 \cup \ldots \cup A_n[/math] состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

Теорема:

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

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

[math]\triangleright[/math]

Будем доказывать теорему, опираясь на метод математической индукции. Пусть [math]~l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]~l=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 = \Bigg( {\bigcup \limits_{i=1}^{n-1}A_i} \Bigg) \cup A_n [/math]. Пусть [math] B = \bigcup \limits_{i=1}^{n-1}A_i [/math] Тогда исходя из предположения индукции имеем, что [math] | B | = \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| [/math] Кроме того, так как формула верна для [math]~l=2[/math] (из базы индукции), то верно равенство [math] | A | = | B | + | A_n | - | B \cap A_n |[/math]. То найдем мощность множества [math]~ B \cap A_n [/math]. Очевидно, что [math] \Big| B \bigcap A_n \Big| = \Bigg| \Bigg( \bigcup \limits_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup \limits_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| (1)[/math] Тогда из предположения индукции имеем, что [math] (1) = [/math] [math] \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \bigg| \bigcap \limits_{ j \in I_{n-1} } \Big( A_j \bigcap A_n \Big) \bigg| = \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| [/math] Таким образом: [math] | A |=| A_n |+\Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) - - \Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \Bigg)[/math] Заметим, что [math] - \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| = \ \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+2} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \[/math] Тогда [math] | A |=| A_n |+\Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) + \Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+2} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \Bigg) = \sum \limits_{I_n} (-1)^{|I_n|+1} \Big| \bigcap \limits_{ j \in I_n } A_j \Big| )[/math] . Равенство справедливо, потому что все наборы [math] I_n [/math] можно разбить на три группы : 1) [math] (n) [/math] 2) [math] (I_{n-1})[/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math], а будут все различные варианты индексов остальных множеств, т.е. [math] I_{n-1} [/math] 3) [math] (n; I_{n-1}) [/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math] Как видно из равенства, каждое слагаемое "отвечает" за соответствующие группы. Значит равенство истинно. Значит для [math]~l=n[/math] мы доказали, что равенство верно. Значит индукционный переход доказан, то теорема доказана.

[math]\triangleleft[/math]