Формула включения и исключения
ДО 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 – это множество всех студентов,
A1 - множество студентов, знающих английский язык;
A2 - множество студентов, знающих немецкий язык;
A3 - множество студентов, знающих французский язык.
Тогда
Нужно найти