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

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

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

Например, в случае двух множеств $A,B$$A,B$ формула включений-исключений имеет вид:

$|A\cup <!--\; \cup \; -->B|=|A|+|B|-<!--\; -\; -->|A\cap <!--\; \cap \; -->B|.$$|A\cup B|=|A|+|B|-|A\cap B|.$

В сумме $|A|+|B|$$|A|+|B|$ элементы пересечения $A\cap <!--\; \cap \; -->B$$A\cap B$ учтены дважды, и чтобы компенсировать это мы вычитаем $|A\cap <!--\; \cap \; -->B|$$|A\cap B|$ из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае $n>2$$n>2$ множеств процесс нахождения количества элементов объединения $A_1\cup <!--\; \cup \; -->A_2\cup <!--\; \cup \; -->\dots <!--\; \dots \; -->\cup <!--\; \cup \; -->A_n$$A_{1}\cup A_{2}\cup \ldots \cup A_{n}$ состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

ФормулировкаПравить

Формулу включений-исключений можно сформулировать в разных формах.

В терминах множествПравить

Пусть $A_1,A_2,\dots <!--\; \dots \; -->,A_n$$A_{1},A_{2},\ldots ,A_{n}$  — конечные множества. Формула включений-исключений утверждает:

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggl |}=\sum _{i}|A_{i}|-\sum _{i<j}|A_{i}\cap A_{j}|+\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|-\ldots +(-1)^{n-1}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$ 

При $n=2$$n=2$  получаем формулу для двух множеств, приведенную выше.

В терминах свойствПравить

Принцип включений-исключений часто приводят в следующей альтернативной формулировке . Пусть дано конечное множество $U$$U$ , состоящее из $N$$N$  элементов, и пусть имеется набор свойств $a_1,\dots <!--\; \dots \; -->,a_n$$a_1, \ldots , a_n$ . Каждый элемент множества $U$$U$  может обладать или не обладать любым из этих свойств. Обозначим через $N(a_{i_1}\dots <!--\; \dots \; -->a_{i_s})$$N(a_{i_{1}}\ldots a_{i_{s}})$  количество элементов, обладающих свойствами $a_{i_1},\dots <!--\; \dots \; -->,a_{i_s}$$a_{i_{1}},\ldots ,a_{i_{s}}$  (и, может быть, некоторыми другими). Также через $N({\stackrel{¯<!--\; ¯\; -->}{a}}_{i_1}\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_{i_s})$$N({\overline {a}}_{i_{1}}\ldots {\overline {a}}_{i_{s}})$  обозначим количество элементов, не обладающих ни одним из свойств $a_{i_1},\dots <!--\; \dots \; -->,a_{i_s}$$a_{i_{1}},\ldots ,a_{i_{s}}$ . Тогда имеет место формула:

$N({\overline {a}}_{1}\ldots {\overline {a}}_{n})=N-\sum _{i}N(a_{i})+\sum _{i<j}N(a_{i}a_{j})-\sum _{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n}N(a_{1}\ldots a_{n}).$ 

Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств. Действительно, если множества $A_i$$A_{i}$  являются подмножествами некоторого множества $U$$U$ , то в силу правил де Моргана $|{\bigcup <!--\; \bigcup \; -->}_i{A}_i|=|U|-<!--\; -\; -->|{\bigcap <!--\; \bigcap \; -->}_i\stackrel{¯<!--\; ¯\; -->}{A_i}|$$|\bigcup \nolimits _{i}A_{i}|=|U|-|\bigcap \nolimits _{i}{\overline {A_{i}}}|$  (черта над множеством — дополнение в множестве $U$$U$ ), и формулу включений-исключений можно переписать так:

${\biggl |}\bigcap _{i=1}^{n}{\overline {A_{i}}}{\biggl |}=|U|-\sum _{i}|A_{i}|+\sum _{i<j}|A_{i}\cap A_{j}|-\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+\ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$ 

Если теперь вместо «элемент $x$$x$  принадлежит множеству $A_i$$A_{i}$ » говорить «элемент $x$$x$  обладает свойством $a_i$$a_{i}$ », то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через $N(r)$$N(r)$  количество элементов, обладающих в точности $r$$r$  свойствами из набора $a_1,\dots <!--\; \dots \; -->,a_n$$a_1, \ldots , a_n$ .Тогда формулу включений-исключений можно переписать в следующей форме:

