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

2012-12-13T20:00:35Z

Павел:

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

[[Файл:пересечение двух множеств.svg.png|thumb|right|Случай для двух множеств]]

Для случая из двух множеств <tex>A, B</tex> формула включения-исключения имеет следующий вид:
<center>
<tex> | A \cup B | = | A | + | B | - | A \cap B |</tex>
</center>
В силу того, что в сумме <tex>| A | + | B |</tex> элементы пересечения <tex>A \cap B</tex> учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.

Для случая с большим количеством рассматриваемых множеств <tex> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.

{{Теорема
|statement=Пусть <tex> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения{{---}}исключения: <center> <tex> | A | = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex> </center>
Причем <tex> N = \{ 1,2, \ldots ,n \} </tex>. Здесь за <tex> 2^N </tex> обозначим множество всех непустых подмножеств <tex> N </tex>.

||proof=
Приведем два разноплановых доказательства теоремы.

'''I. Комбинаторное доказательство теоремы.'''

Рассмотрим некоторый элемент <tex> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <tex> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <tex> x </tex> в правую часть формулы.

<tex>k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} + (-1) {t \choose 0} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} </tex><tex> = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} </tex>

Докажем, что <tex> \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0</tex>

В силу того, что <tex> (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> 0 = (1 + (-1)) ^ t = \sum \limits_{j = 0}^{t} (-1)^j {t \choose j}</tex>, то равенство доказано.

Таким образом, <tex> k = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j = 1 - 0 = 1</tex>, то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана.

'''II. Доказательство теоремы по индукции.'''

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

Предположим, что для <tex>~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex>~l=n</tex>

Пусть <tex> A </tex> {{---}} объединение <tex>~n</tex> множеств. Очевидно, что <tex> A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n </tex>. Пусть <tex> B = \bigcup \limits_{i=1}^{n-1}A_i </tex>; <tex>N' = \{ 1,2, \ldots ,n-1 \} </tex>.

Исходя из предположения индукции, имеем, что
<tex> | B | = \sum \limits_{I \in 2^{N'}} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex>

Кроме того, так как формула верна для <tex>~l=2</tex> (из базы индукции), то верно равенство <tex> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>. Найдем <tex>~| B \cap A_n |</tex>:

Очевидно, что <tex> B \cap A_n = \left( \bigcup \limits_{i=1}^{n-1}A_i \right) \cap A_n = \bigcup \limits_{i=1}^{n-1} \left( A_i \cap A_n \right) (**)</tex>

Опираясь на предположение индукции и равенство <tex> (**) </tex> имеем, что <tex> |B \cap A_n| = \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| </tex>

Подставим полученные значения в <tex>(*)</tex>:

<tex> | 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)</tex> <tex> =| 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)
</tex>

Докажем, что <tex> | 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)
</tex> <tex> = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex>

Равенство справедливо, потому что все наборы <tex> I \in 2^N </tex> можно разбить на две группы :

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

Как видно из равенства, первое и третье слагаемое "отвечают" за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и <tex>|A| = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex> .
Таким образом, для <tex>~l=n</tex> мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.
}}

== Количество беспорядков ==
Попробуем решить следующую задачу: количество перестановок чисел от 1 до n, при которых ни один элемент не стоит на своём месте. Каждая такая перестановка в комбинаторике называется '''беспорядком'''.
Количество всех беспорядков порядка <tex>n</tex> может быть вычислено с помощью принципа включения-исключения и дается выражением:

[[Файл:Formula.png]]

которое называется субфакториалом числа n и обозначается, как !n.

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

Обозначим за [[Файл:Formula4.png]] - количество перестановок из n элементов, в которых на i-ой позиции стоит i.
тогда по формуле включения-исключения имеем:

1) [[Файл:Formula2.png]]

ИЛИ

2) [[Файл:Formula3.png]]

Данные формулы эквивалентны! Действительно, если множества [[Файл:Formula4.png]] являются подмножествами некоторого множества [[Файл:Formula5.png]], то в силу правил де Моргана [[Файл:Formula6.png]].

В нашей задаче множество [[Файл:Formula5.png]] - есть количество перестановок из n элементов, т.е. n!. Черта над множеством [[Файл:Formula4.png]] означает дополняющее множество до [[Файл:Formula5.png]] или, в силу определения [[Файл:Formula4.png]], означает количество перестановок, где на i-ой позиции '''НЕ''' i.

Таким образом величина в левой части формулы 2) - есть количество перестановок, где на 1-ой позици '''НЕ''' 1, на 2-ой позици '''НЕ''' 2 и т.д. Т.е. количество искомых беспорядков! Осталось определить величины в правой части:

[[Файл:Formula5.png]] = <tex>n!</tex>

|[[Файл:Formula4.png]]| можно получить зафиксировав число i на соответствующей ей позиции i, а остальные позиции заполнив как угодно остальными числами => |[[Файл:Formula4.png]]| = <tex>(n - 1)!</tex>. Суммирование ведется по всем i => [[Файл:Formula8.png]]
Аналогичными рассуждениями получаем, что сумма пересечений некоторых k множеств - есть все перестановки при зафиксированных k позициях, т.е. [[Файл:Formula7.png]] х <tex>(n - k)!</tex>. Таким образом приходим к формуле:

[[Файл:Formula9.png]] = <tex>n!</tex> + [[Файл:Formula10.png]] х [[Файл:Formula7.png]] х <tex>(n - k)!</tex>

Раскрывая [[Файл:Formula7.png]] по общеизвестной формуле, получим требуемое выражение, т.е. количество беспорядков порядка <tex>n</tex>.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Файл:Formula10.png

2012-12-13T19:46:58Z

Павел:

Файл:Formula9.png

2012-12-13T19:45:11Z

Павел:

Файл:Formula7.png

2012-12-13T19:35:19Z

Павел:

Файл:Formula8.png

2012-12-13T19:32:18Z

Павел:

Файл:Formula4.png

2012-12-13T18:55:30Z

Павел:

Файл:Formula6.png

2012-12-13T18:54:26Z

Павел:

Файл:Formula5.png

2012-12-13T18:47:43Z

Павел:

Файл:Formula3.png

2012-12-13T18:40:20Z

Павел:

Файл:Formula2.png

2012-12-13T18:27:29Z

Павел:

Файл:Formula.png

2012-12-13T15:27:42Z

Павел:

Викиконспекты - Вклад участника [ru]

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

Файл:Formula10.png

Файл:Formula9.png

Файл:Formula7.png

Файл:Formula8.png

Файл:Formula4.png

Файл:Formula6.png

Файл:Formula5.png

Файл:Formula3.png

Файл:Formula2.png

Файл:Formula.png