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

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

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

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

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

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

Пусть ${\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}}$.Тогда формулу включений-исключений можно переписать в следующей форме:

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

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

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

Индикаторная функция их дополнений ${\displaystyle {\overline {A_{i}}}}$ равна

${\displaystyle \mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},}$

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

${\displaystyle \mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).}$

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

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

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

${\displaystyle |A|=\sum _{x\in U}\mathbf {1} _{A}(x),}$

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

Классический пример использования формулы включений-исключений — задача о беспорядках^[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}},\mathbb {P} )}$ — вероятностное пространство. Тогда для произвольных событий ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ справедлива формула^[1][3][5]

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

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

Пусть ${\displaystyle A_{i}}$ — события вероятностного пространства ${\displaystyle (\Omega ,{\mathfrak {F}},\mathbb {P} )}$, то есть ${\displaystyle A_{i}\in {\mathfrak {F}}}$. Возьмем математическое ожидание ${\displaystyle {\mathcal {M}}}$ от обеих частей этого соотношения, и, воспользовавших линейностью математического ожидания и равенством ${\displaystyle \mathbb {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)=\mathbb {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|}$.

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

• Формула Грассмана
• Неравенство Буля^[англ.]

• Риордан Дж. Введение в комбинаторный анализ = 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.