$N(0)=\sum _{k=0}^{n}(-1)^{k}\sum _{i_{1}<\ldots <i_{k}}N(i_{1},\ldots ,i_{k}).$ 

ДоказательствоПравить

Существует несколько доказательств формулы включений-исключений.

Доказательство по индукции

Формулу включений-исключений можно доказать по индукции .

При $n=1$$n=1$  формула включений-исключений тривиальна:

$N(\stackrel{¯<!--\; ¯\; -->}{a})=N-<!--\; -\; -->N(a).$$N({\overline {a}})=N-N(a).$ 

Пусть формула верна для $n=m$$n=m$ , докажем её для $n=m+1$$n=m+1$ .

Пусть каждый элемент множества $U$$U$  может обладать или не обладать любым из свойств $a_1,\dots <!--\; \dots \; -->,a_m,a_{m+1}$$a_{1},\ldots ,a_{m},a_{m+1}$ . Применим формулу включений-исключений для свойств $a_1,\dots <!--\; \dots \; -->,a_m$$a_{1},\ldots ,a_{m}$ :

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m})=N-\sum _{i\leq m}N(a_{i})+\sum _{i<j\leq m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).$ 

Теперь применим формулу для свойств $a_1,\dots <!--\; \dots \; -->,a_m$$a_{1},\ldots ,a_{m}$  к множеству $N(a_{m+1})$$N(a_{m+1})$  объектов, для которых выполнено свойство $a_{m+1}$$a_{m+1}$ :

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1})=N(a_{m+1})-\sum _{i\leq m}N(a_{i}a_{m+1})+\sum _{i<j\leq m}N(a_{i}a_{j}a_{m+1})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).$ 

Наконец, применим формулу для одного свойства $a_{m+1}$$a_{m+1}$  к совокупности $N({\stackrel{¯<!--\; ¯\; -->}{a}}_1\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_m)$$N({\overline {a}}_{1}\ldots {\overline {a}}_{m})$ , объектов, которые не обладают свойствами $a_1,\dots <!--\; \dots \; -->,a_m$$a_{1},\ldots ,a_{m}$ :

$N({\stackrel{¯<!--\; ¯\; -->}{a}}_1\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_m{\stackrel{¯<!--\; ¯\; -->}{a}}_{m+1})=N({\stackrel{¯<!--\; ¯\; -->}{a}}_1\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_m)-<!--\; -\; -->N({\stackrel{¯<!--\; ¯\; -->}{a}}_1\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_m{a}_{m+1}).$$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}{\overline {a}}_{m+1})=N({\overline {a}}_{1}\ldots {\overline {a}}_{m})-N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1}).$ 

Комбинируя выписанные три формулы, получим формулу включений-исключений для $m+1$$m+1$  свойств $a_1,\dots <!--\; \dots \; -->,a_{m+1}$$a_{1},\ldots ,a_{m+1}$ . Что и требовалось доказать. ■

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

Рассмотрим произвольный элемент $e\in <!--\; \in \; -->U$$e\in U$  и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений.

Если элемент $e$$e$  не обладает ни одним из свойств $a_i$$a_{i}$ , то в правой части формулы он учитывается ровно 1 раз (в члене $N$$N$ ).

Пусть элемент $e$$e$  обладает в точности $r$$r$  свойствами, скажем $a_{j_1},\dots <!--\; \dots \; -->,a_{j_r}$$a_{j_{1}},\ldots ,a_{j_{r}}$ . Он дает по 1 в тех слагаемых суммы $\sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})$ , для которых $\{i_1,\dots <!--\; \dots \; -->,i_s\}$$\{i_{1},\ldots ,i_{s}\}$  есть подмножество $\{j_1,\dots <!--\; \dots \; -->,j_r\}$$\{j_{1},\ldots ,j_{r}\}$ , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний $(\genfrac{}{}{0ex}{}{r}{s})$${\tbinom {r}{s}}$ . Следовательно, вклад элемента $e$$e$  в правую часть равен

$1-<!--\; -\; -->(\genfrac{}{}{0ex}{}{r}{1})+(\genfrac{}{}{0ex}{}{r}{2})-<!--\; -\; -->\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^r(\genfrac{}{}{0ex}{}{r}{r}).$$1-{r \choose 1}+{r \choose 2}-\ldots +(-1)^{r}{r \choose r}.$ 

