bulgakov

29. Включения и исключения: два и три множества

Чтобы узнать, сколько элементов лежит хотя бы в одном из нескольких множеств, нельзя просто сложить их размеры: элементы, лежащие в нескольких множествах, посчитаются несколько раз. Для двух множеств вычитаем пересечение; для трёх — вычитаем попарные пересечения и добавляем обратно тройное. Это начало принципа включений и исключений.

Что пригодится из прошлого: число элементов объединения — формула для двух множеств; пересечение нескольких множеств; двоичные коды — код из нулей и единиц будет описывать, в каких множествах лежит элемент. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Два множества: вспоминаем

Для конечных множеств AA и BB

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.|A\cup B|=|A|+|B|-|A\cap B|.

В сумме ∣A∣+∣B∣|A|+|B| каждый общий элемент посчитан дважды; вычитаем пересечение один раз — теперь каждый элемент посчитан один раз.

Пример. Из 4040 человек 2525 говорят по-английски, 2020 — по-немецки, 88 — на обоих языках. Хотя бы на одном: 25+20−8=3725+20-8=37. Не говорят ни на одном: 40−37=340-37=3.

Три множества: что вычитать

Возьмём три множества AA, BB, CC. Как найти ∣A∪B∪C∣|A\cup B\cup C|?

Шаг 1. Складываем. ∣A∣+∣B∣+∣C∣|A|+|B|+|C|. Элементы, лежащие в двух множествах, посчитаны дважды, лежащие во всех трёх — трижды.

Шаг 2. Вычитаем пары. Вычтем ∣A∩B∣|A\cap B|, ∣A∩C∣|A\cap C|, ∣B∩C∣|B\cap C|. Элемент из двух множеств теперь посчитан 2−1=12-1=1 раз — как надо. Но элемент из всех трёх множеств посчитан 33 раза в сумме и «убран» 33 раза в трёх вычитаниях: 3−3=03-3=0. Его потеряли.

Шаг 3. Возвращаем тройное. Добавим ∣A∩B∩C∣|A\cap B\cap C|: теперь такой элемент посчитан 3−3+1=13-3+1=1 раз.

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣.\boxed{|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}.

Проверка по областям

Элемент может лежать в t=0,1,2,3t=0,1,2,3 из множеств. Посмотрим, сколько раз он учтён в каждом члене формулы. Пар множеств, в которых лежит элемент, — (t2)\dbinom t2, троек — (t3)\dbinom t3 ((tk)\dbinom tk — число способов выбрать kk из tt, см. сочетания). В каждом пункте записано: «одиночные − пары + тройка = сколько раз элемент учтён»:

  • t=0t=0: 0 − 0 + 0 = 0
  • t=1t=1: 1 − 0 + 0 = 1
  • t=2t=2: 2 − 1 + 0 = 1
  • t=3t=3: 3 − 3 + 1 = 1

Каждый элемент, лежащий хотя бы в одном множестве, учитывается ровно один раз: t−(t2)+(t3)=1t-\dbinom t2+\dbinom t3=1. Элемент вне всех множеств не учитывается ни разу. Поэтому формула верна для любых множеств.

Запишем «карту» из кодов

Чтобы не запутаться, опишем каждого человека кодом из трёх цифр: на ii-м месте стоит 11, если он входит в ii-е множество, и 00, если нет. Это та же идея, что в первой главе, только там код описывал подмножество, а здесь — принадлежность множествам. Например, код 110110 значит «входит в AA и в BB, но не в CC». Всего возможно 23=82^3=8 кодов — это восемь областей.

Пример. В классе 3030 человек. Математику любят 1818 (множество AA), физику — 1414 (BB), химию — 1010 (CC). Математику и физику вместе любят 88, математику и химию — 55, физику и химию — 44 (в каждое из этих чисел входят и те, кто любит ещё и третий предмет), все три предмета — 22. Сколько человек не любят ни одного предмета?

Восстановим карту по областям, начиная с тройного пересечения (его размер известен). Тройное пересечение: 22. «Только AA и BB» — 8−2=68-2=6, «только AA и CC» — 5−2=35-2=3, «только BB и CC» — 4−2=24-2=2. «Только AA» — 18−6−3−2=718-6-3-2=7, «только BB» — 14−6−2−2=414-6-2-2=4, «только CC» — 10−3−2−2=310-3-2-2=3.

В таблице «да» значит, что человек любит этот предмет.

