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

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

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

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

Например, в случае двух множеств ~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 с.

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Формула включений-исключений" в других словарях:

  • Тождество максимумов и минимумов — Тождество максимумов и минимумов  математическое соотношение между максимальным элементом конечного множества чисел и минимальными элементами всех его непустых подмножеств. Формулировка Пусть   произвольные действительные числа. Тогда… …   Википедия

  • Когерентность (философская спекулятивная стратегия) — В мысленном эксперименте, предложенном итальянским теоретиком вероятностей Бруно де Финетти в порядке оправдания Байесовской вероятности, массив ставок является точно когерентным, если он не подвергает спорщика верному проигрышу вне зависимости… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»