Формула включений и исключений: примеры решения задач

Деканат свёл две ведомости: 30 студентов записались на факультатив по анализу, 25 — по алгебре. Из объединённого списка вышло 55 фамилий, и заведующий лабораторией заметил: десять из них встречаются дважды. Список не сломан — сломан подсчёт. Люди, ходящие на оба факультатива, попали в сумму два раза, и пока двойной учёт не вычтен, ни одна цифра не заслуживает доверия. Эта маленькая бытовая неприятность — дверь в один из главных инструментов комбинаторики, без которого не обходится ни подсчёт баз данных, ни теория вероятностей, ни олимпиадная задачка про фамилии.

Почему простое сложение мощностей обманывает?#

Вспомним аппарат из урока про множества и операции: мощность $|A|$ — это число элементов, а пересечение $A\cap B$ собирает общие элементы. Для двух пересекающихся множеств верна формула включений и исключений:

Логика прозрачна: каждый элемент, лежащий и в $A$, и в $B$, прибавился дважды — один раз от $|A|$, второй от $|B|$. Одна лишняя копия подлежит вычету. Если же множества не пересекаются, слагаемое $|A\cap B|$ равно нулю и остаётся обычное правило суммы. Для ведомостей деканата: $30+25-10=45$ человек посещают хотя бы один факультатив.

Заметьте, что обратный пересчёт тоже работает: зная объединение и пересечение, можно найти недостающее. Ведомости часто дают именно «объединение» (список всех, кто чем-то занят) и по нему восстанавливают пары. Обращаться со мощностью множества стоит так же свободно, как с обычными числами — это и есть счёт в дискретной математике.

Перед подстановкой чисел полезно прогнать данные через грубые неравенства-фильтры. Пересечение не может быть больше меньшего множества: $|A\cap B|\le \min (|A|,|B|)$. Объединение не больше суммы мощностей и не меньше каждой из них по отдельности. Если в задаче сказано, что $|A\cup B|=|A|$, значит $B$ целиком сидит внутри $A$ и пересечение равно $|B|$. Одна строчка такой проверки отсекает противоречивые условия раньше, чем вы потратите полстраницы выкладок.

Как формула разворачивается для трёх множеств?#

С тремя множествами знаки начинают чередоваться. Одиночные мощности прибавляются, парные пересечения вычитаются, тройное снова прибавляется:

Откуда берётся чередование? Проследим судьбу одного элемента. Если он лежит ровно в одном множестве, он посчитан один раз — всё хорошо. Если ровно в двух, его сосчитали дважды, и минус при паре исправляет счёт. Но элемент тройного пересечения прошёл через сложение трижды и через все три вычитания тоже трижды: $3-3=0$, он исчез совсем. Возвращающий плюс в конце ставит его на место — ровно один раз. Формула устроена как весы: каждый знак компенсирует перегиб предыдущего.

Числовой прогон со спортивными секциями: в отряде плаванием занимаются $18$ человек, шахматами $13$, волейболом $16$; плавание и шахматы совмещают $7$, плавание и волейбол $8$, шахматы и волейбол $5$, все три секции — $2$. Считаем: $18+13+16=47$; $47-7-8-5=27$; $27+2=29$. Хоть чем-то заняты $29$ человек — цифра, которую простое сложение завысило бы до $47$.

Диаграмма Венна здесь раскладывается на семь непересекающихся зон — и это лучший способ не запутаться в «ровно сколько». Чтобы найти, скажем, зону «только плавание и шахматы, без волейбола», из парного пересечения $|A\cap B|$ вычитают тройку: $7-2=5$. Каждая зона получается последовательным вычитанием «всего, что внутри», снизу вверх по размеру.

Как решить задачу про языки и ничего не потерять?#

Теперь полный прогон от условия до всех зон. В потоке из $100$ студентов английский изучают $45$, немецкий $30$, французский $20$. Английский с немецким совмещают $12$, английский с французским $8$, немецкий с французским $5$, все три языка — $3$. Вопросы: сколько студентов изучают хотя бы один язык, сколько не изучает ни одного, и сколько занято только английским?

Зональная таблица — это и есть ответ на любой вопрос экзаменатора: «ровно два языка» — $9+5+2=16$; «английский и ещё что-то» — $28+9+5+3=45$, тут ничего не вычиталось, потому что спросили про вхождение, а не про точную зону. Одна диаграмма закрывает все варианты формулировок.

Что даёт общий случай: суммы по всем подмножествам?#

Для $k$ множеств записей в формуле становится $2^k-1$: все непустые подмножества набора. Компактная запись — сумма по подмножествам $J$ множества номеров $\{1,2,\dots ,k\}$:

Проверим формулу «двоичным подсчётом» по диаграмме Эйлера–Венна. Каждому элементу универсума можно приписать бинарный код: входит он в $A_1$ или нет, в $A_2$ или нет — и так далее, всего $2^k$ кодов, по одному на зону диаграммы. Возьмём элемент, лежащий ровно в $m$ множествах. В сумму он вносит:

