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

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

Метод существует как отдельная единица потому, что он применим в трёх совершенно разных контекстах: (1) прямой подсчёт объектов с запрещёнными свойствами, (2) задачи о перестановках без неподвижных точек (беспорядки), (3) подсчёт сюръекций и задачи теории чисел (функция Эйлера). Формула везде одна, но применяется по-разному.

Принцип включений-исключений — это алгоритм компенсации: каждый элемент, принадлежащий ровно $k$ из $n$ множеств, будет посчитан в итоговой сумме ровно $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \ldots = 1$ раз (что следует из биномиального тождества $(1-1)^k = 0$ при $k \geq 1$). Это и есть математическое объяснение, почему чередование знаков исправляет двойной счёт.

Триггер на олимпиаде: условие содержит слова «хотя бы одно», «ни одно из свойств», «не делится ни на одно из», «никакой из», «сколько перестановок таких, что».

• ФВК для двух множеств. $|A \cup B| = |A| + |B| - |A \cap B|$. Условие: любые два конечных множества. Когда использовать: задача с двумя свойствами (делится на 2 или на 3, красный или синий).

• ФВК для трёх множеств. $|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$. Условие: три конечных множества. Когда использовать: три запрещённых свойства.

• Общая формула для $n$ множеств.$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{i}|A_i| - \sum_{iУсловие: $n$ конечных множеств. Когда использовать: задачи с несколькими делителями, запрещёнными позициями.

• Формула беспорядков (дерандомизация). Число перестановок $n$ элементов без неподвижных точек:$$D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} = n!\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right).$$ При больших $n$: $D_n \approx n!/e$. Условие: перестановки, в которых ни один элемент не стоит на своём месте. Когда использовать: задачи про конверты и письма, шляпы и гардероб, рассадку.

• Число сюръекций из $n$-элементного множества в $k$-элементное:$$\text{Surj}(n,k) = \sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n.$$ Условие: $n \geq k$, функции из одного конечного множества в другое. Когда использовать: «раздать $n$ различных предметов по $k$ ящикам так, чтобы ни один ящик не остался пустым».

• Функция Эйлера через ФВК. Для $n = p_1^{a_1}\cdots p_m^{a_m}$:$$\varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$ Когда использовать: подсчёт чисел от 1 до $N$, взаимно простых с $N$.

• Переформулировать через дополнение: вместо «нет ни одного запрещённого» считать «хотя бы одно запрещённое» через $|A_1 \cup \ldots \cup A_k|$, а затем вычесть из общего.

• Определить множества $A_i$ как «объекты, обладающие $i$-м запрещённым свойством». Чётко записать, что такое $A_i$, $A_i \cap A_j$, до начала подсчёта.

• Вычислить $|A_{i_1} \cap \cdots \cap A_{i_r}|$ для пересечений: в задачах с делителями — НОК, в задачах с позициями — число перестановок с фиксированными позициями.

• Применить симметрию: если все $|A_i|$ равны, все $|A_i \cap A_j|$ равны, — формула упрощается до:$$\left|\overline{A_1}\cap\cdots\cap\overline{A_n}\right| = \sum_{k=0}^{n}(-1)^k\binom{n}{k}f(k),$$ где $f(k)$ — мощность типичного пересечения $k$ множеств.

• Для беспорядков: выводить формулу $D_n$ прямо на месте через ФВК, где $A_i$ = «$i$-й элемент стоит на своём месте», $|A_i| = (n-1)!$, $|A_i \cap A_j| = (n-2)!$.

• Для числа чисел, взаимно простых с $N$: разложить $N$ на простые множители $p_1,\ldots,p_m$ и использовать формулу $\varphi(N) = N(1-1/p_1)\cdots(1-1/p_m)$ — каждый множитель получается применением ФВК для делимости на $p_i$.

• Проверка по малым случаям: до применения формулы для $n=3,4$ проверьте руками — это страхует от ошибки в знаках.

