Принцип включения-исключения

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

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

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

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

Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

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

Содержание

1 Формулировка
- 1.1 В терминах множеств
- 1.2 В терминах свойств
2 Доказательство
3 Применение
- 3.1 Задача о беспорядках
- 3.2 Вычисление функции Эйлера
4 Вариации и обобщения
5 См. также
6 Примечания
7 Ссылки

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

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

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

Пусть — конечные множества. Формула включений-исключений утверждает:

При получаем формулу для двух множеств, приведенную выше.

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

Принцип включений-исключений часто приводят в следующей альтернативной формулировке ^[4]. Пусть дано конечное множество , состоящее из элементов, и пусть имеется набор свойств . Каждый элемент множества может обладать или не обладать любым из этих свойств. Обозначим через количество элементов, обладающих свойствами (и, может быть, некоторыми другими). Также через обозначим количество элементов, не обладающих ни одним из свойств . Тогда имеет место формула:

Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств. Действительно, если множества являются подмножествами некоторого множества , то в силу правил де Моргана (черта над множеством — дополнение в множестве ), и формулу включений-исключений можно переписать так:

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

Обозначим через количество элементов, обладающих в точности свойствами из набора .Тогда формулу включений-исключений можно переписать в следующей замкнутой форме (англ.)

$N(0) = \sum_{k=0}^{n} (-1)^{k} \sum_{i_1 < \ldots < i_k} N(i_1, \ldots, i_k)$

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

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

По индукции

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

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

Пусть формула верна для , докажем ее для .

Пусть каждый элемент множества может обладать или не обладать любым из свойств . Применим формулу включений-исключений для свойств :

Теперь применим формулу для свойств к множеству объектов, для которых выполнено свойство :

Наконец, применим формулу для одного свойства к совокупности , объектов, которые не обладают свойствами :

Комбинируя выписанные три формулы, получим формулу включений-исключений для свойств . Что и требовалось доказать.

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

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

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

Пусть элемент обладает в точности свойствами, скажем . Он дает по 1 в тех слагаемых суммы , для которых есть подмножество , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний . Следовательно, вклад элемента в правую часть равен

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

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств , то есть . Что и требовалось доказать.

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

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

Индикаторные функции их дополнений равны

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

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

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

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

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

Применение

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

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

Классический пример использования формулы включений-исключений — задача о беспорядках ^[4]. Требуется найти число перестановок множества таких что для всех . Такие перестановки называются беспорядками.

Пусть — множество всех перестановок и пусть свойство перестановки выражается равенством . Тогда число беспорядков есть . Легко видеть, что — число перестановок, оставляющих на месте элементы , и таким образом сумма содержит одинаковых слагаемых. Формула включений-исключений дает выражение для числа беспорядков:

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

Нетрудно видеть, что выражение в скобках является частичной суммой ряда . Таким образом, с хорошей точностью число беспорядков составляет долю от общего числа перестановок:

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

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

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

Для целого положительного функция Эйлера дает количество чисел ряда , взаимно простых с . Найдем явное выражение для функции Эйлера.

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

Число взаимно просто с тогда и только тогда, когда ни один из простых делителей не делит . Если теперь свойство означает, что делит , то количество чисел взаимно простых с есть .

Количество чисел, обладающих свойствами равно , поскольку .

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

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

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

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

Пусть — вероятностное пространство. Тогда для произвольных событий справедлива формула ^[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)$

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

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

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

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

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

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

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

Пусть — измеримые множества пространства , то есть . Проинтегрируем обе части этого равенства по мере , воспользуемся линейностью интеграла и соотношением , и получим формулу включений-исключений для меры.

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

Основная статья: Тождество максимумов и минимумов

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

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

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

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

Основная статья: Обращение Мёбиуса

Пусть — конечное множество, и пусть — произвольная функция, определенная на совокупности подмножеств и принимающая действительные значения. Определим функцию следующим соотношением:

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

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

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

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

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

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

Тогда функция , определенная формулой

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

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

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

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

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

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

См. также

Примечания

↑ ¹ ² ³ ⁴ ⁵ Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — С. 63-66. — 289 с.
Derangement (англ.) на сайте Wolfram MathWorld.

↑ Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 264. — 309 с.

↑ ¹ ² ³ Холл М. Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 18-20. — 424 с.

↑ ¹ ² Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 69-73. — 309 с.

↑ Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — С. 266. — 309 с.

↑ Боровков, А. А. Теория вероятностей. — 2-е изд. — М.: «Наука», 1986. — С. 24. — 431 с.

↑ Холл М. Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 30-31. — 424 с.

↑ Стенли Р. Перечислительная комбинаторика = 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.

Krasorion.ru

Упаковочные материалы

Категории