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

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

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

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

$| A \cup B | = | A | + | B | - | A \cap B |$

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

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

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

Формулировка

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

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

Пусть $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$ получаем формулу для двух множеств, приведенную выше.

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

Принцип включений-исключений часто приводят в следующей альтернативной формулировке ^[4]. Пусть дано конечное множество $~U$, состоящее из $~N$ элементов, и пусть имеется набор свойств $~a_1, \ldots , a_n$. Каждый элемент множества $~U$ может обладать или не обладать любым из этих свойств. Обозначим через $~N(a_{i_1} \ldots a_{i_s})$ количество элементов, обладающих свойствами $a_{i_1}, \ldots, a_{i_s}$ (и, может быть, некоторыми другими). Также через $~N(\overline{a}_{i_1} \ldots \overline{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$ являются подмножествами некоторого множества $~U$, то в силу правил де Моргана $| \bigcup\nolimits_{i} A_i | = | U | - | \bigcap\nolimits_{i} \overline{A_i} |$ (черта над множеством — дополнение в множестве $~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$ принадлежит множеству $~A_i$» говорить «элемент $~x$ обладает свойством $~a_i$», то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через $~N(r)$ количество элементов, обладающих в точности $~r$ свойствами из набора $~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)$

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

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

По индукции

Формулу включений-исключений можно доказать по индукции ^{[1] [5]}.

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

$N(\overline{a}) = N - N(a)$

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

Пусть каждый элемент множества $~U$ может обладать или не обладать любым из свойств $~a_1, \ldots, a_m, a_{m+1}$. Применим формулу включений-исключений для свойств $~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, \ldots , a_m$ к множеству $~N(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}$ к совокупности $N(\overline{a}_1 \ldots \overline{a}_m)$, объектов, которые не обладают свойствами $a_1, \ldots , a_m$:

$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$ свойств $a_1, \ldots , a_{m+1}$. Что и требовалось доказать.

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

Рассмотрим произвольный элемент $~e \in U$ и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений^[4].

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

Пусть элемент $~e$ обладает в точности $~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, \ldots , i_s\}$ есть подмножество $\{ j_1, \ldots , j_r\}$, и 0 для остальных. Число таких подмножеств по определению есть число сочетаний $r \choose s$. Следовательно, вклад элемента $~e$ в правую часть равен

$1 - {r \choose 1} + {r \choose 2} - \ldots + (-1)^n {r \choose n}$

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

$\sum_{s=0}^{r} (-1)^s {r \choose s} = \bigg (1 + (- 1) \bigg )^r = 0$

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств $~a_i$, то есть $N(\overline{a}_1 \ldots \overline{a}_n)$. Что и требовалось доказать.

Используя индикаторные функции

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

Индикаторные функции их дополнений $~\overline{A_i}$ равны

$\mathbf{1}_{\overline{A_i}} = 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}$

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

$|A| = \sum_{x \in U}\mathbf{1}_{A}(x)$

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

Применение

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

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

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

Пусть $~U$ — множество всех перестановок $~p$ и пусть свойство $~a_i$ перестановки выражается равенством $~p_i = i$. Тогда число беспорядков есть $N(\overline{a}_1, \overline{a}_2, \ldots , \overline{a}_n)$. Легко видеть, что $N(a_{i_1}, \ldots , a_{i_s}) = (n-s)!$ — число перестановок, оставляющих на месте элементы $i_1, \ldots, i_s$, и таким образом сумма $\sum N(a_{i_1}, a_{i_2} , \ldots , a_{i_s})$ содержит $n \choose s$ одинаковых слагаемых. Формула включений-исключений дает выражение для числа $~D_n$ беспорядков:

$D_n = n! - {n \choose 1} (n-1)! + {n \choose 2} (n-2)! - ... + (-1)^n {n \choose n} 0!$

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

$D_n = n! \bigg ( 1- \frac {1} {1!} + \frac {1} {2!} - \ldots + \frac {(-1)^n} {n!} \bigg )$

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

$D_n / P_n \approx 1/e.$

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

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

Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера ^[6].

Для целого положительного $~n$ функция Эйлера $\varphi (n)$ дает количество чисел ряда $~1, 2, \ldots , n$, взаимно простых с $~n$. Найдем явное выражение для функции Эйлера.

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

$n = p_1^{s_1} p_2^{s_2} \ldots p_k^{s_k}$

Число $~m \in \{ 1, \ldots n \}$ взаимно просто с $~n$ тогда и только тогда, когда ни один из простых делителей $~p_i$ не делит $~m$. Если теперь свойство $~a_i$ означает, что $~p_i$ делит $~m$, то количество чисел взаимно простых с $~n$ есть $~N(\overline{a}_1, \ldots , \overline{a}_k)$.

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

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

$\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$

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

$\varphi(n) = n \prod_{i=1}^{k} \bigg (1 - \frac {1} {p_i} \bigg )$

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

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

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

$\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} \biggl( \bigcap_{i=1}^n A_i \biggr)$

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

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

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

Пусть $(X, \mathfrak{S}, \mu)$ — пространство с мерой. Тогда для произвольных измеримых множеств $~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 \biggl( \bigcap_{i=1}^n A_i \biggr)$

Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: $\mu (A) = \mathcal{P}(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$ — измеримые множества пространства $(X, \mathfrak{S}, \mu)$, то есть $~A_i \in \mathfrak{S}$. Проинтегрируем обе части этого равенства по мере $~\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 \in \{ 0 , 1\}$ мы получаем одну из форм принципа включений-исключений. В самом деле, если положить $~a_i = \mathbf{1}_{A_i}(x)$, где $~x$ — произвольный элемент из $~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$ — конечное множество, и пусть $f \colon 2^S \to \mathbb{R}$ — произвольная функция, определенная на совокупности подмножеств $~S$ и принимающая действительные значения. Определим функцию $g \colon 2^S \to \mathbb{R}$ следующим соотношением:

$g(Y) = \sum_{X \supset Y} f(X)$

Тогда имеет место следующая формула обращения^{[8] [9]}:

$f(Y) = \sum_{X \supset Y} (-1)^{|X| - |Y|} \, g(X)$

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

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

$f(X) = \biggl | \biggl ( \bigcap_{i \in X} A_i \biggr ) \cap \biggl ( \bigcap_{j \notin X} \overline{A_j} \biggl ) \biggr |$

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

$g(Y) = \sum_{X \supset Y} f(X)$

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

$g(X) = \biggl | \bigcap_{i \in X} A_i \biggr |$

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

$f(\varnothing) = \biggl | \bigcap_{i} \overline{A_i} \biggr |$

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

$\biggl | \bigcap_{i} \overline{A_i} \biggr | = \sum_{X} (-1)^{|X|} \, \biggl | \bigcap_{i \in X} A_i \biggr |$

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

См. также

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

Примечания

1. ↑ ^{1 2 3 4 5} Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — С. 63-66. — 289 с.
2. ↑ Weisstein, Eric W. Derangement (англ.) на сайте Wolfram MathWorld.
3. ↑ Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 264. — 309 с.
4. ↑ ^{1 2 3} Холл М. Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 18-20. — 424 с.
5. ↑ ^{1 2} Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 69-73. — 309 с.
6. ↑ Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 266. — 309 с.
7. ↑ Боровков, А. А. Теория вероятностей. — 2-е изд. — М.: «Наука», 1986. — С. 24. — 431 с.
8. ↑ Холл М. Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 30-31. — 424 с.
9. ↑ Стенли Р. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 103-107. — 440 с.

Ссылки

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