При $s>r$$s>r$  числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

$\underset{s=0}{\overset{r}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^s(\genfrac{}{}{0ex}{}{r}{s})=(1+(-<!--\; -\; -->1){)}^r=0.$$\sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.$ 

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств $a_i$$a_{i}$ , то есть $N({\stackrel{¯<!--\; ¯\; -->}{a}}_1\dots <!--\; \dots \; -->{\stackrel{¯<!--\; ¯\; -->}{a}}_n)$$N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$ . Что и требовалось доказать. ■

Доказательство через индикаторные функции

Пусть $A_i$$A_{i}$  — произвольные (не обязательно конечные) множества, являющиеся подмножествами некоторого множества $U$$U$ , и пусть ${\mathbf{1}}_{A_i}$$\mathbf {1} _{A_{i}}$  — индикаторные функции $A_i$$A_{i}$  (или, эквивалентно, свойств $a_i$$a_{i}$ ).

Индикаторная функция их дополнений $\stackrel{¯<!--\; ¯\; -->}{A_i}$${\overline {A_{i}}}$  равна

${\mathbf{1}}_{\stackrel{¯<!--\; ¯\; -->}{A_i}}=1-<!--\; -\; -->{\mathbf{1}}_{A_i},$$\mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},$ 

а индикаторная функция пересечения дополнений:

${\mathbf{1}}_{{\cap <!--\; \cap \; -->}_i\stackrel{¯<!--\; ¯\; -->}{A_i}}=\underset{i}{\prod <!--\; \prod \; -->}(1-<!--\; -\; -->{\mathbf{1}}_{A_i}).$$\mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).$ 

Раскрывая скобки в правой части и ещё раз используя тот факт, что индикаторная функция пересечения множеств равна произведению их индикаторных функций, получаем:

$\mathbf {1} _{\bigcap _{i}{\overline {A_{i}}}}=1-\sum _{i}\mathbf {1} _{A_{i}}+\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}-\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n}\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$ 

Это соотношение — одна из форм принципа включений-исключений. Оно выражает собой логическое тождество и верно для произвольных множеств $A_i$$A_{i}$ . В случае конечных множеств $A_i$$A_{i}$  (и, соответственно, в предположении конечности множества $U$$U$ ), просуммировав это соотношение по всем $x\in <!--\; \in \; -->U$$x\in U$  и воспользоваться тем, что для произвольного подмножества $A\subset <!--\; \subset \; -->U$$A\subset U$  его мощность равна

$|A|=\underset{x\in <!--\; \in \; -->U}{\sum <!--\; \sum \; -->}{\mathbf{1}}_A(x),$$|A|=\sum _{x\in U}\mathbf {1} _{A}(x),$ 

получим формулировку принципа включений-исключений в терминах мощностей множеств (или в терминах свойств). ■

Топологическое доказательство

Снабдим множества $A_i$$A_{i}$  дискретной топологией. В таком случае $H^k(A_i)=0$$H^{k}(A_{i})=0$  при $k>0$$k>0$ , а при $k=0$$k=0$  имеет место тождество $\dim <!--\; \; -->H^0(A_i)=|A_i|.$$\dim H^{0}(A_{i})=|A_{i}|.$  В случае двух множеств $A_1$$A_{1}$  и $A_2$$A_{2}$  можно воспользоваться точной последовательностью Майера — Вьеториса, которая, учитывая зануление старших когомологий, будет выглядеть как: $0\to <!--\; \to \; -->H^0(A_1\cup <!--\; \cup \; -->A_2)\to <!--\; \to \; -->H^0(A_1)\oplus <!--\; \oplus \; -->H^0(A_2)\to <!--\; \to \; -->H^0(A_1\cap <!--\; \cap \; -->A_2)\to <!--\; \to \; -->0.$$0\to H^{0}(A_{1}\cup A_{2})\to H^{0}(A_{1})\oplus H^{0}(A_{2})\to H^{0}(A_{1}\cap A_{2})\to 0.$  Значит, имеет место тождество $\dim <!--\; \; -->H^0(A_1)\oplus <!--\; \oplus \; -->H^0(A_2)=\dim <!--\; \; -->H^0(A_1\cup <!--\; \cup \; -->A_2)+\dim <!--\; \; -->H^0(A_1\cap <!--\; \cap \; -->A_2),$$\dim H^{0}(A_{1})\oplus H^{0}(A_{2})=\dim H^{0}(A_{1}\cup A_{2})+\dim H^{0}(A_{1}\cap A_{2}),$  или, если переписать его, $|A_1|+|A_2|=|A_1\cup <!--\; \cup \; -->A_2|+|A_1\cap <!--\; \cap \; -->A_2|,$$|A_{1}|+|A_{2}|=|A_{1}\cup A_{2}|+|A_{1}\cap A_{2}|,$  что эквивалентно формуле включений-исключений.

