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

2015-01-14T10:13:45Z

81.28.160.116:

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

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

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

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

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

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

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

'''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} + (-1) {t \choose 0} = -\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 dpi = "130">~| B \cap A_n |</tex>:

Очевидно, что <tex dpi = "130"> 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 dpi = "130"> (**) </tex> имеем, что <tex dpi = "130"> |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 dpi = "130">(*)</tex>:

<tex dpi = "130"> | 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 dpi = "130"> =| 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 dpi = "130"> | 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 dpi = "130"> = \sum \limits_{I \in 2^N} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I } A_j \right| </tex>

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

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

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

== Беспорядки ==
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition='''Беспорядок''' (англ. ''Derangement'') — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.
}}
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement= Количество беспорядков порядка <tex>n</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 Википедия {{---}} Субфакториал]</ref> числа <tex>n</tex> (обозначение: <tex>!n</tex>) и вычисляется по формуле:

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

<tex dpi = "140"> \Big |\bigcap_{i=_1}^n \overline{A}_i \Big| = |U|-\sum \limits_{i} |A_i|+\sum \limits_{i < j} |A_i\bigcap A_j|-\sum \limits_{i < j < k} |A_i\bigcap A_j\bigcap A_k|</tex> <tex dpi = "130">+ ... +(-1)^{n}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>, где универсум <tex dpi = "130">U</tex> — множество из всех перестановок порядка <tex dpi = "130">n</tex>.

<tex>\overline{A}_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.

Таким образом <tex dpi = "130">| \bigcap_{i=_1}^n \overline {A}_i |</tex> — количество всех перестановок, в каждой из которых <tex>i</tex>-ый элемент <tex dpi = "130">\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>

Рассмотрим <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}| = (n - k)! </tex> Количество всех способов выбрать <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> равно <tex dpi = "130">\binom{n}{k} </tex>. Таким образом получаем, что:

<tex dpi = "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}{k} \cdot(n-k)! </tex>

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

<tex dpi = "130">| \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>.
}}

== Рекурсивная формула нахождения количества беспорядков ==

{{Утверждение
|statement =
Количество беспорядков удовлетворяет рекурсивным соотношениям:

<tex dpi = "140"> d(n)=(n-1)[d(n-1)+d(n-2)] </tex>

и

<tex dpi = "140"> d(n)=n \times d(n-1)+(-1)^{n} </tex>,

где <tex dpi = "140"> d(1)=0 </tex>, а <tex dpi = "140"> d(2)=1 </tex>
|proof =
1) Сначала докажем второе соотношение:

Так как <tex dpi = "140"> d(n)=!n </tex>, то можно переписать эту формулу, как <tex dpi = "140"> !n=n!(n-1)+(-1)^{n} </tex>
По формуле субфакториала <tex dpi = "140"> !n=n!(\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!} + \frac {(-1)^{n}}{n!})=n!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}+(-1)^{n}=n \times !(n-1)+(-1)^{n}</tex>

2) Теперь, используя вторую формулу, докажем первую:

}}
== См. также ==
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]

==Примечания==

<references />
== Источники информации ==
* [[wikipedia:ru:Беспорядок_(перестановка)|Википедия — Беспорядок]]
* [http://en.wikipedia.org/wiki/Derangement Wikipedia — Derangement]
* Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика, Изд. 4-е, исправленное - МЦНМО, 2013 ISBN 978-5-4439-0052-0
* Р. Стенли, Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.

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

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

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