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

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

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

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

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.}$

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

Таким же образом и в случае ${\displaystyle n>2}$ множеств процесс нахождения количества элементов объединения ${\displaystyle A_{1}\cup A_{2}\cup \ldots \cup A_{n}}$ состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

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

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

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

Пусть ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ — конечные множества. Формула включений-исключений утверждает:

${\displaystyle {\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}|.}$

При ${\displaystyle n=2}$ получаем формулу для двух множеств, приведенную выше.

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

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

${\displaystyle 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}).}$

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

${\displaystyle {\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}|.}$

Если теперь вместо «элемент ${\displaystyle x}$ принадлежит множеству ${\displaystyle A_{i}}$» говорить «элемент ${\displaystyle x}$ обладает свойством ${\displaystyle a_{i}}$», то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

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

${\displaystyle N(0)=\sum _{k=0}^{n}(-1)^{k}\sum _{i_{1}<\ldots <i_{k}}N(i_{1},\ldots ,i_{k}).}$

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

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

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

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

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

${\displaystyle N({\overline {a}})=N-N(a).}$

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

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

${\displaystyle N({\overline {a}}_{1}\ldots {\overline {a}}_{m})=N-\sum _{i\leq m}N(a_{i})+\sum _{i<j\leq m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).}$

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

${\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<j\leq m}N(a_{i}a_{j}a_{m+1})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).}$

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

${\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}).}$

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

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

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

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

Пусть элемент ${\displaystyle e}$ обладает в точности ${\displaystyle r}$ свойствами, скажем ${\displaystyle a_{j_{1}},\ldots ,a_{j_{r}}}$. Он дает по 1 в тех слагаемых суммы ${\displaystyle \sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})}$, для которых ${\displaystyle \{i_{1},\ldots ,i_{s}\}}$ есть подмножество ${\displaystyle \{j_{1},\ldots ,j_{r}\}}$, и 0 для остальных. Число таких подмножеств по определению есть число сочетаний ${\displaystyle {\tbinom {r}{s}}}$. Следовательно, вклад элемента ${\displaystyle e}$ в правую часть равен

${\displaystyle 1-{r \choose 1}+{r \choose 2}-\ldots +(-1)^{r}{r \choose r}.}$

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

${\displaystyle \sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.}$

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств ${\displaystyle a_{i}}$, то есть ${\displaystyle N({\overline {a}}_{1}\ldots {\overline {a}}_{n})}$. Что и требовалось доказать. ■

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

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

Индикаторная функция их дополнений ${\displaystyle {\overline {A_{i}}}}$ равна

${\displaystyle \mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},}$

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

${\displaystyle \mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).}$

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

${\displaystyle \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}}.}$

Это соотношение — одна из форм принципа включений-исключений. Оно выражает собой логическое тождество^[1] и верно для произвольных множеств ${\displaystyle A_{i}}$. В случае конечных множеств ${\displaystyle A_{i}}$ (и, соответственно, в предположении конечности множества ${\displaystyle U}$), просуммировав это соотношение по всем ${\displaystyle x\in U}$ и воспользоваться тем, что для произвольного подмножества ${\displaystyle A\subset U}$ его мощность равна

${\displaystyle |A|=\sum _{x\in U}\mathbf {1} _{A}(x),}$

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

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

Снабдим множества ${\displaystyle A_{i}}$ дискретной топологией. В таком случае ${\displaystyle H^{k}(A_{i})=0}$ при ${\displaystyle k>0}$, а при ${\displaystyle k=0}$ имеет место тождество ${\displaystyle \dim H^{0}(A_{i})=|A_{i}|.}$ В случае двух множеств ${\displaystyle A_{1}}$ и ${\displaystyle A_{2}}$ можно воспользоваться точной последовательностью Майера — Вьеториса, которая, учитывая зануление старших когомологий, будет выглядеть как: ${\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.}$ Значит, имеет место тождество ${\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}),}$ или, если переписать его, ${\displaystyle |A_{1}|+|A_{2}|=|A_{1}\cup A_{2}|+|A_{1}\cap A_{2}|,}$ что эквивалентно формуле включений-исключений.

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