В случае более чем двух множеств для доказательства формулы включений-исключений вместо точной последовательности Майера — Вьеториса надо написать некоторую спектральную последовательность (а именно спектральную последовательность Лере^[en] для отображения проекции из несвязного объединения $A_i$$A_{i}$  в их объединение), и так же вычислить ранги групп когомологий. ■

ПрименениеПравить

Задача о беспорядкахПравить

Основная статья: Задача о беспорядках

Классический пример использования формулы включений-исключений — задача о беспорядках. Требуется найти число перестановок $(p_1,p_2,\dots <!--\; \dots \; -->,p_n)$$(p_{1},p_{2},\ldots ,p_{n})$  множества $\{1,2,\dots <!--\; \dots \; -->,n\}$$\{1,2,\ldots ,n\}$  таких что $p_i\ne <!--\; \ne \; -->i$$p_{i}\neq i$  для всех $i$$i$ . Такие перестановки называются беспорядками.

Пусть $U$$U$  — множество всех перестановок $p$$p$  и пусть свойство $a_i$$a_{i}$  перестановки выражается равенством $p_i=i$$p_{i}=i$ . Тогда число беспорядков есть $N({\stackrel{¯<!--\; ¯\; -->}{a}}_1,{\stackrel{¯<!--\; ¯\; -->}{a}}_2,\dots <!--\; \dots \; -->,{\stackrel{¯<!--\; ¯\; -->}{a}}_n)$$N({\overline {a}}_{1},{\overline {a}}_{2},\ldots ,{\overline {a}}_{n})$ . Легко видеть, что $N(a_{i_1},\dots <!--\; \dots \; -->,a_{i_s})=(n-<!--\; -\; -->s)!$$N(a_{i_{1}},\ldots ,a_{i_{s}})=(n-s)!$  — число перестановок, оставляющих на месте элементы $i_1,\dots <!--\; \dots \; -->,i_s$$i_{1},\ldots ,i_{s}$ , и таким образом сумма $\sum <!--\; \sum \; -->N(a_{i_1},a_{i_2},\dots <!--\; \dots \; -->,a_{i_s})$$\sum N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})$  содержит $(\genfrac{}{}{0ex}{}{n}{s})$${\tbinom {n}{s}}$  одинаковых слагаемых. Формула включений-исключений дает выражение для числа $D_n$$D_{n}$  беспорядков:

$D_n=n!-<!--\; -\; -->(\genfrac{}{}{0ex}{}{n}{1})(n-<!--\; -\; -->1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-<!--\; -\; -->2)!-<!--\; -\; -->\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{n}{n})0!.$$D_{n}=n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n}0!.$ 

Это соотношение можно преобразовать к виду

$D_n=n!\left(1-<!--\; -\; -->\frac{1}{1!}+\frac{1}{2!}-<!--\; -\; -->\dots <!--\; \dots \; -->+\frac{(-<!--\; -\; -->1{)}^n}{n!}\right).$$D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n}}{n!}}\right).$ 

Нетрудно видеть, что выражение в скобках является частичной суммой ряда $\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{(-<!--\; -\; -->1{)}^k}{k!}=e^{-<!--\; -\; -->1}$$\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$ . Таким образом, с хорошей точностью число беспорядков составляет $1/e$$1/e$  долю от общего числа $P_n=n!$$P_{n}=n!$  перестановок:

$D_n/P_n\approx <!--\; \approx \; -->1/e.$$D_{n}/P_{n}\approx 1/e.$ 

Вычисление функции ЭйлераПравить

Основная статья: Функция Эйлера

Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера $\mathrm{\phi <!--\; \phi \; -->}(n)$$\varphi (n)$ , выражающей количество чисел из $\{1,2,\dots <!--\; \dots \; -->,n\}$$\{1,2,\ldots ,n\}$ , взаимно простых с $n$$n$ .

