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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Например, в случае двух множеств ~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 состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

Формулировка[править | править исходный текст]

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

В терминах множеств[править | править исходный текст]

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

В терминах свойств[править | править исходный текст]

Принцип включений-исключений часто приводят в следующей альтернативной формулировке [2]. Пусть дано конечное множество ~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).

Доказательство[править | править исходный текст]

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

Применение[править | править исходный текст]

Задача о беспорядках[править | править исходный текст]

Классический пример использования формулы включений-исключений — задача о беспорядках[2]. Требуется найти число перестановок (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}) содержит \tbinom{n}{s} одинаковых слагаемых. Формула включений-исключений дает выражение для числа ~D_n беспорядков:

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!} - \ldots + \frac {(-1)^n}{n!} \right).

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

D_n / P_n \approx 1/e.

Вычисление функции Эйлера[править | править исходный текст]

Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера \varphi (n)[4], выражающей количество чисел из \{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} \left(1 - \frac {1} {p_i} \right).

Вариации и обобщения[править | править исходный текст]

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

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


\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 — события вероятностного пространства (\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 \left( \bigcap_{i=1}^n A_i \right).

Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: \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).

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


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) = \left| \left( \bigcap_{i \in X} A_i \right) \cap \left( \bigcap_{j \notin X} \overline{A_j} \right) \right|.

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


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

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


g(X) = \left| \bigcap_{i \in X} A_i \right|.

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


f(\varnothing) = \left| \bigcap_{i} \overline{A_i} \right|.

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


\left| \bigcap_{i} \overline{A_i} \right| = \sum_{X} (-1)^{|X|} \, \left| \bigcap_{i \in X} A_i \right|.

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

История[править | править исходный текст]

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

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

Ссылки[править | править исходный текст]