Принцип включения-исключения: формула и примеры

Когда нужно посчитать, сколько объектов удовлетворяют хотя бы одному из нескольких условий, прямой перебор часто невозможен - объекты пересекаются. Принцип включения-исключения (ПВИ) даёт точную формулу: сложить мощности всех множеств, вычесть попарные пересечения, прибавить тройные и так далее, чередуя знаки. Это один из ключевых инструментов дискретной математики и комбинаторики: с ним решаются задачи на делимость чисел, вероятность объединения событий, число сюръекций и задачи о беспорядках. Попробуй калькулятор ниже - он мгновенно покажет, как меняется объединение при разных пересечениях, и разложит результат по слагаемым формулы.

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

Для двух конечных множеств $A$ и $B$ формула выглядит так:

$$|A \cup B| = |A| + |B| - |A \cap B|.$$

Смысл прост: если сложить $|A|$ и $|B|$, элементы из пересечения $A \cap B$ войдут в сумму дважды. Чтобы каждый элемент считался ровно один раз, вычитаем $|A \cap B|$.

Для трёх множеств $A$, $B$, $C$:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

Здесь тройное пересечение прибавляется обратно: первые три слагаемых учитывают его трижды, три вычитания убирают трижды - в итоге оно исчезло, хотя должно стоять один раз. Знак $+|A \cap B \cap C|$ восстанавливает баланс.

Общая формула для $n$ множеств $A_1, A_2, \ldots, A_n$:

