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

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

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

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

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

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

[править | править код]

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

Применение

[править | править код]

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

[править | править код]

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

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

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

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

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

[править | править код]

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

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

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

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

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

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

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

[править | править код]

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

[править | править код]

Пусть  — вероятностное пространство. Тогда для произвольных событий справедлива формула[1][3][5]

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

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

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

[править | править код]

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

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

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

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

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

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

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

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

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

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

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

Литература

[править | править код]
  • Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — 289 с.
  • Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. — М.: Изд-во МГУ, 1985. — 309 с.
  • Стенли Р. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: Мир, 1990. — 440 с.
  • Холл М. Комбинаторика = Combinatorial Theory. — М.: Мир, 1970. — 424 с.
  • И. Яглом. Заплаты на кафтане // Квант. — 1974. — № 2. — С. 13—21.