AA BB CC Код Людей
да нет нет 100 7
нет да нет 010 4
нет нет да 001 3
да да нет 110 6
да нет да 101 3
нет да да 011 2
да да да 111 2
нет нет нет 000 3
всего 30

Теперь применим формулу:

∣A∪B∪C∣=18+14+10−8−5−4+2=27.|A\cup B\cup C|=18+14+10-8-5-4+2=27.

Любят хотя бы один предмет 2727 человек, не любят ни одного 30−27=330-27=3 — это последняя строка карты. Сверка с картой: 7+4+3+6+3+2+2=277+4+3+6+3+2+2=27.

Что будет для четырёх и больше множеств

Напрашивается закономерность: сначала складываем размеры множеств, потом вычитаем размеры всех парных пересечений, добавляем размеры всех тройных, вычитаем четверные и так далее:

∣S1∪⋯∪Sn∣=∑∣Si∣−∑∣Si∩Sj∣+∑∣Si∩Sj∩Sk∣−⋯|S_1\cup\dots\cup S_n|=\sum|S_i|-\sum|S_i\cap S_j|+\sum|S_i\cap S_j\cap S_k|-\cdots

Пока это лишь предположение; строгое доказательство для любого nn — в следующих главах.

Примеры

Явные множества. A={1,2,3,4,5}A=\{1,2,3,4,5\}, B={4,5,6,7}B=\{4,5,6,7\}, C={5,7,8}C=\{5,7,8\}. Пересечения: A∩B={4,5}A\cap B=\{4,5\}, A∩C={5}A\cap C=\{5\}, B∩C={5,7}B\cap C=\{5,7\}, A∩B∩C={5}A\cap B\cap C=\{5\}. Формула: 5+4+3−2−1−2+1=85+4+3-2-1-2+1=8. Объединение {1,…,8}\{1,\dots,8\} действительно содержит 88 элементов.

Частые ошибки

  • Сложить только размеры. Получится завышенный ответ, если у множеств есть общие элементы.
  • Вычесть пары и забыть добавить тройное. Элементы из всех трёх множеств потеряются.
  • Путать «хотя бы одно» и «ровно одно». ∣A∪B∪C∣|A\cup B\cup C| считает элементы из хотя бы одного множества.
  • Применять формулу к неконечным множествам. Здесь всё считается числом элементов.

Проверь себя

1. Из 100100 студентов 6060 изучают английский, 4545 немецкий, 2020 оба языка. Сколько изучают хотя бы один? Сколько не изучают ни одного?

Решение

Хотя бы один: 60+45−20=8560+45-20=85. Ни одного: 100−85=15100-85=15.

2. Известно: ∣A∣=20|A|=20, ∣B∣=15|B|=15, ∣C∣=12|C|=12, ∣A∩B∣=6|A\cap B|=6, ∣A∩C∣=5|A\cap C|=5, ∣B∩C∣=4|B\cap C|=4, ∣A∩B∩C∣=2|A\cap B\cap C|=2. Найдите ∣A∪B∪C∣|A\cup B\cup C|.

Решение

20+15+12−6−5−4+2=3420+15+12-6-5-4+2=34.

3. В классе 3535 человек. 1818 занимаются футболом, 1414 шахматами, 1010 музыкой. Футбол и шахматы — 55, футбол и музыку — 44, шахматы и музыку — 33 (в каждое из этих чисел входят и те, кто занимается ещё и третьим), все три занятия — 11. Сколько человек не занимаются ничем?

Решение

Хотя бы одним занимаются 18+14+10−5−4−3+1=3118+14+10-5-4-3+1=31 человек. Не занимаются ничем 35−31=435-31=4.

4. Почему при вычитании только парных пересечений формула неверна для трёх множеств?

Решение

Элемент из всех трёх множеств посчитан трижды в ∣A∣+∣B∣+∣C∣|A|+|B|+|C| и трижды вычтен в трёх парных пересечениях: 3−3=03-3=0. Он пропал из подсчёта. Тройное пересечение нужно добавить обратно.

Итог

  • Два множества: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|.
  • Три множества: складываем одиночные, вычитаем парные, добавляем тройное.
  • Проверка по областям: элемент из t≥1t\ge1 множеств учитывается t−(t2)+(t3)=1t-\dbinom t2+\dbinom t3=1 раз.
  • Код из нулей и единиц описывает, в каких множествах лежит элемент; всего 2n2^n областей.
ПрактикаЗагружаем тест…