Пусть каноническое разложение числа $n$$n$  на простые множители имеет вид

$n=p_1^{s_1}{p}_2^{s_2}\dots <!--\; \dots \; -->p_k^{s_k}.$$n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.$ 

Число $m\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->n\}$$m\in \{1,\ldots n\}$  взаимно просто с $n$$n$  тогда и только тогда, когда ни один из простых делителей $p_i$$p_{i}$  не делит $m$$m$ . Если теперь свойство $a_i$$a_{i}$  означает, что $p_i$$p_{i}$  делит $m$$m$ , то количество чисел взаимно простых с $n$$n$  есть $N({\stackrel{¯<!--\; ¯\; -->}{a}}_1,\dots <!--\; \dots \; -->,{\stackrel{¯<!--\; ¯\; -->}{a}}_k)$$N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})$ .

Количество $N(a_{i_1},\dots <!--\; \dots \; -->,a_{i_s})$$N(a_{i_{1}},\ldots ,a_{i_{s}})$  чисел, обладающих свойствами $a_{i_1},\dots <!--\; \dots \; -->,a_{i_s}$$a_{i_{1}},\ldots ,a_{i_{s}}$  равно $n/p_{i_1}\dots <!--\; \dots \; -->p_{i_s}$$n/p_{i_{1}}\ldots p_{i_{s}}$ , поскольку $p_{i_1}|m,\dots <!--\; \dots \; -->,p_{i_s}|m\iff <!--\; \iff \; -->p_{i_1}\dots <!--\; \dots \; -->p_{i_s}|m$$p_{i_{1}}|m,\ldots ,p_{i_{s}}|m\Leftrightarrow p_{i_{1}}\ldots p_{i_{s}}|m$ .

По формуле включений-исключений находим

$\mathrm{\phi <!--\; \phi \; -->}(n)=n-<!--\; -\; -->\underset{i}{\sum <!--\; \sum \; -->}n/p_i+\underset{i,j}{\sum <!--\; \sum \; -->}n/p_i{p}_j-<!--\; -\; -->\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^{k}n/p_1\dots <!--\; \dots \; -->p_k.$$\varphi (n)=n-\sum _{i}n/p_{i}+\sum _{i,j}n/p_{i}p_{j}-\ldots +(-1)^{k}n/p_{1}\ldots p_{k}.$ 

Эта формула преобразуется к виду:

$\mathrm{\phi <!--\; \phi \; -->}(n)=n\underset{i=1}{\overset{k}{\prod <!--\; \prod \; -->}}\left(1-<!--\; -\; -->\frac{1}{p_i}\right).$$\varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).$ 

Вариации и обобщенияПравить

Принцип включения-исключения для вероятностейПравить

Пусть $(\mathrm{\Omega <!--\; \Omega \; -->},\mathfrak{F},\mathcal{P})$$(\Omega ,{\mathfrak {F}},{\mathcal {P}})$  — вероятностное пространство. Тогда для произвольных событий $A_1,A_2,\dots <!--\; \dots \; -->,A_n$$A_{1},A_{2},\ldots ,A_{n}$  справедлива формула

