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

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

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

Например, в случае двух множеств [math]\displaystyle{ A, B }[/math] формула включений-исключений имеет вид:

[math]\displaystyle{ | A \cup B | = | A | + | B | - | A \cap B |. }[/math]

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

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

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

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

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

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

[math]\displaystyle{ \biggl | \bigcup_{i=1}^{n}A_i \biggl | = \sum_{i} | A_i | - \sum_{i\lt j} | A_i \cap A_j | + \sum_{i\lt j\lt 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]\displaystyle{ n=2 }[/math] получаем формулу для двух множеств, приведенную выше.

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

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

[math]\displaystyle{ N(\overline{a}_1 \ldots \overline{a}_n) = N - \sum_{i} N(a_i) + \sum_{i\lt j} N(a_i a_j) - \sum_{i\lt j\lt k} N(a_i a_j a_k) + \ldots + (-1)^n N(a_1 \ldots a_n). }[/math]

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

[math]\displaystyle{ \biggl | \bigcap_{i=1}^{n} \overline{A_i} \biggl | = | U | - \sum_{i} | A_i | + \sum_{i\lt j} | A_i \cap A_j | - \sum_{i\lt j\lt k} | A_i \cap A_j \cap A_k | + \ldots + (-1)^n | A_1 \cap A_2 \cap \ldots \cap A_n |. }[/math]

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

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

[math]\displaystyle{ N(0) = \sum_{k=0}^{n} (-1)^{k} \sum_{i_1 \lt \ldots \lt i_k} N(i_1, \ldots, i_k). }[/math]

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

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

Доказательство по индукции

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

При [math]\displaystyle{ n=1 }[/math] формула включений-исключений тривиальна:

[math]\displaystyle{ N(\overline{a}) = N - N(a). }[/math]

Пусть формула верна для [math]\displaystyle{ n=m }[/math], докажем её для [math]\displaystyle{ n=m+1 }[/math].

Пусть каждый элемент множества [math]\displaystyle{ U }[/math] может обладать или не обладать любым из свойств [math]\displaystyle{ a_1, \ldots, a_m, a_{m+1} }[/math]. Применим формулу включений-исключений для свойств [math]\displaystyle{ a_1, \ldots, a_m }[/math]:

[math]\displaystyle{ N(\overline{a}_1 \ldots \overline{a}_m) = N - \sum_{i \leq m} N(a_i) + \sum_{i \lt j \leq m} N(a_i a_j) + \ldots + (-1)^m N(a_1 \ldots a_m). }[/math]

Теперь применим формулу для свойств [math]\displaystyle{ a_1, \ldots , a_m }[/math] к множеству [math]\displaystyle{ N(a_{m+1}) }[/math] объектов, для которых выполнено свойство [math]\displaystyle{ a_{m+1} }[/math]:

[math]\displaystyle{ 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 \lt j \leq m} N(a_i a_j a_{m+1}) + \ldots + (-1)^m N(a_1 \ldots a_m a_{m+1}). }[/math]

Наконец, применим формулу для одного свойства [math]\displaystyle{ a_{m+1} }[/math] к совокупности [math]\displaystyle{ N(\overline{a}_1 \ldots \overline{a}_m) }[/math], объектов, которые не обладают свойствами [math]\displaystyle{ a_1, \ldots , a_m }[/math]:

[math]\displaystyle{ 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}). }[/math]

Комбинируя выписанные три формулы, получим формулу включений-исключений для [math]\displaystyle{ m+1 }[/math] свойств [math]\displaystyle{ a_1, \ldots , a_{m+1} }[/math]. Что и требовалось доказать. ■

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

Рассмотрим произвольный элемент [math]\displaystyle{ e \in U }[/math] и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений.

Если элемент [math]\displaystyle{ e }[/math] не обладает ни одним из свойств [math]\displaystyle{ a_i }[/math], то в правой части формулы он учитывается ровно 1 раз (в члене [math]\displaystyle{ N }[/math]).

Пусть элемент [math]\displaystyle{ e }[/math] обладает в точности [math]\displaystyle{ r }[/math] свойствами, скажем [math]\displaystyle{ a_{j_1}, \ldots , a_{j_r} }[/math]. Он дает по 1 в тех слагаемых суммы [math]\displaystyle{ \sum\nolimits_{i_1 \lt \ldots \lt i_s} N(a_{i_1}, \ldots , a_{i_s}) }[/math], для которых [math]\displaystyle{ \{ i_1, \ldots , i_s\} }[/math] есть подмножество [math]\displaystyle{ \{ j_1, \ldots, j_r\} }[/math], и 0 для остальных. Число таких подмножеств по определению есть число сочетаний [math]\displaystyle{ \tbinom{r}{s} }[/math]. Следовательно, вклад элемента [math]\displaystyle{ e }[/math] в правую часть равен

