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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формула включения-исключения)
(Формула включения-исключения)
Строка 14: Строка 14:
 
{{Теорема  
 
{{Теорема  
 
|statement=Пусть <tex> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <tex> | A | = \sum \limits_{I } (-1)^{k+1}  \Big| \bigcap \limits_{ j \in I } A_j \Big| </tex> </center>
 
|statement=Пусть <tex> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <tex> | A | = \sum \limits_{I } (-1)^{k+1}  \Big| \bigcap \limits_{ j \in I } A_j \Big| </tex> </center>
Причем <tex> I = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} </tex>, то есть некоторый набор индексов множеств, пересечение которых мы ищем в текущем слагаемом суммы. За <tex> k </tex> принимаем количество таких индексов в текущем <tex> I </tex>.
+
Причем <tex> I = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} </tex>, то есть некоторый набор индексов множеств, пересечение которых мы ищем в текущем слагаемом суммы. За <tex> k </tex> принимаем количество таких индексов в текущем <tex> I </tex>, за <tex> j </tex> индекс текущего множества (причем <tex> j \in I </tex>), которое будет входить в пересечение в текущем слагаемом.
  
||proof=Для случая <tex>~n=1</tex> и <tex>~n=2</tex> теорема, очевидно, верна.  
+
||proof=
 +
Будем доказывать, опираясь на метод математической индукции.
 +
Для случая <tex>~n=1</tex> и <tex>~n=2</tex> теорема, очевидно, верна.  
  
 
Теперь рассмотрим <tex>~n>2</tex>:
 
Теперь рассмотрим <tex>~n>2</tex>:

Версия 02:06, 19 октября 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 } (-1)^{k+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| [/math]
Причем [math] I = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} [/math], то есть некоторый набор индексов множеств, пересечение которых мы ищем в текущем слагаемом суммы. За [math] k [/math] принимаем количество таких индексов в текущем [math] I [/math], за [math] j [/math] индекс текущего множества (причем [math] j \in I [/math]), которое будет входить в пересечение в текущем слагаемом.
Доказательство:
[math]\triangleright[/math]

Будем доказывать, опираясь на метод математической индукции. Для случая [math]~n=1[/math] и [math]~n=2[/math] теорема, очевидно, верна.

Теперь рассмотрим [math]~n\gt 2[/math]:

[math] A = \bigcup \limits_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup \limits_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n [/math]


[math] | B | = \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| [/math]


[math] | A | = | B | + | A_n | - | 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| = [/math]


[math] = \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap \limits_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \Big| [/math]


Таким образом:


[math] | A |=| A_n |+\Bigg( \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| \Bigg) - - \Bigg( \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum \limits_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| [/math]

[math]\triangleleft[/math]