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

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

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

Принцип включений-исключений часто приводят в следующей альтернативной формулировке [2]. Пусть дано конечное множество ${\displaystyle U}$, состоящее из ${\displaystyle N}$ элементов, и пусть имеется набор свойств ${\displaystyle a_{1},\ldots ,a_{n}}$. Каждый элемент множества ${\displaystyle U}$ может обладать или не обладать любым из этих свойств. Обозначим через ${\displaystyle N(a_{i_{1}}\ldots a_{i_{s}})}$ количество элементов, обладающих свойствами ${\displaystyle a_{i_{1}},\ldots ,a_{i_{s}}}$ (и, может быть, некоторыми другими). Также через ${\displaystyle N({\overline {a}}_{i_{1}}\ldots {\overline {a}}_{i_{s}})}$ обозначим количество элементов, не обладающих ни одним из свойств ${\displaystyle a_{i_{1}},\ldots ,a_{i_{s}}}$. Тогда имеет место формула:

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

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

Обозначим через ${\displaystyle N(r)}$ количество элементов, обладающих в точности ${\displaystyle r}$ свойствами из набора ${\displaystyle a_{1},\ldots ,a_{n}}$.Тогда формулу включений-исключений можно переписать в следующей форме:

Классический пример использования формулы включений-исключений — задача о беспорядках[2]. Требуется найти число перестановок ${\displaystyle (p_{1},p_{2},\ldots ,p_{n})}$ множества ${\displaystyle \{1,2,\ldots ,n\}}$ таких что ${\displaystyle p_{i}\neq i}$ для всех ${\displaystyle i}$. Такие перестановки называются беспорядками.

Пусть ${\displaystyle U}$ — множество всех перестановок ${\displaystyle p}$ и пусть свойство ${\displaystyle a_{i}}$ перестановки выражается равенством ${\displaystyle p_{i}=i}$. Тогда число беспорядков есть ${\displaystyle N({\overline {a}}_{1},{\overline {a}}_{2},\ldots ,{\overline {a}}_{n})}$. Легко видеть, что ${\displaystyle N(a_{i_{1}},\ldots ,a_{i_{s}})=(n-s)!}$ — число перестановок, оставляющих на месте элементы ${\displaystyle i_{1},\ldots ,i_{s}}$, и таким образом сумма ${\displaystyle \sum N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})}$ содержит ${\displaystyle {\tbinom {n}{s}}}$ одинаковых слагаемых. Формула включений-исключений дает выражение для числа ${\displaystyle D_{n}}$ беспорядков:

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

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

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

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

Число ${\displaystyle m\in \{1,\ldots n\}}$ взаимно просто с ${\displaystyle n}$ тогда и только тогда, когда ни один из простых делителей ${\displaystyle p_{i}}$ не делит ${\displaystyle m}$. Если теперь свойство ${\displaystyle a_{i}}$ означает, что ${\displaystyle p_{i}}$ делит ${\displaystyle m}$, то количество чисел взаимно простых с ${\displaystyle n}$ есть ${\displaystyle N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})}$.

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

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

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

Пусть ${\displaystyle (\Omega ,{\mathfrak {F}},{\mathcal {P}})}$ — вероятностное пространство. Тогда для произвольных событий ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ справедлива формула[1][3][5]

${\displaystyle {\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).}$

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

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

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

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

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

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

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

${\displaystyle \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}).}$

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

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

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

${\displaystyle f(Y)=\sum _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).}$

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

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

Тогда функция ${\displaystyle g\colon 2^{S}\to \mathbb {R} }$, определенная формулой

${\displaystyle g(Y)=\sum _{X\supset Y}f(X),}$

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

${\displaystyle g(X)=\left|\bigcap _{i\in X}A_{i}\right|.}$

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

${\displaystyle f(\varnothing )=\left|\bigcap _{i}{\overline {A_{i}}}\right|.}$

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

${\displaystyle \left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\in X}A_{i}\right|.}$

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