[math]\displaystyle{ 1 - {r \choose 1} + {r \choose 2} - \ldots + (-1)^r {r \choose r}. }[/math]

При [math]\displaystyle{ s \gt r }[/math] числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

[math]\displaystyle{ \sum_{s=0}^{r} (-1)^s {r \choose s} = \bigg (1 + (- 1) \bigg )^r = 0. }[/math]

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств [math]\displaystyle{ a_i }[/math], то есть [math]\displaystyle{ N(\overline{a}_1 \ldots \overline{a}_n) }[/math]. Что и требовалось доказать. ■

Доказательство через индикаторные функции

Пусть [math]\displaystyle{ A_i }[/math] — произвольные (не обязательно конечные) множества, являющиеся подмножествами некоторого множества [math]\displaystyle{ U }[/math], и пусть [math]\displaystyle{ \mathbf{1}_{A_i} }[/math] — индикаторные функции [math]\displaystyle{ A_i }[/math] (или, эквивалентно, свойств [math]\displaystyle{ a_i }[/math]).

Индикаторная функция их дополнений [math]\displaystyle{ \overline{A_i} }[/math] равна

[math]\displaystyle{ \mathbf{1}_{\overline{A_i}} = 1 - \mathbf{1}_{A_i}, }[/math]

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

[math]\displaystyle{ \mathbf{1}_{\cap_{i} \overline{A_i}} = \prod_{i} (1 - \mathbf{1}_{A_i}). }[/math]

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

[math]\displaystyle{ \mathbf{1}_{\bigcap_{i} \overline{A_i}} = 1 - \sum_{i} \mathbf{1}_{A_i} + \sum_{i \lt j} \mathbf{1}_{A_i \cap A_j} - \sum_{i \lt j \lt 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]\displaystyle{ A_i }[/math]. В случае конечных множеств [math]\displaystyle{ A_i }[/math] (и, соответственно, в предположении конечности множества [math]\displaystyle{ U }[/math]), просуммировав это соотношение по всем [math]\displaystyle{ x \in U }[/math] и воспользоваться тем, что для произвольного подмножества [math]\displaystyle{ A \subset U }[/math] его мощность равна

[math]\displaystyle{ |A| = \sum_{x \in U}\mathbf{1}_{A}(x), }[/math]

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

Топологическое доказательство

Снабдим множества [math]\displaystyle{ A_i }[/math] дискретной топологией. В таком случае [math]\displaystyle{ H^k(A_i) = 0 }[/math] при [math]\displaystyle{ k\gt 0 }[/math], а при [math]\displaystyle{ k=0 }[/math] имеет место тождество [math]\displaystyle{ \dim H^0(A_i) = |A_i|. }[/math] В случае двух множеств [math]\displaystyle{ A_1 }[/math] и [math]\displaystyle{ A_2 }[/math] можно воспользоваться точной последовательностью Майера — Вьеториса, которая, учитывая зануление старших когомологий, будет выглядеть как: [math]\displaystyle{ 0\to H^0(A_1\cup A_2) \to H^0(A_1)\oplus H^0(A_2) \to H^0(A_1\cap A_2)\to 0. }[/math] Значит, имеет место тождество [math]\displaystyle{ \dim H^0(A_1)\oplus H^0(A_2) = \dim H^0(A_1\cup A_2) + \dim H^0(A_1\cap A_2), }[/math] или, если переписать его, [math]\displaystyle{ |A_1|+|A_2|=|A_1\cup A_2|+|A_1\cap A_2|, }[/math] что эквивалентно формуле включений-исключений.

В случае более чем двух множеств для доказательства формулы включений-исключений вместо точной последовательности Майера — Вьеториса надо написать некоторую спектральную последовательность (а именно спектральную последовательность Лере для отображения проекции из несвязного объединения [math]\displaystyle{ A_i }[/math] в их объединение), и так же вычислить ранги групп когомологий. ■

Применение

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

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

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

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

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

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

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

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

[math]\displaystyle{ D_n / P_n \approx 1/e. }[/math]

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

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

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

Пусть каноническое разложение числа [math]\displaystyle{ n }[/math] на простые множители имеет вид

[math]\displaystyle{ n = p_1^{s_1} p_2^{s_2} \ldots p_k^{s_k}. }[/math]

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

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

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

[math]\displaystyle{ \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]\displaystyle{ \varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac {1} {p_i} \right). }[/math]

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

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

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

