23
правки
Изменения
Новая страница: «== Формула включения-исключения == '''Формула включения-исключения''' - это комбинаторная фор…»
== Формула включения-исключения ==
'''Формула включения-исключения''' - это комбинаторная формула, которая позволяет определить мощность объединения конечных множеств, если известны их мощности и мощности всех их возможных пересечений.
[[Файл:пересечение двух множеств.png|thumb|left|случай для двух множеств]]
Например, в случае двух множеств <math>~A, B</math> формула включения-исключения имеет вид:
<center>
<math> | A \cup B | = | A | + | B | - | A \cap B |</math>
</center>
В сумме <math>~| A | + | B |</math> элементы пересечения <math>A \cap B</math> учтены дважды, и чтобы компенсировать это мы вычитаем <math> | A \cap B |</math> из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.
Таким же образом и в случае <math>~n>2</math> множеств процесс нахождения количества элементов объединения <math>A_1 \cup A_2 \cup \ldots \cup A_n</math> состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>
== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.
Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>
<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ 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_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>
<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>
<center>
Таким образом:
</center>
<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>
'''Формула включения-исключения''' - это комбинаторная формула, которая позволяет определить мощность объединения конечных множеств, если известны их мощности и мощности всех их возможных пересечений.
[[Файл:пересечение двух множеств.png|thumb|left|случай для двух множеств]]
Например, в случае двух множеств <math>~A, B</math> формула включения-исключения имеет вид:
<center>
<math> | A \cup B | = | A | + | B | - | A \cap B |</math>
</center>
В сумме <math>~| A | + | B |</math> элементы пересечения <math>A \cap B</math> учтены дважды, и чтобы компенсировать это мы вычитаем <math> | A \cap B |</math> из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.
Таким же образом и в случае <math>~n>2</math> множеств процесс нахождения количества элементов объединения <math>A_1 \cup A_2 \cup \ldots \cup A_n</math> состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
== Теорема ==
Пусть <math> A = \bigcup_{i=1}^{n}A_i </math> , тогда по формуле включения-исключения:
<center>
<math> | A | = \sum_{I=(i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>
== Доказательство ==
Для случая <math>~n=1</math> и <math>~n=2</math> теорема, очевидно, верна.
Теперь рассмотрим <math>~n>2</math>:
<center>
<math> A = \bigcup_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </math>
<math> | B | = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ 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_{i=1}^{n-1}A_i \Bigg) \bigcap A_n \Bigg|= \Bigg| \bigcup_{i=1}^{n-1} \bigg( A_i \bigcap A_n \bigg) \Bigg| = </math>
<math> = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \bigg| \bigcap_{ j \in I } \Big( A_j \bigcap A_n \Big) \bigg| = \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| </math>
</center>
<center>
Таким образом:
</center>
<center>
<math> | A | = | A_n| + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j \in I } A_j \Big| \Bigg) + \Bigg( \sum_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap_{ j\in I \cup \{ n \} } A_j \Big| \Bigg) = \sum_{I \subset \{ 1,2, \ldots ,n \} } (-1)^{k+1} \Big| \bigcap_{ j \in I } A_j \Big| </math>
</center>
