3.5. Принцип включения и исключения

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

если элемент обладает свойством , если элемент не обладает свойством сумма весов элементов со свойством — сумма весов элементов множества которые обладают каждым из свойств суммирование выполняется по всем сочетаниям длины из свойств, количество сочетаний равно

Таким образом, в суммируются веса только тех элементов, которые имеют как минимум свойств. Пусть элемент обладает к свойствами и тогда его вес войдет раз.

Так, содержит членов и содержит членов.

Распространим определение на положив сумма весов элементов исходного множества

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

Теорема. Сумма весов элементов, обладающих точно свойствами из свойств равна

или

Доказательство. Для доказательства достаточно показать, что вклад веса произвольного элемента в правую и левую

части (3.5.1) одинаковый. Пусть обладает точно свойствами. Возможны следующие соотношения между :

1) , тогда не входит в и не входит в для Равенство (3.5.1) примет вид .

2) , тогда входит один раз в и один раз в

3) , тогда не входит в и левая часть равна 0. Покажем, что в этом случае и правая часть выражения (3.5.1) равна нулю.

Вес входит раз, Правая часть для веса одного элемента примет вид

Заметим, что

Следовательно, а исходная сумма составит

И в третьем случае выражение (3.5.1) справедливо. Теорема доказана.

Следствие.

Задача. В группе 23 студента. Из них 18 знают английский язык, 9 — немецкий и 6 — оба языка. Сколько студентов в группе не знают ни одного языка? Сколько студентов знают один язык?

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

Тогда — студенты со знанием одного языка (обладают ровно одним свойством).

Задача. Найти число перестановок шаров, в которых ровно шаров остаются на месте.

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