[math]\displaystyle{ \mathcal{P} \biggl( \bigcup_{i=1}^n A_i \biggr) = \sum_{i} \mathcal{P}(A_i) - \sum_{i\lt j} \mathcal{P}(A_i \cap A_j) + \sum_{i\lt j\lt 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]\displaystyle{ \mathbf{1}_{\bigcup_{i} A_i} = \sum_{i} \mathbf{1}_{A_i} - \sum_{i \lt j} \mathbf{1}_{A_i \cap A_j} + \sum_{i \lt j \lt 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]\displaystyle{ A_i }[/math] — события вероятностного пространства [math]\displaystyle{ (\Omega,\mathfrak{F},\mathcal{P}) }[/math], то есть [math]\displaystyle{ A_i \in \mathfrak{F} }[/math]. Возьмем математическое ожидание [math]\displaystyle{ \mathcal{M} }[/math] от обеих частей этого соотношения, и, воспользовавших линейностью математического ожидания и равенством [math]\displaystyle{ \mathcal{P}(A) = \mathcal{M}(\mathbf{1}_A) }[/math] для произвольного события [math]\displaystyle{ A \in \mathfrak{F} }[/math], получим формулу включения-исключения для вероятностей.

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

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

[math]\displaystyle{ \mu \biggl( \bigcup_{i=1}^n A_i \biggr) = \sum_{i} \mu(A_i) - \sum_{i\lt j} \mu(A_i \cap A_j) + \sum_{i\lt j\lt 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]\displaystyle{ \mu (A) = \mathcal{P}(A) }[/math]. Во втором случае в качестве меры берется мощность множества: [math]\displaystyle{ \mu (A) = |A| }[/math].

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

[math]\displaystyle{ \mathbf{1}_{\bigcup_{i} A_i} = \sum_{i} \mathbf{1}_{A_i} - \sum_{i \lt j} \mathbf{1}_{A_i \cap A_j} + \sum_{i \lt j \lt 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]\displaystyle{ A_i }[/math] — измеримые множества пространства [math]\displaystyle{ (X, \mathfrak{S}, \mu) }[/math], то есть [math]\displaystyle{ A_i \in \mathfrak{S} }[/math]. Проинтегрируем обе части этого равенства по мере [math]\displaystyle{ \mu }[/math], воспользуемся линейностью интеграла и соотношением [math]\displaystyle{ \mu(A) = \int_{X} \mathbf{1}_A(x) \, d \mu }[/math], и получим формулу включений-исключений для меры.

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

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

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

[math]\displaystyle{ \max(a_1, \ldots , a_n) = \sum_{i} a_i - \sum_{i \lt j} \min(a_i, a_j) + \ldots + (-1)^{n-1} \, \min(a_1, \ldots , a_n). }[/math]

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

[math]\displaystyle{ \mathbf{1}_{\bigcup_{i} A_i} (x) = \sum_{i} \mathbf{1}_{A_i} (x) - \sum_{i \lt j} \mathbf{1}_{A_i \cap A_j} (x) + \sum_{i \lt j \lt 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]\displaystyle{ S }[/math] — конечное множество, и пусть [math]\displaystyle{ f \colon 2^S \to \mathbb{R} }[/math] — произвольная функция, определенная на совокупности подмножеств [math]\displaystyle{ S }[/math] и принимающая действительные значения. Определим функцию [math]\displaystyle{ g \colon 2^S \to \mathbb{R} }[/math] следующим соотношением:

[math]\displaystyle{ g(Y) = \sum_{X \supset Y} f(X). }[/math]

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

[math]\displaystyle{ f(Y) = \sum_{X \supset Y} (-1)^{|X| - |Y|} \, g(X). }[/math]

Это утверждение является частным случаем общей формулы обращения Мёбиуса для алгебры инцидентности совокупности [math]\displaystyle{ 2^S }[/math] всех подмножеств множества [math]\displaystyle{ S }[/math], частично упорядоченных по отношению включения [math]\displaystyle{ \subset }[/math].

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

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

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

[math]\displaystyle{ g(Y) = \sum_{X \supset Y} f(X), }[/math]

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

[math]\displaystyle{ g(X) = \left| \bigcap_{i \in X} A_i \right|. }[/math]

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

[math]\displaystyle{ f(\varnothing) = \left| \bigcap_{i} \overline{A_i} \right|. }[/math]

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

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

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

История

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

См. также

• Формула Грассмана
• Неравенство Буля

Литература

• Риордан Дж. Введение в комбинаторный анализ = 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.