Формула включения и исключения

ДО 5 БАЛЛОВ ЗА КОНСПЕКТ

Формула включения и исключения – это формула для нахождения числа элементов объединения нескольких конечных множеств. Выведем формулу для объединения двух множеств. Пусть Тогда (см. диаграмму Венна на рис.1).

Рис. 1

Также нетрудно получить формулу для мощности объединения трех множеств

Выведем формулу для объединения n множеств. Эта формула такова

(1)

Общая сумма формулы (1)

. (2)

Формула (2) – это сумма мощностей всех возможных пересечений k множеств, отобранных из n данных. В этой сумме слагаемых. Для доказательства формулы (1) надо доказать, что каждый элемент x из левой части формулы ровно один раз считается в правой части. Пусть x принадлежит m множествам из n имеющихся. Подсчитаем, сколько раз учитывается элемент x в правой части формулы:

- столько отдельных множеств содержат элемент х;

- столько пересечений двух множеств, каждое из которых содержит x

………………………………………………………………………….

- только одно пересечение m множеств содержит x.

Значит, с учетом знака, элемент x в правой части формулы учитывается

Формула (1) называется формулой включения и исключения.

Пример. Вернемся к примеру 4 из предыдущей лекции.

Из 100 студентов английский язык знают 28 человек, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все языки знают 3 человека. Сколько человек не знают ни одного языка?

Решение. Пусть универсум U – это множество всех студентов,

A₁ - множество студентов, знающих английский язык;

A₂ - множество студентов, знающих немецкий язык;

A₃ - множество студентов, знающих французский язык.

Тогда

Нужно найти