$$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i}|A_i| - \sum_{i < j}|A_i \cap A_j| + \sum_{i < j < k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n|.$$

Знаки чередуются: суммы нечётного числа множеств входят со знаком $+$, чётного - со знаком $-$.

Рассчитать для своей задачи

Вывод через диаграмму Венна

Нагляднее всего ПВИ виден на диаграмме Венна. Разобьём объединение $A \cup B$ на три непересекающиеся зоны: «только A», «только B», «A и B». Прямое суммирование $|A| + |B|$ покрывает зону пересечения дважды. Вычитание $|A \cap B|$ снимает лишний слой - каждая зона считается ровно раз.

Для трёх кругов зона тройного пересечения при прямом суммировании входит трижды (от $|A|$, $|B|$, $|C|$). После вычитания трёх попарных пересечений она убирается трижды - итого ноль. Добавляем $+|A \cap B \cap C|$, чтобы она вошла ровно однажды.

Рассчитать для своей задачи

Именно это чередование знаков «включить - исключить - включить» и дало принципу его название.

Задачи на делимость

Классическое применение ПВИ - подсчёт чисел от 1 до $N$, кратных хотя бы одному из нескольких простых.

Пример. Сколько чисел от 1 до 100 делятся на 2, 3 или 5?

Обозначим $A$ - кратные 2, $B$ - кратные 3, $C$ - кратные 5. Тогда:

$$|A| = \left\lfloor\frac{100}{2}\right\rfloor = 50, \quad |B| = \left\lfloor\frac{100}{3}\right\rfloor = 33, \quad |C| = \left\lfloor\frac{100}{5}\right\rfloor = 20.$$

Попарные пересечения - кратные НОК:

$$|A \cap B| = \left\lfloor\frac{100}{6}\right\rfloor = 16, \quad |A \cap C| = \left\lfloor\frac{100}{10}\right\rfloor = 10, \quad |B \cap C| = \left\lfloor\frac{100}{15}\right\rfloor = 6.$$

Тройное пересечение - кратные 30:

$$|A \cap B \cap C| = \left\lfloor\frac{100}{30}\right\rfloor = 3.$$

По ПВИ:

$$|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.$$

Этот тип задачи - «решето» - лежит в основе решета Эратосфена и алгоритмов теории чисел.

Применение к вероятностям

Принцип включения-исключения переносится на вероятности напрямую: каждая мощность заменяется вероятностью события. Для двух событий $A$ и $B$:

$$P(A \cup B) = P(A) + P(B) - P(A \cap B).$$

Для независимых событий $P(A \cap B) = P(A) \cdot P(B)$, но ПВИ работает и без независимости - нужно лишь знать вероятность совместного наступления.

Формула для трёх событий:

$$P(A \cup B \cup C) = P(A)+P(B)+P(C) - P(AB) - P(AC) - P(BC) + P(ABC),$$

где $P(AB) = P(A \cap B)$ и так далее.

Пример. Студент знает ответ на вопрос A с вероятностью 0,7, на B - 0,6, на оба - 0,4. Вероятность ответить хотя бы на один:

$$P(A \cup B) = 0{,}7 + 0{,}6 - 0{,}4 = 0{,}9.$$

Число сюръекций и задача о беспорядках

ПВИ лежит в основе формулы числа сюръекций (накрывающих функций) из $n$-элементного множества в $k$-элементное:

$$\text{Sur}(n, k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n.$$

Здесь знакочередующаяся сумма - прямое следствие ПВИ: мы начинаем с $k^n$ всех функций, затем вычитаем те, что «забывают» хотя бы один элемент кодомена, прибавляем забывшие хотя бы два, и так далее.

Задача о беспорядках ($D_n$ - число перестановок $n$ элементов без неподвижных точек) тоже решается через ПВИ:

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{n!}{e}.$$

Эта формула показывает, что примерно $1/e \approx 36{,}8\%$ случайных перестановок не содержат ни одного неподвижного элемента.

Пример из теории вероятностей: вероятность хотя бы одной ошибки

Принцип включения-исключения часто применяют для оценки вероятности хотя бы одного из нескольких независимых негативных событий. Пусть $A_i$ - событие «$i$-й элемент содержит ошибку», $P(A_i) = p_i$. Тогда вероятность того, что хотя бы один элемент из $n$ содержит ошибку, - это $P(A_1 \cup A_2 \cup \cdots \cup A_n)$.

Для независимых событий проще посчитать через дополнение:

$$P(A_1 \cup \cdots \cup A_n) = 1 - P(\overline{A_1} \cap \cdots \cap \overline{A_n}) = 1 - \prod_{i=1}^{n}(1-p_i).$$

Но ПВИ даёт тот же результат при раскрытии произведения по формуле Ньютона. Более того, когда события зависимы (что типично для испытаний, общих данных), только ПВИ в исходном виде остаётся верным.

Задача. Три устройства отказывают независимо с вероятностями 0,1, 0,2 и 0,15. Найти вероятность хотя бы одного отказа.

$$P(A \cup B \cup C) = 0{,}1 + 0{,}2 + 0{,}15 - (0{,}1 \cdot 0{,}2) - (0{,}1 \cdot 0{,}15) - (0{,}2 \cdot 0{,}15) + (0{,}1 \cdot 0{,}2 \cdot 0{,}15).$$ $$= 0{,}45 - 0{,}02 - 0{,}015 - 0{,}03 + 0{,}003 = 0{,}388.$$

Проверка через дополнение: $1 - 0{,}9 \cdot 0{,}8 \cdot 0{,}85 = 1 - 0{,}612 = 0{,}388$. Результаты совпадают.

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

• Забыть тройные пересечения при трёх множествах. Студенты часто останавливаются на $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|$, пропуская $+|A\cap B\cap C|$. Это заниженный результат.
• Неверный знак у многократных пересечений. Общая закономерность: пересечение $k$ множеств входит со знаком $(-1)^{k+1}$, то есть нечётное число - плюс, чётное - минус.
• Неправильный подсчёт кратных через НОК. При задачах на делимость пересечение «кратные $p$ и кратные $q$» - это кратные $\text{НОК}(p, q)$, а не $p \cdot q$ (если $p$ и $q$ не взаимно просты).
• Применение формулы вероятностей без учёта зависимости. $P(A \cap B) \ne P(A) \cdot P(B)$ для зависимых событий; нужно использовать условную вероятность или знать совместную.
• Отрицательный результат при неверных данных. Если заданные пересечения противоречат ограничению $|A \cap B| \le \min(|A|, |B|)$, формула даст некорректный ответ. Всегда проверяй согласованность исходных данных.

FAQ

Для скольких множеств работает принцип включения-исключения?

Для любого конечного числа множеств $n$. Формула содержит $2^n - 1$ слагаемых (все непустые подмножества индексов), знак каждого определяется чётностью мощности подмножества. На практике для $n \ge 5$ вычисления громоздки, но алгоритмически принцип применяется и для больших $n$ - например, в задачах о покрытиях и в алгоритме Сорпа.

Как ПВИ связан с формулой Мёбиуса?

Принцип включения-исключения - частный случай обращения Мёбиуса на решётке подмножеств. Формула Мёбиуса обобщает ПВИ на произвольные частично упорядоченные множества; знакочередующийся коэффициент $(-1)^{k}$ - это функция Мёбиуса булевой решётки.

Можно ли применять ПВИ, если множества бесконечны?

В общем случае - нет: разности бесконечных кардиналов не определены стандартным образом. Но если все пересечения конечны или выполнены специальные условия (мера Лебега, $\sigma$-аддитивность), аналог ПВИ работает. Для вероятностей формула верна всегда, так как вероятности - числа из $[0,1]$.

Коротко

Принцип включения-исключения - точная формула для мощности объединения конечных множеств: суммируем одиночные мощности, вычитаем попарные пересечения, прибавляем тройные и так далее со знаком $(-1)^{k+1}$. Для двух множеств: $|A \cup B| = |A| + |B| - |A \cap B|$. Для трёх добавляется тройное пересечение с плюсом. Метод универсален: он решает задачи на делимость, вероятность объединения событий, число сюръекций и беспорядков. Главное - не забыть последнее слагаемое и проверить согласованность заданных пересечений.