Применение

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

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

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

Пусть ${\displaystyle U}$ — множество всех перестановок ${\displaystyle p}$ и пусть свойство ${\displaystyle a_{i}}$ перестановки выражается равенством ${\displaystyle p_{i}=i}$. Тогда число беспорядков есть ${\displaystyle N({\overline {a}}_{1},{\overline {a}}_{2},\ldots ,{\overline {a}}_{n})}$. Легко видеть, что ${\displaystyle N(a_{i_{1}},\ldots ,a_{i_{s}})=(n-s)!}$ — число перестановок, оставляющих на месте элементы ${\displaystyle i_{1},\ldots ,i_{s}}$, и таким образом сумма ${\displaystyle \sum N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})}$ содержит ${\displaystyle {\tbinom {n}{s}}}$ одинаковых слагаемых. Формула включений-исключений дает выражение для числа ${\displaystyle D_{n}}$ беспорядков:

${\displaystyle D_{n}=n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n}0!.}$

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

${\displaystyle D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n}}{n!}}\right).}$

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

${\displaystyle D_{n}/P_{n}\approx 1/e.}$

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

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

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

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

${\displaystyle n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.}$

Число ${\displaystyle m\in \{1,\ldots n\}}$ взаимно просто с ${\displaystyle n}$ тогда и только тогда, когда ни один из простых делителей ${\displaystyle p_{i}}$ не делит ${\displaystyle m}$. Если теперь свойство ${\displaystyle a_{i}}$ означает, что ${\displaystyle p_{i}}$ делит ${\displaystyle m}$, то количество чисел взаимно простых с ${\displaystyle n}$ есть ${\displaystyle N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})}$.

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

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

${\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}.}$

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

${\displaystyle \varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).}$

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

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

Пусть ${\displaystyle (\Omega ,{\mathfrak {F}},\mathbb {P} )}$ — вероятностное пространство. Тогда для произвольных событий ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ справедлива формула^[1][3][5]

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right).}$

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

${\displaystyle \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}}.}$

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

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

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

${\displaystyle \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).}$

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

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

${\displaystyle \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}}.}$

Пусть ${\displaystyle A_{i}}$ — измеримые множества пространства ${\displaystyle (X,{\mathfrak {S}},\mu )}$, то есть ${\displaystyle A_{i}\in {\mathfrak {S}}}$. Проинтегрируем обе части этого равенства по мере ${\displaystyle \mu }$, воспользуемся линейностью интеграла и соотношением ${\displaystyle \mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu }$, и получим формулу включений-исключений для меры.

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

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

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

${\displaystyle \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}).}$

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

${\displaystyle \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).}$

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

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

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

${\displaystyle g(Y)=\sum _{X\supset Y}f(X).}$

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

${\displaystyle f(Y)=\sum _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).}$

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

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

${\displaystyle f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j}}}\right)\right|.}$

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

${\displaystyle g(Y)=\sum _{X\supset Y}f(X),}$

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

${\displaystyle g(X)=\left|\bigcap _{i\in X}A_{i}\right|.}$

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

${\displaystyle f(\varnothing )=\left|\bigcap _{i}{\overline {A_{i}}}\right|.}$

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

${\displaystyle \left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\in X}A_{i}\right|.}$

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

История

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

См. также

• Формула Грассмана
• Неравенство Буля^[англ.]

Примечания

1. Риордан Дж. Введение в комбинаторный анализ = An Introduction to Combinatorial Analysis. — М.: Изд-во иностранной литературы, 1963. — С. 63—66. — 289 с.
2. Холл М. Комбинаторика = Combinatorial Theory. — М.: «Мир», 1970. — С. 18-20. — 424 с.
3. Рыбников К. А. Введение в комбинаторный анализ. — 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.

Ссылки

• Weisstein, Eric W. Inclusion-Exclusion Principle (англ.) на сайте Wolfram MathWorld.