${\mathcal {P}}{\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}{\mathcal {P}}(A_{i})-\sum _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\sum _{i<j<k}{\mathcal {P}}(A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,{\mathcal {P}}\left(\bigcap _{i=1}^{n}A_{i}\right).$ 

Эта формула выражает принцип включений-исключений для вероятностей. Её можно получить из принципа включений-исключений в форме индикаторных функций:

$\mathbf {1} _{\bigcup _{i}A_{i}}=\sum _{i}\mathbf {1} _{A_{i}}-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$ 

Пусть $A_i$$A_{i}$  — события вероятностного пространства $(\mathrm{\Omega <!--\; \Omega \; -->},\mathfrak{F},\mathcal{P})$$(\Omega ,{\mathfrak {F}},{\mathcal {P}})$ , то есть $A_i\in <!--\; \in \; -->\mathfrak{F}$$A_{i}\in {\mathfrak {F}}$ . Возьмем математическое ожидание $\mathcal{M}$${\mathcal {M}}$  от обеих частей этого соотношения, и, воспользовавших линейностью математического ожидания и равенством $\mathcal{P}(A)=\mathcal{M}({\mathbf{1}}_A)$${\mathcal {P}}(A)={\mathcal {M}}(\mathbf {1} _{A})$  для произвольного события $A\in <!--\; \in \; -->\mathfrak{F}$$A\in {\mathfrak {F}}$ , получим формулу включения-исключения для вероятностей.

Принцип включений-исключений в пространствах с меройПравить

Пусть $(X,\mathfrak{S},\mathrm{\mu <!--\; \mu \; -->})$$(X,{\mathfrak {S}},\mu )$  — пространство с мерой. Тогда для произвольных измеримых множеств $A_i$$A_{i}$  конечной меры $\mu (A_{i})<\infty$  имеет место формула включений-исключений:

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}\mu (A_{i})-\sum _{i<j}\mu (A_{i}\cap A_{j})+\sum _{i<j<k}\mu (A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,\mu \left(\bigcap _{i=1}^{n}A_{i}\right).$ 

Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: $\mathrm{\mu <!--\; \mu \; -->}(A)=\mathcal{P}(A)$$\mu (A)={\mathcal {P}}(A)$ . Во втором случае в качестве меры берется мощность множества: $\mathrm{\mu <!--\; \mu \; -->}(A)=|A|$$\mu (A)=|A|$ .

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

$\mathbf {1} _{\bigcup _{i}A_{i}}=\sum _{i}\mathbf {1} _{A_{i}}-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$ 

Пусть $A_i$$A_{i}$  — измеримые множества пространства $(X,\mathfrak{S},\mathrm{\mu <!--\; \mu \; -->})$$(X,{\mathfrak {S}},\mu )$ , то есть $A_i\in <!--\; \in \; -->\mathfrak{S}$$A_{i}\in {\mathfrak {S}}$ . Проинтегрируем обе части этого равенства по мере $\mathrm{\mu <!--\; \mu \; -->}$$\mu$ , воспользуемся линейностью интеграла и соотношением $\mathrm{\mu <!--\; \mu \; -->}(A)={\int <!--\; \int \; -->}_X{\mathbf{1}}_A(x)d\mathrm{\mu <!--\; \mu \; -->}$$\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$ , и получим формулу включений-исключений для меры.

Тождество максимумов и минимумовПравить

Основная статья: Тождество максимумов и минимумов

Формула включений-исключений может рассматриваться как частный случай тождества максимумов и минимумов:

$\max(a_{1},\ldots ,a_{n})=\sum _{i}a_{i}-\sum _{i<j}\min(a_{i},a_{j})+\ldots +(-1)^{n-1}\,\min(a_{1},\ldots ,a_{n}).$ 

Это соотношение справедливо для произвольных чисел $a_i$$a_{i}$ . В частном случае, когда $a_i\in <!--\; \in \; -->\{0,1\}$$a_{i}\in \{0,1\}$  мы получаем одну из форм принципа включений-исключений. В самом деле, если положить $a_i={\mathbf{1}}_{A_i}(x)$$a_{i}=\mathbf {1} _{A_{i}}(x)$ , где $x$$x$  — произвольный элемент из $U$$U$ , то получим соотношение для индикаторных функций множеств:

$\mathbf {1} _{\bigcup _{i}A_{i}}(x)=\sum _{i}\mathbf {1} _{A_{i}}(x)-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}(x)+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}(x).$ 

Обращение МёбиусаПравить

Основная статья: Обращение Мёбиуса

Пусть $S$$S$  — конечное множество, и пусть $f:<!--\; :\; -->2^S\to <!--\; \to \; -->\mathbb{R}$$f\colon 2^{S}\to \mathbb {R}$  — произвольная функция, определённая на совокупности подмножеств $S$$S$  и принимающая действительные значения. Определим функцию $g:<!--\; :\; -->2^S\to <!--\; \to \; -->\mathbb{R}$$g\colon 2^{S}\to \mathbb {R}$  следующим соотношением:

$g(Y)=\underset{X\supset <!--\; \supset \; -->Y}{\sum <!--\; \sum \; -->}f(X).$$g(Y)=\sum _{X\supset Y}f(X).$ 

Тогда имеет место следующая формула обращения:

$f(Y)=\underset{X\supset <!--\; \supset \; -->Y}{\sum <!--\; \sum \; -->}(-<!--\; -\; -->1{)}^{|X|-<!--\; -\; -->|Y|}g(X).$$f(Y)=\sum _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).$ 

