Принцип включения-исключения

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

Формулировка

Для конечных множеств \(A_1, A_2, \dots, A_n\) мощность их объединения выражается формулой:

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

Знак каждого слагаемого определяется чётностью числа пересекаемых множеств: чётное число — минус, нечётное — плюс. Формула справедлива для любых конечных множеств, а также для мер (например, вероятностей, площадей, объёмов) в соответствующих пространствах.

История

Принцип включения-исключения в неявном виде использовался ещё в древности. В XVII веке французский математик Пьер де Ферма и английский математик Джон Валлис применяли его для подсчёта числа целых чисел, не делящихся на заданные простые числа. В явном виде формулу впервые опубликовал в 1713 году швейцарский математик Якоб Бернулли в своей книге «Искусство предположений» (Ars Conjectandi). В XIX веке принцип получил систематическое развитие в работах немецкого математика Абрахама де Муавра и французского математика Огюстена Луи Коши. Современную формулировку в терминах теории множеств дал немецкий математик Георг Кантор.

Доказательство

Доказательство проводится по индукции по числу множеств \(n\). Для двух множеств формула очевидна: \(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\). Для \(n\) множеств предполагается, что формула верна для \(n-1\) множеств, и затем применяется к объединению \(A_1 \cup A_2 \cup \cdots \cup A_{n-1}\) и множеству \(A_n\). После раскрытия скобок и группировки слагаемых получается требуемое выражение. Альтернативное доказательство использует подсчёт вклада каждого элемента объединения: элемент, принадлежащий ровно \(k\) множествам, учитывается в сумме ровно \(C_k^1 - C_k^2 + C_k^3 - \cdots + (-1)^{k-1} C_k^k = 1\) раз, что и доказывает формулу.

Частные случаи

Два множества

\[ |A \cup B| = |A| + |B| - |A \cap B|. \]

Три множества

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|. \]

Бесконечные множества и меры

Принцип обобщается на произвольные меры, включая вероятности, длины, площади и объёмы. Для вероятностного пространства:

\[ P\left(\bigcup_{i=1}^{n} A_i\right) = \sum_{i=1}^{n} P(A_i) - \sum_{i<j} P(A_i \cap A_j) + \cdots + (-1)^{n-1} P(A_1 \cap \cdots \cap A_n). \]

Примеры применения

Комбинаторика: подсчёт перестановок без неподвижных точек (задача о беспорядках)

Число перестановок \(n\) элементов, в которых ни один элемент не остаётся на своём месте (беспорядки), обозначается \(!n\) и вычисляется по формуле:

\[ !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \]

Принцип включения-исключения применяется к множествам \(A_i\) — перестановок, в которых \(i\)-й элемент остаётся на месте.

Теория чисел: функция Эйлера

Функция Эйлера \(\varphi(n)\) — количество натуральных чисел, не превосходящих \(n\) и взаимно простых с \(n\). Если \(n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\) — разложение на простые множители, то

\[ \varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right). \]

Формула получается применением принципа включения-исключения к множествам чисел, делящихся на каждое из простых \(p_i\).

Теория вероятностей: задача о совпадениях

Вероятность того, что в случайной перестановке \(n\) элементов хотя бы один элемент останется на своём месте, равна

\[ P = 1 - \frac{!n}{n!} = \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}. \]

При больших \(n\) эта вероятность стремится к \(1 - 1/e \approx 0,632\).

Обобщения

Принцип включения-исключения для мер

Формула справедлива для любых аддитивных мер, в том числе для вероятностей, длин, площадей, объёмов. В теории меры она является частным случаем формулы Сильвестра — Галлея.

Принцип включения-исключения для бесконечных множеств

Для бесконечных множеств принцип применяется, если все пересечения конечны или определены соответствующие мощности (например, для счётных множеств). В общем случае требуется аккуратное обращение с бесконечностями.

Принцип включения-исключения в комбинаторике перечислений

Существуют обобщения для подсчёта числа объектов, удовлетворяющих нескольким свойствам, с учётом весов и знаков. Эти обобщения используются в теории графов, комбинаторной топологии и статистической физике.

Критика и ограничения

Принцип включения-исключения является точным, но его практическое применение затруднено при большом числе множеств, так как количество слагаемых растёт экспоненциально (\(2^n - 1\)). Для \(n = 10\) требуется вычислить 1023 слагаемых, что делает ручной подсчёт неэффективным. В таких случаях используются приближённые методы, например, метод Монте-Карло или решётчатые алгоритмы. Кроме того, формула требует точного знания мощностей всех пересечений, что не всегда возможно.

Применение в информатике

В информатике принцип включения-исключения используется для:

• подсчёта числа целых чисел, не делящихся на заданные простые числа (решето Эратосфена с включением-исключением);
• анализа сложности алгоритмов, связанных с перебором подмножеств;
• вычисления вероятностей в задачах надёжности систем;
• решения задач о покрытиях и раскрасках графов.

Применение в статистике

В статистике принцип применяется для оценки вероятностей сложных событий, например, при анализе зависимостей между несколькими тестами или при расчёте доверительных интервалов для множественных сравнений.

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

В теории вероятностей принцип включения-исключения является основой для вычисления вероятностей объединения событий, особенно в задачах о совпадениях, о днях рождения, о беспорядках и о случайных отображениях.

Интересные факты

• Принцип включения-исключения является частным случаем более общей формулы обращения Мёбиуса на частично упорядоченных множествах.
• В комбинаторике существует аналог для подсчёта числа элементов, не принадлежащих ни одному из множеств (принцип дополнения).
• Формула включения-исключения для вероятностей была впервые сформулирована французским математиком Симеоном Дени Пуассоном в 1837 году.
• В русской математической литературе принцип также называют формулой включений и исключений или формулой Сильвестра — Галлея.

Источники

• Бернулли Я. Искусство предположений. — 1713.
• Холл М. Комбинаторика. — М.: Мир, 1970.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. — М.: Мир, 1998.
• Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969.
• Рыбников К. А. Введение в комбинаторный анализ. — М.: Изд-во МГУ, 1985.