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

Пусть дано n -множество элементов S и N- множество свойств p ₁,…, p_N. Элементы множества S могут как обладать, так и не обладать любым из свойств p_i. Количество элементов, обладающих теми или иными свойствами и их комбинациями, известно.

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

Обозначим:

1) через некоторую i -ю выборку свойств, а через – число элементов, каждый из которых обладает всеми этими r выбранными свойствами.

2) через – отсутствие у элемента свойства p_i. Тогда, например, – число элементов, обладающих свойствами p ₁ и p₃ и не обладающих свойствами p₂ и p₄.

Рассмотрим два частных случая.

1. Имеется лишь одно свойство p. Тогда очевидно, что число элементов, не обладающих свойством p, равно общему числу элементов минус число элементов, обладающих свойством p. .

2. Имеется конечное множество свойств p ₁,…, p_N, но они не совместимы (т.е. ни один из элементов не может обладать более чем одним свойством). Тогда число элементов, не обладающих ни одним из свойств, равно общему числу элементов минус число элементов, обладающих свойством p ₁, минус число элементов, обладающих свойством p ₂ и т.д.

.

Общий случай – элементы могут обладать комбинацией совместимых свойств.

Теорема. Если даны n -множество элементов S и N свойств p_i , то число элементов, не обладающих ни одним из свойств, равно (формула решета):

Рассмотрим доказательство при N =3.

Обозначим кругами подмножества элементов, обладающих хотя бы свойством p ₁, хотя бы свойством p ₂ и хотя бы свойством p ₃. Тогда пересечения двух кругов будут давать подмножество элементов, обладающих хотя бы двумя свойствами одновременно, а пересечение всех трех кругов дает подмножество элементов, обладающих всеми тремя свойствами. Прямоугольник, в котором расположены круги, обозначает все множество S, содержащее n элементов. Нужно найти количество элементов, не обладающие ни одним из трёх свойств (за пределами кругов).

Чтобы найти это число, нужно из n -множества исключить элементы, обладающие свойством p ₁, затем обладающие свойством p₂, затем – p₃, т.е. вычесть . Однако при этом элементы, обладающие двумя свойствами (например, p ₁ и p₂), окажутся исключёнными дважды (сначала как элементы, обладающие свойством p ₁, затем как обладающие p₂). Следовательно, нужно возвратить по одному разу элементы, исключённые дважды, т.е. добавить . Но при этом элементы, обладающие сразу тремя свойствами (p ₁, p₂, p₃), сначала были трижды исключены как элементы, обладающие по отдельности свойствами p ₁, p₂ или p₃, а затем трижды включены как обладающие парами свойств. Поэтому их нужно один раз исключить, т.е. вычесть . Рассуждая подобным образом, получаем алгоритм, который состоит в попеременном включении и отбрасывании подмножеств, дающий приведенную выше формулу решета.

Следствие. Характер доказательства таков, что его можно применять к любой комбинации свойств. Например,

.