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

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

${\displaystyle |A\cup B|=|A|+|B|-|A\cap 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 {\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}|.}$

При ${\displaystyle n=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 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}).}$

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

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

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

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

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

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

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

Применение

Задача о беспорядках

Классический пример использования формулы включений-исключений — задача о беспорядках . Требуется найти число перестановок ${\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 D_{n}=n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n}0!.}$

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

${\displaystyle D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n}}{n!}}\right).}$

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

${\displaystyle D_{n}/P_{n}\approx 1/e.}$

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

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

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

${\displaystyle n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.}$

Число ${\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 \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}.}$

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

${\displaystyle \varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).}$

Вариации и обобщения

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

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

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

Пусть ${\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 {\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).}$

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

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

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

Пусть ${\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 \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).}$

Обращение Мёбиуса

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

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

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

${\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 f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j}}}\right)\right|.}$

Тогда функция ${\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 году . Но ещё в 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. (англ.) на сайте Wolfram MathWorld .