Изменения

 == Формула включения-исключения =={{Определение|definition='''Формула включения-исключения''' (англ. ''Inclusion-exclusion principle'') {{---}} это комбинаторная формула, которая позволяет определить выражающая мощность объединения конечных множеств, если известны их через мощности всех множеств и мощности всех их возможных пересечений.}}

Например, в случае Для случая из двух множеств <texdpi = "140">~A, B</tex> формула включения-исключения имеет следующий вид:

<texdpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</tex>

В силу того, что в сумме <texdpi = "140">~| A | + | B |</tex> элементы пересечения <texdpi = "140">A \cap B</tex> учтены дважды, и то уменьшаем текущее значение суммы на мощность пересечения, чтобы компенсировать это мы вычитаем <tex> | A \cap B |</tex> из правой части формулыкаждый элемент был подсчитан ровно один раз. Справедливость этого рассуждения видна из диаграммы Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.  Для случая с большим количеством рассматриваемых множеств <tex dpi = "140"> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

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

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

Будем доказывать теоремуПриведем два разноплановых доказательства теоремы. '''I. Комбинаторное доказательство теоремы.''' Рассмотрим некоторый элемент <tex dpi = "140"> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <tex dpi = "140"> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <tex dpi = "140"> x </tex> в правую часть формулы. <tex dpi = "140">k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} </tex><tex dpi = "140"> = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} </tex> Докажем, опираясь на метод математической что <tex dpi = "140"> \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0</tex> В силу того, что <tex dpi = "140"> (1 + (-1)) ^ t = {t \choose 0} 1^t (-1)^0 + {t \choose 1} 1 ^ {t - 1} (-1) ^ 1 + \ldots + {t \choose t} 1^0 (-1)^t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, имеем <tex dpi = "140"> 0 = (1 + (-1)) ^ t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, то равенство доказано. Таким образом, <tex dpi = "140"> k = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j = 1 - 0 = 1</tex>, то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана. '''II. Доказательство теоремы по индукции.''' Пусть <tex dpi = "130">~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex dpi = "130">~l=1</tex> равенство обращается в тривиальное (<tex dpi = "130"> |A| = |A_1| </tex> {{---}} истинно). Для случая <tex dpi = "130"x>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <tex dpi = "130">~l=2</tex> {{---}} база индукции.  Предположим, что для <tex dpi = "130">~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex dpi = "130">~l=n</tex>   Пусть <tex dpi = "130"> A </tex> {{---}} объединение <tex dpi = "130">~n</tex> множеств. Очевидно, что <tex dpi = "130"> A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n </tex>. Пусть <tex dpi = "130"> B = \bigcup \limits_{i=1}^{n-1}A_i </tex>; <tex dpi = "130">N' = \{ 1,2, \ldots ,n-1 \} </tex>.  Исходя из предположения индукции, имеем, что <tex dpi = "130"> | B | = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex>  Кроме того, так как формула верна для <tex dpi = "130">~l=2</tex> (из базы индукции), то верно равенство <tex dpi = "130"> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>.

Предположим, что для Найдем <tex>~ldpi =n-1</tex> теорема верна, то есть равенство выполняется. Докажем, что равенство истинно для <tex"130">~l=n| B \cap A_n |</tex> :

Пусть <tex> A </tex>{{---}} пересечение <tex>~n</tex> множеств. Тогда очевидноОчевидно, что <texdpi = "130"> A = B \bigcup \limits_{i=1}^{n}A_i cap A_n = \Biggleft( {\bigcup \limits_{i=1}^{n-1}A_i} \Biggright) \cup cap A_n </tex>. Пусть <tex> B = \bigcup \limits_{i=1}^{n-1}\left( A_i \cap A_n \right) (**)</tex>

Тогда исходя из предположения Опираясь на предположение индукции и равенство <tex dpi = "130"> (**) </tex> имеем, что <texdpi = "130"> | B \cap A_n| = \sum \limits_{I_I \in 2^{n-1N'}} (-1)^{|I_I|+1} \left| \bigcap \limits_{nj \in I} \left( A_j \cap A_n \right) \right| = \sum \limits_{I \in 2^{N'}} (-1})^{|I|+1} \Bigleft| \bigcap \limits_{ j \in I_I \cup \{n-1\} } A_j \Bigright| </tex>

Кроме того, так как формула верна для Подставим полученные значения в <tex>~ldpi =2</tex"130"> (из базы индукции*), то верно равенство <tex> | A | = | B | + | A_n | - | B \cap A_n |</tex>. То найдем мощность множества <tex>~ B \cap A_n </tex>.:

Очевидно, что <texdpi = "130"> | A | = | A_n |+\left( \sum \Biglimits_{I \in 2^{N'}} (-1)^{|I|+1} \left| B \bigcap A_n \Biglimits_{ j \in I} A_j \right| = \Bigg| right) - \Biggleft( \bigcup sum \limits_{i=I \in 2^{N'}} (-1})^{n-|I|+1}A_i \Bigg) left| \bigcap \limits_{ j\in I \cup \{ n \} } A_j \right| \right)</tex> <tex dpi = "130"> =| A_n |+\left( \Biggsum \limits_{I \in 2^{N'}} (-1)^{|I|= +1} \Biggleft| \bigcup bigcap \limits_{i=1j \in I }A_j \right| \right) + \left( \sum \limits_{I \in 2^{nN'}} (-1)^{|I|+2} \bigg( A_i left| \bigcap A_n \bigg) limits_{ j\in I \cup \{ n \} } A_j \Biggright| (1\right) </tex>

Тогда из предположения индукции имеемДокажем, что <texdpi = "130"> | A_n |+\left(1) = </tex> <tex> \sum \limits_{I_I \in 2^{n-1N'}} (-1)^{|I_{n-1}I|+1} \biggleft| \bigcap \limits_{ j \in I_{n-1I } } \Big( A_j \bigcap A_n right| \Bigright) + \bigg| = left( \sum \limits_{I_I \in 2^{n-1N'}} (-1)^{|I_{n-1}I|+12} \Bigleft| \bigcap \limits_{ j\in I_I \cup \{n\} } A_j \right| \right) </tex> <tex dpi = "130"> = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \cup left| \bigcap \limits_{ n j \} in I } A_j \Bigright| </tex>

