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

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

Случай для двух множеств

Для случая из двух множеств [math]A, B[/math] формула включения-исключения имеет следующий вид:

[math] | A \cup B | = | A | + | B | - | A \cap B |[/math]

В силу того, что в сумме [math]| A | + | B |[/math] элементы пересечения [math]A \cap B[/math] учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера—Венна для двух множеств, приведенной на рисунке справа.

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Беспорядки

Беспорядком в комбинаторике называется перестановка чисел от [math]1[/math] до [math]n[/math], в которой ни один элемент не стоит на своём месте.

Теорема:

Количество всех беспорядков порядка [math]n[/math] или субфакториалом числа [math]n[/math] (обозначение: ![math]n[/math]) может быть вычислено по формуле:

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

Воспользуемся принципом включения-исключения: обозначим за — количество перестановок из [math]n[/math] элементов, в каждой из которых [math]i[/math]-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:

1)

ИЛИ

2)

Данные формулы являются эквивалентными. Действительно, если некоторое множество [math]\mathbf{S}[/math] являются подмножествами некоторого множества , то, в силу законов де Моргана

[math]|[/math] [math]\mathbf{S}[/math] [math]|[/math] [math]=[/math] [math]|[/math] [math]|[/math] — [math]|[/math] [math]\lnot[/math][math]\mathbf{S}[/math] [math]|[/math].

В данной задаче множество — есть количество перестановок из [math]n[/math] элементов, т.е. [math]n![/math]. Верхнее подчеркивание или символ [math]\lnot[/math] перед [math]\mathbf{S}[/math] означает дополняющее множество до [math]\Rightarrow[/math] [math]\lnot[/math] — количество перестановок, где [math]i[/math]-ый элемент стоит НЕ на своём [math]i[/math]-ом месте.

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

[math]=[/math] [math]n![/math].

|| — количество перестановок с уже занятой позицией [math]i[/math] [math]\Rightarrow[/math] || [math]=[/math] [math](n - 1)![/math]. Суммирование ведется по всем [math]i[/math] [math]\Rightarrow[/math] [math]\sum \limits_{i = 1}^{n} |\lnot [/math][math]|[/math] [math]=[/math] [math]\binom{n}{1}[/math][math]\cdot[/math][math](n-1)![/math]

Производя аналогичные рассуждения, получаем, что сумма пересечений некоторых [math]k[/math] множеств (то есть сумма всеx перестановки при некоторых зафиксированных [math]k[/math] позициях) — есть [math](n-k)![/math]. Количество способов выбрать [math]k[/math] позиций — [math]\binom{n}{k}[/math] [math]\Rightarrow[/math] Количество перестановок с [math]k[/math] неподвижными точками: [math]\binom{n}{k}[/math][math]\cdot[/math][math](n-k)![/math]

[math]=[/math] [math]n![/math] [math]+[/math] [math]\sum \limits_{i = 1}^{n} (-1)^{n}(n - k)![/math][math]\cdot[/math][math]\binom{n}{k}[/math]

Раскрывая [math]\binom{n}{k}[/math] по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка [math]n[/math].