Русская Википедия:Формула включений-исключений

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Файл:Venn A intersect B.svg

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

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

<math>| A \cup B | = | A | + | B | - | A \cap B |.</math>

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

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

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

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

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

Пусть <math>A_1, A_2, \ldots, A_n</math> — конечные множества. Формула включений-исключений утверждает:

<math>\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 |.</math>

При <math>n=2</math> получаем формулу для двух множеств, приведенную выше.

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

Принцип включений-исключений часто приводят в следующей альтернативной формулировке . Пусть дано конечное множество <math>U</math>, состоящее из <math>N</math> элементов, и пусть имеется набор свойств <math>a_1, \ldots , a_n</math>. Каждый элемент множества <math>U</math> может обладать или не обладать любым из этих свойств. Обозначим через <math>N(a_{i_1} \ldots a_{i_s})</math> количество элементов, обладающих свойствами <math>a_{i_1}, \ldots, a_{i_s}</math> (и, может быть, некоторыми другими). Также через <math>N(\overline{a}_{i_1} \ldots \overline{a}_{i_s})</math> обозначим количество элементов, не обладающих ни одним из свойств <math>a_{i_1}, \ldots, a_{i_s}</math>. Тогда имеет место формула:

<math>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).</math>

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

<math>\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 |.</math>

Если теперь вместо «элемент <math>x</math> принадлежит множеству <math>A_i</math>» говорить «элемент <math>x</math> обладает свойством <math>a_i</math>», то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через <math>N(r)</math> количество элементов, обладающих в точности <math>r</math> свойствами из набора <math>a_1, \ldots , a_n</math>.Тогда формулу включений-исключений можно переписать в следующей форме:

<math>N(0) = \sum_{k=0}^{n} (-1)^{k} \sum_{i_1 < \ldots < i_k} N(i_1, \ldots, i_k).</math>

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

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

Шаблон:Доказ1 = 1 - \mathbf{1}_{A_i},</math>

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

<math>\mathbf{1}_{\cap_{i} \overline{A_i}} = \prod_{i} (1 - \mathbf{1}_{A_i}).</math>

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

<math>\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}.</math>

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

<math>

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

</math>

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

Применение

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

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

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

<math>D_n = n! - {n \choose 1} (n-1)! + {n \choose 2} (n-2)! - \ldots + (-1)^n {n \choose n} 0!.</math>

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

<math>D_n = n! \left( 1- \frac{1}{1!} + \frac{1}{2!} - \ldots + \frac {(-1)^n}{n!} \right).</math>

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

<math>D_n / P_n \approx 1/e.</math>

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

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

Пусть каноническое разложение числа <math>n</math> на простые множители имеет вид

<math>n = p_1^{s_1} p_2^{s_2} \ldots p_k^{s_k}.</math>

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

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

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

<math>\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.</math>

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

<math>\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac {1} {p_i} \right).</math>

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

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

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

<math>

\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).

</math>

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

<math>\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}.</math>

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

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

Пусть <math>(X, \mathfrak{S}, \mu)</math> — пространство с мерой. Тогда для произвольных измеримых множеств <math>A_i</math> конечной меры <math>\mu (A_i) < \infty</math> имеет место формула включений-исключений:

<math>\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).</math>

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

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

<math>\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}.</math>

Пусть <math>A_i</math> — измеримые множества пространства <math>(X, \mathfrak{S}, \mu)</math>, то есть <math>A_i \in \mathfrak{S}</math>. Проинтегрируем обе части этого равенства по мере <math>\mu</math>, воспользуемся линейностью интеграла и соотношением <math>\mu(A) = \int_{X} \mathbf{1}_A(x) \, d \mu</math>, и получим формулу включений-исключений для меры.

Тождество максимумов и минимумов

Шаблон:Main Формула включений-исключений может рассматриваться как частный случай тождества максимумов и минимумов:

<math>

\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).

</math>

Это соотношение справедливо для произвольных чисел <math>a_i</math>. В частном случае, когда <math>a_i \in \{ 0 , 1\}</math> мы получаем одну из форм принципа включений-исключений. В самом деле, если положить <math>a_i = \mathbf{1}_{A_i}(x)</math>, где <math>x</math> — произвольный элемент из <math>U</math>, то получим соотношение для индикаторных функций множеств:

<math>\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).</math>

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

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

<math>g(Y) = \sum_{X \supset Y} f(X).</math>

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

<math>

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

</math>

Это утверждение является частным случаем общей формулы обращения Мёбиуса для en (Incidence algebra) совокупности <math>2^S</math> всех подмножеств множества <math>S</math>, частично упорядоченных по отношению включения <math>\subset</math>.

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

<math>f(X) = \left| \left( \bigcap_{i \in X} A_i \right) \cap \left( \bigcap_{j \notin X} \overline{A_j} \right) \right|.</math>

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

<math>

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

</math>

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

<math>

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

</math>

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

<math>

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

</math>

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

<math>

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

</math>

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

История

Впервые формулу включений-исключений опубликовал португальский математик [[|en]] (Daniel da Silva (mathematician)) в 1854 году. Но ещё в 1713 году en (Nicolaus I Bernoulli) использовал этот метод для решения задачи en (Pierre Raymond de Montmort), известной как задача о встречах (Шаблон:Lang-fr), частным случаем которой является задача о беспорядках. Также формулу включений-исключений связывают с именем английского математика Джозефа Сильвестра.

См. также

• Формула Грассмана
• [[|en]] (Boole's inequality)

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья

Ссылки

• Шаблон:MathWorld