У этого термина существуют и другие значения, см. Исключение.
Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощностьобъединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре[1].
Например, в случае двух множеств формула включений-исключений имеет вид:
В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.
Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
Принцип включений-исключений часто приводят в следующей альтернативной формулировке
[2].
Пусть дано конечное множество , состоящее из элементов, и пусть имеется набор свойств . Каждый элемент множества может обладать или не обладать любым из этих свойств. Обозначим через количество элементов, обладающих свойствами (и, может быть, некоторыми другими). Также через обозначим количество элементов, не обладающих ни одним из свойств . Тогда имеет место формула:
Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств.
Действительно, если множества являются подмножествами некоторого множества , то в силу правил де Моргана (черта над множеством — дополнение в множестве ), и формулу включений-исключений можно переписать так:
Если теперь вместо «элемент принадлежит множеству » говорить «элемент обладает свойством », то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.
Обозначим через количество элементов, обладающих в точности свойствами из набора .Тогда формулу включений-исключений можно переписать в следующей форме:
Существует несколько доказательств формулы включений-исключений.
Доказательство по индукции
Формулу включений-исключений можно доказать по индукции[1][3].
При формула включений-исключений тривиальна:
Пусть формула верна для , докажем её для .
Пусть каждый элемент множества может обладать или не обладать любым из свойств .
Применим формулу включений-исключений для свойств :
Теперь применим формулу для свойств к множеству объектов, для которых выполнено свойство :
Наконец, применим формулу для одного свойства к совокупности , объектов, которые не обладают свойствами :
Комбинируя выписанные три формулы, получим формулу включений-исключений для свойств . Что и требовалось доказать.
■
Комбинаторное доказательство
Рассмотрим произвольный элемент и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений[2].
Если элемент не обладает ни одним из свойств , то в правой части формулы он учитывается ровно 1 раз (в члене ).
Пусть элемент обладает в точности свойствами, скажем . Он дает по 1 в тех слагаемых суммы , для которых есть подмножество , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний. Следовательно, вклад элемента в правую часть равен
При числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна
Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств , то есть . Что и требовалось доказать.
■
Доказательство через индикаторные функции
Пусть — произвольные (не обязательно конечные) множества, являющиеся подмножествами некоторого множества , и пусть — индикаторные функции (или, эквивалентно, свойств ).
Раскрывая скобки в правой части и ещё раз используя тот факт, что индикаторная функция пересечения множеств равна произведению их индикаторных функций, получаем:
Это соотношение — одна из форм принципа включений-исключений. Оно выражает собой логическое тождество[1] и верно для произвольных множеств . В случае конечных множеств (и, соответственно, в предположении конечности множества ), просуммировав это соотношение по всем и воспользоваться тем, что для произвольного подмножества его мощность равна
получим формулировку принципа включений-исключений в терминах мощностей множеств (или в терминах свойств).
■
Топологическое доказательство
Снабдим множества дискретной топологией. В таком случае при , а при имеет место тождество В случае двух множеств и можно воспользоваться точной последовательностью Майера — Вьеториса, которая, учитывая зануление старших когомологий, будет выглядеть как: Значит, имеет место тождество или, если переписать его, что эквивалентно формуле включений-исключений.
В случае более чем двух множеств для доказательства формулы включений-исключений вместо точной последовательности Майера — Вьеториса надо написать некоторую спектральную последовательность (а именно спектральную последовательность Лере[англ.] для отображения проекции из несвязного объединения в их объединение), и так же вычислить ранги групп когомологий.
■
Классический пример использования формулы включений-исключений — задача о беспорядках[2].
Требуется найти число перестановок множества таких что для всех . Такие перестановки называются беспорядками.
Пусть — множество всех перестановок и пусть свойство перестановки выражается равенством . Тогда число беспорядков есть . Легко видеть, что — число перестановок, оставляющих на месте элементы , и таким образом сумма содержит одинаковых слагаемых. Формула включений-исключений дает выражение для числа беспорядков:
Это соотношение можно преобразовать к виду
Нетрудно видеть, что выражение в скобках является частичной суммой ряда . Таким образом, с хорошей точностью число беспорядков составляет долю от общего числа перестановок:
Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера[4], выражающей количество чисел из , взаимно простых с .
Число взаимно просто с тогда и только тогда, когда ни один из простых делителей не делит . Если теперь свойство означает, что делит , то количество чисел взаимно простых с есть .
Количество чисел, обладающих свойствами равно , поскольку .
Эта формула выражает принцип включений-исключений для вероятностей. Её можно получить из принципа включений-исключений в форме индикаторных функций:
Пусть — события вероятностного пространства , то есть . Возьмем математическое ожидание от обеих частей этого соотношения, и, воспользовавших линейностью математического ожидания и равенством для произвольного события , получим формулу включения-исключения для вероятностей.
Принцип включений-исключений в пространствах с мерой
Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: . Во втором случае в качестве меры берется мощность множества: .
Вывести принцип включений-исключений для пространств с мерой можно также, как для указанных частных случаев, из тождества для индикаторных функций:
Пусть — измеримые множества пространства , то есть . Проинтегрируем обе части этого равенства по мере, воспользуемся линейностью интеграла и соотношением , и получим формулу включений-исключений для меры.
Это соотношение справедливо для произвольных чисел . В частном случае, когда мы получаем одну из форм принципа включений-исключений. В самом деле, если положить , где — произвольный элемент из , то получим соотношение для индикаторных функций множеств:
Покажем, как из этой формулы следует принцип включения-исключения для конечных множеств.
Пусть дано семейство подмножеств конечного множества , обозначим — множество индексов. Для каждого набора индексов определим как число элементов, входящих только в те множества , для которых . Математически это можно записать так:
Тогда функция , определённая формулой
даёт количество элементов, каждый из которых входит во все множества , и, быть может, ещё в другие. То есть
Заметим далее, что — количество элементов, не обладающих ни одним из свойств:
С учётом сделанных замечаний запишем формулу обращения Мёбиуса:
Это есть в точности формула включений-исключений для конечных множеств, только в ней не сгруппированы слагаемые, относящиеся к одинаковым значениям .
↑ 12345Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — С. 63—66. — 289 с.
↑ 123Холл М.Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 18-20. — 424 с.
↑ 12Рыбников К. А. Введение в комбинаторный анализ. — 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 с.