<tex> | A |=| A_n |+\Bigg( \sum \limits_= Беспорядки =={I_{n-1}} Определение|id=идентификатор (-1необязательно)^{, пример: def1. |I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) - - \Bigg( \sum \limits_{I_{n-1}} definition='''Беспорядок''' (-1англ. ''Derangement'')^{|I_{n-— это перестановка чисел от <tex>1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ </tex> до <tex>n \} } A_j \Big| \Bigg)</tex>, в которой ни один элемент не стоит на своём месте. }}

Заметим, что <tex> === Явная формула с использованием принципа включения- \sum \limits_исключения ==={I_{n-1}} Теорема|id=идентификатор (-1необязательно)^{, пример: th1. |I_{statement= Количество беспорядков порядка <tex>n-1}|+1} \Big| \bigcap \limits_</tex> равно субфакториалу <ref>[http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B1%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB Википедия { 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_{Субфакториал]</ref> числа <tex>n-1} \cup \{ </tex> (обозначение: <tex>!n \} } A_j \Big| \</tex>) и вычисляется по формуле:

<tex dpi = "150"> !n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + \frac{n!}{n!}(-1)^{n}= \sum_{k=0}^n\frac{n!}{k!}(-1)^{k} </tex>|proof=Воспользуемся принципом включения-исключения: обозначим за <tex dpi = "130">A_i</tex> — количество перестановок из <tex dpi = "130">n</tex> элементов, в каждой из которых <tex dpi = "130">i</tex>-ый элемент стоит на своём месте. Тогдапо формуле включения-исключения имеем:

<texdpi = "140"> \Big | A |=| A_n |+\Bigg( \sum \limits_bigcap_{I_{n-1i=_1}} (-1)^n \overline{|I_{n-1A}|+1} _i \Big| = |U|-\bigcap sum \limits_{ j \in I_{n-1i} } A_j \Big| \Bigg) A_i|+ \Bigg( \sum \limits_{I_{n-1i < j}} (-1)^{|I_{n-1}|+2} A_i\Bigbigcap A_j| -\bigcap sum \limits_{ i < j\in I_{n-1< k} |A_i\cup \{ n \} } bigcap A_j \Bigbigcap A_k| \Bigg) </tex> <tex dpi = \sum \limits_{I_n} "130">+ ... +(-1)^{n}|I_n|+1} A_1 \bigcap A_2 \Big| bigcap ... \bigcap A_n | </tex>, где универсум <tex dpi = "130">U</tex> — множество из всех перестановок порядка <tex dpi = "130">n</tex>.  <tex>\limits_overline{ j \in I_n A} A_j \Big| )_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex> -ом месте.

Равенство справедливоТаким образом <tex dpi = "130">| \bigcap_{i=_1}^n \overline {A}_i |</tex> — количество всех перестановок, потому что все наборы в каждой из которых <tex>i</tex>-ый элемент <texdpi = "130"> I_n \neq</tex> можно разбить на три группы :<tex dpi = "130">i</tex>,то есть количество искомых беспорядков.

<tex dpi = "130">|A_i| = (n - 1) !</tex>, так как <tex dpi = "130">i</tex>-ая позиция занята числом <tex dpi = "130">i</tex> . <tex dpi = "130">\binom{n}{1}</tex> — количество способов выбрать одну <tex dpi = "130">i</tex>-ую позицию <tex dpi = "130"> \Rightarrow \sum \limits_{i = 1}^{n} |A_i| = \binom{n}{1} (n-1) !</tex>

2Рассмотрим <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| </tex>, где <tex dpi = "130"> 1\leqslant i_1 < i_2 < ... < i_k \leqslant n </tex>. Так как некоторые <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> заняты соответствующими числами, то количество способов расставить остальные <tex dpi = "130">n-k</tex> чисел равно <tex dpi = "130">(n-k) !</tex> . То есть <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (I_{n-1}k)! </tex> Это означает, что в наборе точно '''не''' будет присутствовать индекс Количество всех способов выбрать <texdpi = "130"> n k</tex>позиций <tex dpi = "130">i_1, а будут все различные варианты индексов остальных множествi_2, т.е. . , i_k </tex> I_равно <tex dpi = "130">\binom{n-1}{k} </tex>. Таким образом получаем, что:

3) <texdpi = "130"> (\sum \limits_{1\leqslant i_1 < i_2 < ... < i_k \leqslant n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = \binom{n; I_}{k} \cdot(n-1}k) </tex> Аналогично предыдущему, только в наборе будет индекс <tex> n ! </tex>

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

Значит для <texdpi = "130">~l| \bigcap_{i=_1}^n \overline{A}_i | =n! + \sum \limits_{k = 1}^{n} (-1)^{k}\binom{n}{k} \cdot (n - k)!.</tex> мы доказали Раскрывая <tex dpi = "140">\binom{n}{k}</tex> по общеизвестной формуле, что равенство верно. Значит индукционный переход доказанполучим требуемое выражение, то теорема доказанаесть количество беспорядков порядка <tex dpi = "130">n</tex>.