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

По правилу суммы, мощность объединения двух не пересекающихся множеств равна сумме их мощностей. В общем же случае, когда множества A и B могут пересекаться, в сумме некоторые элементы из множества сосчитаны дважды. Это те элементы, которые принадлежат пересечению . Следовательно, мощность объединения двух конечных множеств можно найти по формуле:

.

Использованный здесь прием подсчета можно применить и для определения количества элементов в объединении любого числа множеств. Его называют методом включений и исключений. Докажем формулу включений и исключений в общем случае.

Теорема 10. Для любых конечных множеств имеет место равенство

, (1)

где .

Д о к а з а т е л ь с т в о. Рассмотрим произвольный элемент и определим вклад, который он вносит в правую часть формулы (1). Допустим, что x входит точно в m из множеств . Так как – это сумма мощностей этих множеств, то элемент x в сосчитан m раз. Далее, – сумма мощностей попарных пересечений множеств . Значит, x будет в этой сумме сосчитан столько раз, сколько существует пар множеств таких, что . Но x принадлежит точно m множествам, значит, таких пар будет . Рассуждая и дальше в том же духе, приходим к выводу, что для любого элемент x в сумме учтен раз. Значит, общий вклад элемента x в правую часть формулы (1) равен . Из свойства 6 биномиальных коэффициентов следует, что эта сумма равна . Значит, каждый элемент сосчитан точно один раз и правая часть (1) равна числу элементов, т.е. мощности объединения множеств . 

В качестве примера применения метода включения и исключения рассмотрим задачу о беспорядках: сколько существует перестановок чисел таких, что при любом ?

Число искомых перестановок D является разностью между числом всех перестановок и числом перестановок, у которых хотя бы один символ стоит на своем месте. Обозначим множество перестановок, для которых через , тогда . Мощность объединения множеств находим по формуле включения и исключения. Пересечение любых k множеств содержит все такие перестановки, у которых числа стоят на своих местах. Поскольку остальные n-k чисел располагаются на оставшихся местах произвольно, число таких перестановок равно (n-k)!. Поэтому каждое слагаемое в сумме равно !. Число слагаемых равно числу способов выбрать k чисел из n, т.е. . Следовательно, .

Задачи

1. На одной из кафедр университета работают тринадцать человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро - немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский.

Сколько человек знают все три языка?

Сколько человек знают ровно два языка?

Сколько человек знают только английский язык?

2. В музыкальном ансамбле используется четыре инструмента, Для каждого инструмента в ансамбле имеется четыре человека, владеющих данным инструментом, для любых двух инструментов - три человека, играющих на них, для любых трех - два человека. Один человек владеет всеми четырьмя инструментами. Сколько человек в ансамбле?