Поверхностные признаки (что буквально написано):
- «Сколько чисел от 1 до $N$ не делятся ни на одно из $p_1, \ldots, p_k$»
- «Сколькими способами можно рассадить / разложить / раздать так, чтобы никто не оказался на своём месте»
- «Найдите число перестановок, в которых ни один из элементов не стоит на исходном месте»
- «Хотя бы одно из условий выполнено» или «ни одно из условий не выполнено»

Структурные признаки (форма выражения, объекты):
- Несколько «запрещённых» свойств, и объекты могут обладать несколькими одновременно
- Перестановки с ограничениями на позиции
- Счётные задачи с условием делимости на несколько чисел
- Задачи, где прямой перебор слишком велик, но «запрещённые» случаи структурированы

Цель задачи (что от тебя хотят):
- Подсчитать объекты, не обладающие ни одним из перечисленных свойств
- Найти число способов выполнить действие при нескольких запретах
- Вычислить $\varphi(N)$ или подобный комбинаторный инвариант

Задача 1. Беспорядки: пять человек и шляпы

Условие: Пятеро знакомых сдали шляпы в гардероб. Гардеробщик выдал их в случайном порядке. Найдите вероятность того, что никто не получит свою шляпу.

Источник: классическая олимпиадная задача (ВсОШ, районный этап, комбинаторика)

Как думать (рассуждение ученика$):
1. $Что я вижу? Перестановки 5 элементов, запрет: ни один элемент не стоит на своём месте. Слово «никто» — триггер на беспорядок.$2. *$Метод: принцип включений-исключений. Обозначу $A_i$ = «$i$-й человек получил свою шляпу». Хочу $|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}\cap\overline{A_4}\cap\overline{A_5}|$.$3. *$Первый ход: применю ФВК: $D_5 = 5! - \binom{5}{1}4! + \binom{5}{2}3! - \binom{5}{3}2! + \binom{5}{4}1! - \binom{5}{5}0!$.$4. *$Ключевая идея:* $|A_i| = 4!$ (фиксируем позицию $i$, остальных переставляем произвольно); $|A_i \cap A_j| = 3!$; все пересечения одного размера — используем симметрию.

Решение:

Пусть $A_i$ — «$i$-й человек получил свою шляпу». Тогда:$$D_5 = 5! - \binom{5}{1}4! + \binom{5}{2}3! - \binom{5}{3}2! + \binom{5}{4}1! - \binom{5}{5}0!$$ $$= 120 - 5\cdot24 + 10\cdot6 - 10\cdot2 + 5\cdot1 - 1$$ $= 120 - 120 + 60 - 20 + 5 - 1 = 44.$

Вероятность:$$P = \frac{D_5}{5!} = \frac{44}{120} = \frac{11}{30}.$$

Альтернативно: $D_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}$, поэтому$$D_5 = 120\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 120 \cdot \frac{44}{120} = 44.$$

Ответ: $D_5 = 44$ беспорядка; вероятность равна $\dfrac{11}{30}$.

Что в этой задаче было главным: слово «никто» сразу указывает на дополнение, затем симметрия множеств $A_i$ позволяет не выписывать каждое пересечение вручную, а использовать биномиальные коэффициенты.

Задача 2. Числа, взаимно простые с 60

Условие: Сколько натуральных чисел от 1 до 100 взаимно просты с 60?

Источник: тренировочная (в духе ВсОШ, теория чисел)

Как думать (рассуждение ученика$):
1. $Что я вижу?* Нужно подсчитать числа без запрещённых делителей. $60 = 2^2 \cdot 3 \cdot 5$, простые делители: $2, 3, 5$. Триггер: «взаимно просты» = «не делятся ни на 2, ни на 3, ни на 5».$2. *$Метод: ФВК. Обозначу $A_2$ = «делится на 2», $A_3$ = «делится на 3», $A_5$ = «делится на 5».$3. *$Первый ход: $|A_p \cap [1,100]| = \lfloor 100/p \rfloor$.$4. *$Ключевая идея: $|A_i \cap A_j|$ — делимость на НОК; применяю ФВК.