Это утверждение является частным случаем общей формулы обращения Мёбиуса для алгебры инцидентности (англ.) совокупности $2^S$$2^{S}$  всех подмножеств множества $S$$S$ , частично упорядоченных по отношению включения $\subset <!--\; \subset \; -->$$\subset$ .

Покажем, как из этой формулы следует принцип включения-исключения для конечных множеств. Пусть дано семейство подмножеств $A_1,\dots <!--\; \dots \; -->,A_n$$A_{1},\ldots ,A_{n}$  конечного множества $U$$U$ , обозначим $S=\{1,\dots <!--\; \dots \; -->,n\}$$S=\{1,\ldots ,n\}$  — множество индексов. Для каждого набора индексов $X\subset <!--\; \subset \; -->S$$X\subset S$  определим $f(X)$$f(X)$  как число элементов, входящих только в те множества $A_i$$A_{i}$ , для которых $i\in <!--\; \in \; -->X$$i\in X$ . Математически это можно записать так:

$f(X)=\left|\left(\underset{i\in <!--\; \in \; -->X}{\bigcap <!--\; \bigcap \; -->}{A}_i\right)\cap <!--\; \cap \; -->\left(\underset{j\notin <!--\; \notin \; -->X}{\bigcap <!--\; \bigcap \; -->}\stackrel{¯<!--\; ¯\; -->}{A_j}\right)\right|.$$f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j}}}\right)\right|.$ 

Тогда функция $g:<!--\; :\; -->2^S\to <!--\; \to \; -->\mathbb{R}$$g\colon 2^{S}\to \mathbb {R}$ , определённая формулой

$g(Y)=\underset{X\supset <!--\; \supset \; -->Y}{\sum <!--\; \sum \; -->}f(X),$$g(Y)=\sum _{X\supset Y}f(X),$ 

даёт количество элементов, каждый из которых входит во все множества $A_i$$A_{i}$ , $i\in <!--\; \in \; -->X$$i\in X$  и, быть может, ещё в другие. То есть

$g(X)=\left|\underset{i\in <!--\; \in \; -->X}{\bigcap <!--\; \bigcap \; -->}{A}_i\right|.$$g(X)=\left|\bigcap _{i\in X}A_{i}\right|.$ 

Заметим далее, что $f(\mathrm{\varnothing <!--\; \varnothing \; -->})$$f(\varnothing )$  — количество элементов, не обладающих ни одним из свойств:

$f(\mathrm{\varnothing <!--\; \varnothing \; -->})=\left|\underset{i}{\bigcap <!--\; \bigcap \; -->}\stackrel{¯<!--\; ¯\; -->}{A_i}\right|.$$f(\varnothing )=\left|\bigcap _{i}{\overline {A_{i}}}\right|.$ 

С учётом сделанных замечаний запишем формулу обращения Мёбиуса:

$\left|\underset{i}{\bigcap <!--\; \bigcap \; -->}\stackrel{¯<!--\; ¯\; -->}{A_i}\right|=\underset{X}{\sum <!--\; \sum \; -->}(-<!--\; -\; -->1{)}^{|X|}\left|\underset{i\in <!--\; \in \; -->X}{\bigcap <!--\; \bigcap \; -->}{A}_i\right|.$$\left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\in X}A_{i}\right|.$ 

Это есть в точности формула включений-исключений для конечных множеств, только в ней не сгруппированы слагаемые, относящиеся к одинаковым значениям $|X|$$|X|$ .

ИсторияПравить

Впервые формулу включений-исключений опубликовал португальский математик Даниэль да Сильва (англ.) в 1854 году. Но ещё в 1713 году Николай Бернулли (англ.) использовал этот метод для решения задачи Монмора (англ.), известной как задача о встречах (фр. Le problème des rencontres), частным случаем которой является задача о беспорядках. Также формулу включений-исключений связывают с именем английского математика Джозефа Сильвестра.

См. такжеПравить

• Формула Грассмана
• Неравенство Буля (англ.)

ЛитератураПравить

• Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — 289 с.
• Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — 309 с.
• Стенли Р. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: Мир, 1990. — 440 с.
• Холл М. Комбинаторика = Combinatorial Theory. — М.: Мир, 1970. — 424 с.
• И. Яглом. Заплаты на кафтане // Квант. — 1974. — № 2. — С. 13—21.

СсылкиПравить

• Weisstein, Eric W. Inclusion-Exclusion Principle (англ.) на сайте Wolfram MathWorld.