Меню Главная Случайная статья Настройки Формула включений-исключений Материал из https://ru.wikipedia.org Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре[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}}$ состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключённого и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы. Содержание 1 Формулировка 1.1 В терминах множеств 1.2 В терминах свойств 2 Доказательство 3 Применение 3.1 Задача о беспорядках 3.2 Вычисление функции Эйлера 4 Вариации и обобщения 4.1 Принцип включения-исключения для вероятностей 4.2 Принцип включений-исключений в пространствах с мерой 4.3 Тождество максимумов и минимумов 4.4 Обращение Мёбиуса 5 История 6 См. также 7 Примечания 8 Литература 9 Ссылки Формулировка Формулу включений-исключений можно сформулировать в разных формах. В терминах множеств Пусть ${\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}}$. Что и требовалось доказать.