Решение:

Простые делители числа 60: $\{2, 3, 5\}$. Обозначим:
- $|A_2| = \lfloor 100/2 \rfloor = 50$ - $|A_3| = \lfloor 100/3 \rfloor = 33$ - $|A_5| = \lfloor 100/5 \rfloor = 20$ - $|A_2 \cap A_3| = \lfloor 100/6 \rfloor = 16$ - $|A_2 \cap A_5| = \lfloor 100/10 \rfloor = 10$ - $|A_3 \cap A_5| = \lfloor 100/15 \rfloor = 6$ - $|A_2 \cap A_3 \cap A_5| = \lfloor 100/30 \rfloor = 3$

По ФВК:$$|A_2 \cup A_3 \cup A_5| = 50+33+20-16-10-6+3 = 74.$$

Чисел, не делящихся ни на 2, ни на 3, ни на 5:$100 - 74 = 26.$

Проверка через $\varphi$: $\varphi(60) = 60(1-\tfrac{1}{2})(1-\tfrac{1}{3})(1-\tfrac{1}{5}) = 16$. Из 60 чисел 16 взаимно просты с 60. Из 100 чисел имеем $\lfloor 100/60 \rfloor = 1$ полный блок из 60 (даёт 16 чисел) плюс остаток $\{61,\ldots,100\}$ — 40 чисел. Среди них взаимно простых с 60: $\lfloor 40/60 \cdot 16 \rfloor$... нет, лучше вернуться к прямому ФВК.

Ответ: 26 натуральных чисел от 1 до 100 взаимно просты с 60.

Что в этой задаче было главным: разложение числа 60 на простые множители даёт ровно те делители, на которые проверяется взаимная простота; пересечения $A_i \cap A_j$ — это делимость на НОК, что мгновенно вычисляется.

• Ошибка: неправильные знаки. Пишут $|A|+|B|+|C|-|A\cap B\cap C|$ вместо полной формулы. → Почему неверно: пропущены попарные пересечения $|A\cap B|$, $|A\cap C|$, $|B\cap C|$. → Как избежать: всегда выписывайте формулу полностью с биномиальными коэффициентами перед подстановкой чисел.

• Ошибка: забывают про дополнение. Считают $|A_1 \cup \ldots \cup A_n|$ вместо $N - |A_1 \cup \ldots \cup A_n|$. → Почему неверно: задача просит «ни одного», а не «хотя бы одно». → Как избежать: перед началом решения явно написать: «ищу $N - |A_1 \cup \ldots \cup A_n|$».

• Ошибка: считают $|A_i \cap A_j|$ не через НОК, а через произведение. Например, $|A_2 \cap A_3| = \lfloor N/6 \rfloor$, а пишут $\lfloor N/2 \rfloor \cdot \lfloor N/3 \rfloor / N$. → Как избежать: пересечение «делится на $p$» и «делится на $q$» = «делится на $\text{lcm}(p,q)$»; при $\gcd(p,q)=1$ это просто $pq$.

• Ошибка: в задаче о беспорядках путают $D_n$ и $n!/e$. Приближение $D_n \approx n!/e$ не является точным при малых $n$. → Как избежать: при $n \leq 10$ всегда вычисляйте точное значение по формуле с чередующейся суммой.

• Ошибка: при подсчёте сюръекций забывают делитель $k!$ (путают с числом разбиений). Формула $\text{Surj}(n,k)$ считает упорядоченные образы; если образы неупорядочены — это числа Стирлинга второго рода $S(n,k)$, и $\text{Surj}(n,k) = k! \cdot S(n,k)$. → Как избежать: читайте условие: различимы ли «ящики» (= множество значений функции).

• Ошибка: неверное определение множеств $A_i$. Если $A_i$ не определены однозначно (например, $A_i$ = «нарушено $i$-е условие»), формула может не работать. → Как избежать: до начала вычислений чётко запишите $A_i$ как подмножество основного множества объектов.