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

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

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

Для случая из двух множеств [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]

Беспорядок

Определение:

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

Определение:

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

Теорема:

[math] !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!} [/math]

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

[math]\triangleright[/math]

Воспользуемся принципом включения-исключения: обозначим за [math]A_i[/math] — количество перестановок из [math]n[/math] элементов, в каждой из которых [math]i[/math]-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем: 1) [math]\Big |\bigcup_{i=_1}^n A_i \Big| = \sum \limits_{i} |A_i|-\sum \limits_{i\lt j} |A_i\bigcap A_j|+\sum \limits_{i\lt j\lt k} |A_i\bigcap A_j\bigcap A_k|[/math] [math]- ... +(-1)^{n-1}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | [/math] 2) [math]\Big |\bigcap_{i=_1}^n \lnot A_i \Big| = |U|-\sum \limits_{i} |A_i|+\sum \limits_{i\lt j} |A_i\bigcap A_j|-\sum \limits_{i\lt j\lt k} |A_i\bigcap A_j\bigcap A_k|[/math] [math]+ ... +(-1)^{n}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | [/math] Данные формулы эквивалентны. Действительно, если некоторое множество [math]S[/math] является подмножеством некоторого множества [math]U[/math], то, в силу законов де Моргана: [math]|S| = |U| - |\lnot S|[/math], где [math]U[/math] — универсальное множество. [math]|U| = n![/math], т.е. количество перестановок из [math]n[/math] элементов. Откуда следует, что [math]\lnot[/math][math]A_i[/math] — количество перестановок, в каждой из которых [math]i[/math]-ый элемент стоит не на своём [math]i[/math]-ом месте. Таким образом [math]| \bigcap_{i=_1}^n \lnot A_i |[/math] — количество всех перестановок, в каждой из которых [math]i[/math]-ый элемент [math]\neq[/math] [math]i[/math],т.е. количество искомых беспорядков. [math]|A_i| = (n - 1)![/math] (т.к. [math]i[/math]-ая позиция занята числом [math]i[/math]). [math]\binom{n}{1}[/math] — количество способов выбрать одну [math]i[/math]-ую позицию [math]\Rightarrow[/math] [math]\sum \limits_{i = 1}^{n} |A_i| = [/math] [math]\binom{n}{1}[/math][math] (n-1)![/math] Рассмотрим [math] |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| [/math], где [math] 1\le i_1 \lt i_2 \lt ... \lt i_k \le n [/math]. Так как некоторые [math]k[/math] позиций [math]i_1, i_2, ... , i_k [/math] заняты соответствующими числами, то количество способов расставить остальные [math]n-k[/math] чисел равно [math](n-k)![/math]. То есть [math] |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! [/math] Количество всех способов выбрать [math]k[/math] позиций [math]i_1, i_2, ... , i_k [/math] равно [math]\binom{n}{k} [/math]. Таким образом получаем, что: [math]\sum \limits_{1\le i_1 \lt i_2 \lt ... \lt i_k \le n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = [/math] [math]\binom{n}{k}[/math][math]\cdot(n-k)![/math] Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем: [math]| \bigcap_{i=_1}^n \lnot A_i | = n! + \sum \limits_{k = 1}^{n} (-1)^{k}(n - k)! \cdot[/math][math]\binom{n}{k}[/math] Раскрывая [math]\binom{n}{k}[/math] по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка [math]n[/math].

[math]\triangleleft[/math]

Ссылки

• Википедия — Беспорядок
• Википедия — Субфакториал

Литература

Виленкин Н.Я. Комбинаторика