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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Доказываем теорему по индукции.
 
Доказываем теорему по индукции.
  
Пусть <tex>~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex>~l=1</tex> и <tex>~l=2</tex> теорема, очевидно, верна. Таким образом, <tex>~l=2</tex> {{---}} база индукции.   
+
Пусть <tex>~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex>~l=1</tex> равенство обращается в тривиальное (<tex> |A| = |A| </tex>).  Для случая <tex>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <tex>~l=2</tex> {{---}} база индукции.   
  
 
Предположим, что для <tex>~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex>~l=n</tex>  
 
Предположим, что для <tex>~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex>~l=n</tex>  

Версия 02:08, 25 октября 2011

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

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

Например, в случае двух множеств [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 \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]

Доказываем теорему по индукции.

Пусть [math]~l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]~l=1[/math] равенство обращается в тривиальное ([math] |A| = |A| [/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 |(1)[/math]. Найдем [math]~| B \cap A_n |[/math]:


Очевидно, что [math] | B \cap A_n | = \left| \left( \bigcup \limits_{i=1}^{n-1}A_i \right) \cap A_n \right|= \left| \bigcup \limits_{i=1}^{n-1} \left( A_i \cap A_n \right) \right| (2)[/math]


Тогда из предположения индукции имеем, что [math] (2) = [/math] [math] \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](1)[/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] - \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| = \ \sum \limits_{I \in 2^{N'}} (-1)^{|I|+2} \left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \[/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|+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] можно разбить на три группы :

  1. [math] \{ n \} [/math]
  2. [math] I \in 2^{N'} [/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math], а будут все различные варианты индексов остальных множеств, т.е. [math] I \in 2^{N'}[/math]
  3. [math] \{ n \} \cup I \in 2^{N'} [/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math]

Как видно из равенства, каждое слагаемое "отвечает" за соответствующие группы. Значит, равенство истинно.

Таким образом, для [math]~l=n[/math] мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.
[math]\triangleleft[/math]