Метод включений и исключений

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

Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:

(6)

В результате по индукции получаем формулу включений и исключений:

(7)

Название этой формулы подчеркивает использование последовательных включений и исключений элементов подмножеств.

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

(8)

Использование формулы (8) в комбинаторике называют методом включений и исключений.

Пример 5. Рассмотрим слова длины в алфавите {0, 1, 2}. Сколько имеется слов, в которых встречаются все три цифры?

Обозначим через множество всех слов, в которых не встречается цифра , . Тогда . Кроме того, . Наконец, . В множество входят слова, в которых отсутствует хотя бы одна цифра. По формуле(7)

.

По формуле обращения число слов, в которых присутствуют все три цифры, равно .