Это тождество Ньютона для бинома: сумма чередующихся биномиальных коэффициентов от $\left(\genfrac{}{}{0ex}{}{m}{1}\right)$ до $\left(\genfrac{}{}{0ex}{}{m}{m}\right)$ всегда равна единице. Проверьте на пальцах: при $m=3$ выходит $3-3+1=1$. При таком взгляде формула включений-исключений — не случайный набор знаков, а точный механизм: он сшивает $2^k$ непересекающихся зон в одно число, не считая ни одну зону дважды. Для $k=4$ слагаемых уже пятнадцать, и зональная таблица становится жизненно необходимой.

Классика этого уровня — подсчёт делимости. Сколько чисел от $1$ до $100$ делятся хотя бы на одно из чисел $2$, $3$, $5$? Множества кратных: $50$, $33$, $20$; попарные пересечения — кратные $6$, $10$, $15$ — дают $16$, $10$, $6$; тройное — кратные $30$ — их $3$. Итого $50+33+20-16-10-6+3=74$ числа. Вычитанием получаем $26$ чисел, взаимно простых с $30$, — так работает решето Эратосфена, и та же схема считает вероятности делимости в теории чисел. Потренироваться на готовых задачах можно в тренажёре комбинаторики, а подборка типовых условий с ответами собрана в задачах по комбинаторике.

Куда формула ведёт дальше: сюръекции и беспорядки?#

Сила формулы раскрывается, когда «хотя бы одно свойство отсутствует» превращается в перебор запрещённых событий. Первое классическое применение — подсчёт сюръекций: сколькими способами можно раздать $n$ различных предметов по $k$ различным ящикам так, чтобы ни один ящик не остался пустым? Всего раздач $k^n$, но среди них есть брак: пустой первый ящик, пустой второй… Пустые ящики и сыграют роль «множеств», которые мы вычитаем. Итоговая формула:

Прогон для $n=4$, $k=3$: $3^4-\left(\genfrac{}{}{0ex}{}{3}{1}\right)2^4+\left(\genfrac{}{}{0ex}{}{3}{2}\right)1^4-0=81-48+3=36$. Каждому из четырёх предметов — свой ящик, все три ящика заняты, и таких раздач ровно $36$. Приёмы работы с биномиальными коэффициентами и факториалами, которые здесь включаются, разобраны в уроке про перестановки, размещения и сочетания, а шпаргалка по ним лежит рядом с таблицей формул комбинаторики.

Второе применение — знаменитая задача о беспорядках, ей больше трёхсот лет: $n$ писем случайным образом разложили по $n$ конвертам с адресами. Сколько раскладок, в которых ни одно письмо не попало в свой конверт? Здесь запрещённые события — «$i$-е письмо на месте»; объединяем их той же формулой и получаем число беспорядков (деранжемент):

Числа выходят контринтуитивные: для $n=4$ это $24-24+12-4+1=9$ из $24$ раскладок, для $n=5$ — $44$ из $120$. Доля беспорядков $!n/n!$ стремится к $1/e\approx 0,368$, и уже при $n=5$ совпадение до второй цифры: $44/120\approx 0,367$. Чем больше писем, тем безнадёжнее угадать, «наверняка хоть кто-то доехал» — и тем ближе вероятность полного бардака к $37$ процентам.

Здесь же видна связь с принципом Дирихле. Он даёт экзистенциальный ответ: тринадцать человек и двенадцать месяцев гарантируют, что двое родились в одном месяце — размещений без совпадений просто не существует, их ноль. Формула включений-исключений идёт дальше и даёт количественный ответ: сколько раскладок избегает всех совпадений, если совпадения всё-таки возможны. Задача о беспорядках — это принцип Дирихле, переведённый из «да/нет» в точный подсчёт. Для быстрых вычислений у беспорядков есть и своя рекуррентность $!n=(n-1)(!(n-1)+!(n-2))$ — приёмы работы с такими соотношениями собраны в уроке про рекуррентные соотношения.

• Два множества: сложили мощности — вычли пересечение; три — добавили парные вычитания и вернули тройку
• Общий случай: $2^k-1$ слагаемых по всем непустым подмножествам, знак чередуется по мощности подмножества
• Бинарная проверка: элемент ровно в $m$ множествах учитывается ${\sum }_{j=1}^m(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{m}{j})=1$ раз
• Зоны диаграммы Венна считаются «снизу вверх»: от тройного пересечения к одиночным зонам
• Сюръекции и беспорядки — два классических приложения: формулы $\sum (-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n$ и $n!\sum (-1{)}^j/j!$
• «Хотя бы один» и «ровно один» — разные числа; перечитайте вопрос до того, как считать