30. Формула включений и исключений для n множеств
Размер объединения множеств равен сумме размеров всех пересечений по одному множеству, минус сумма размеров всех попарных пересечений, плюс сумма всех тройных, и так далее с чередующимися знаками. Каждый элемент из объединения при этом учитывается ровно один раз — по тому же принципу, что мы проверили для трёх множеств.
Что пригодится из прошлого: включения и исключения для двух и трёх множеств — идея «добавили, вычли, вернули»; следствия бинома — знакопеременная сумма ; законы де Моргана и распределительные законы — для второго доказательства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Теорема
Пусть — конечное множество, а — его подмножества. В формуле ниже встречаются суммы такого вида:
— сумма размеров пересечений всех наборов из различных множеств. Номера в наборе записываются по возрастанию, чтобы каждый набор был учтён один раз. Таких наборов .
Черта над множеством означает дополнение: — те элементы , которые не лежат в (см. дополнение множества).
Теорема (принцип включений и исключений).
И вместе с ней
Знак перед суммой по наборам из множеств равен : плюс для и минус для . Второе равенство складывается из двух простых шагов. Закон де Моргана (для двух множеств, для нескольких) даёт : элементы, не попавшие ни в одно , — это дополнение объединения. А в дополнении столько элементов, сколько в без объединения: .
Разберём на четырёх множествах
Чтобы увидеть устройство формулы, возьмём , , , . Слагаемых в формуле столько, сколько непустых наборов номеров: .
В таблице «Номера» — это номера множеств, которые пересекаем, «Элементы» — их общие элементы, «Вклад» — размер пересечения со знаком, с которым оно входит в формулу:
| Номера | Элементы | Вклад | |
|---|---|---|---|
| 1 | 1 | {1,2,3,4} | +4 |
| 1 | 2 | {3,4,5,6} | +4 |
| 1 | 3 | {2,4,6,8} | +4 |
| 1 | 4 | {4,5,6,7} | +4 |
| 2 | 1,2 | {3,4} | −2 |
| 2 | 1,3 | {2,4} | −2 |
| 2 | 1,4 | {4} | −1 |
| 2 | 2,3 | {4,6} | −2 |
| 2 | 2,4 | {4,5,6} | −3 |
| 2 | 3,4 | {4,6} | −2 |
| 3 | 1,2,3 | {4} | +1 |
| 3 | 1,2,4 | {4} | +1 |
| 3 | 1,3,4 | {4} | +1 |
| 3 | 2,3,4 | {4,6} | +2 |
| 4 | 1,2,3,4 | {4} | −1 |
| итого | 8 |
Числа со знаками дают . Объединение действительно содержит элементов.
Доказательство 1: по вкладу каждого элемента
Возьмём любой элемент множества и посмотрим, сколько раз он учтён в правой части формулы.
- Если не лежит ни в одном , он не попадает ни в одно пересечение: вклад , и в левой части его тоже нет.
- Пусть лежит ровно в из множеств. В пересечение набора из множеств он входит ровно тогда, когда все множеств набора — из этих . Таких наборов . Значит, вклад элемента (с учётом знаков) равен
По формуле бинома при знакопеременная сумма по всем от до равна нулю: (это следствие из главы про бином). Слагаемое с равно , поэтому . Вклад элемента отличается от этой суммы только знаком, то есть равен .
Итак, каждый элемент объединения учтён один раз, элементы вне объединения — ни разу. Правая часть равна .
Это доказательство работает и для трёх множеств: подсчёт по областям из прошлой главы был его частным случаем.
Доказательство 2: индукция по
Для теорема очевидна, для и мы её уже проверили. Предположим, что она верна для любых множеств, и докажем её для множеств. Обозначим . По формуле для двух множеств
Для (здесь ) вся формула выглядит так:
Теперь разберём три слагаемых в общем случае.
- — это объединение множеств. По предположению оно записывается формулой, в которой участвуют все наборы номеров из .
- — набор из единственного номера , со знаком «плюс».
- . По распределительному закону — снова объединение множеств . По предположению индукции их объединение раскладывается по всем наборам из , и пересечение . Эти слагаемые — наборы номеров, содержащие , размера ; перед ними в формуле для стоит знак (набор из множеств ), а в нашей формуле перед всем стоит ещё минус. Итоговый знак . Но такое слагаемое отвечает набору из множеств (вместе с ), а требуемый знак для набора такого размера — . Знаки совпали.
Вместе: наборы без номера пришли из ; одиночный набор — из ; остальные наборы с номером — из . Все непустые наборы номеров из встретились по разу и с нужными знаками.
Проверка на крайнем случае
Пусть все множеств совпадают с одним множеством . Тогда объединение равно , а в правой части все пересечения тоже равны :
потому что из следует , то есть выражение в скобках равно .
Частые ошибки
- Забыть какие-то пересечения. Слагаемых : все непустые наборы номеров.
- Перепутать знаки. Нечётные наборы (из множеств) — плюс, чётные — минус.
- Взять не «по возрастанию». Набор и набор — один и тот же; номера нужно перебирать так, чтобы каждый набор встретился один раз.
- Путать и . Второе — элементы, не лежащие ни в одном .
Проверь себя
1. Сколько слагаемых в формуле включений и исключений для пяти множеств? Сколько из них со знаком «плюс»?
Решение
Все непустые наборы номеров: . «Плюс» — наборы из , , множеств: . «Минус» — наборы из и множеств: .
2. Известно, что в множестве из элементов объединение . Сколько элементов лежит вне всех ?
Решение
.
3. Покажите, что при формула совпадает с известной.
Решение
Для наборы номеров: , (плюс) и (минус): .
Итог
- — сумма размеров пересечений наборов из множеств со знаком , по всем ; слагаемых .
- Элементы вне всех множеств: .
- Доказательство 1: элемент из множеств учтён раз.
- Доказательство 2: индукция, и распределительный закон.
