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

Цели урока

• Применять PIE для |A∪B∪C| и обобщать формулу на n множеств через знакочередующиеся суммы
• Считать число дерангементов Dₙ через PIE и распознавать предельное соотношение Dₙ/n! → 1/e
• Считать сюръекции Surj(n,k) через PIE и связывать их с числами Стирлинга 2-го рода: Surj(n,k) = k!·S(n,k)
• Вычислять функцию Эйлера φ(n) через PIE по простым делителям и видеть её роль в RSA, в PostgreSQL OR-cardinality, в Spotify shuffle
• Применять PIE как технику derandomization (Naor, 1990s) и unbiased estimator (Karp-Luby, 1985) для DNF #P

PostgreSQL planner оценивает `WHERE x>10 OR y<5` через PIE и выбирает плана сканирования. Spotify shuffle отбраковывает перестановки, где трек остался на месте - доля валидных стремится к 1/e и не зависит от длины плейлиста. Naor (1990s) превратил PIE в инструмент derandomization - превратив рандомизированные алгоритмы в детерминированные. Один и тот же знакочередующийся ряд режет поверх криптографии, баз данных, токенизации LLM и теории чисел.

• **PostgreSQL cardinality estimation:** оценщик селективности WHERE с OR использует PIE по корреляционной статистике предикатов
• **Bloom filter analysis:** вероятность false positive раскладывается через PIE по битам хеш-функций
• **Spotify / YouTube shuffle:** rejection-семплинг дерангементов даёт fairness, среднее число попыток ≈ e ≈ 2.718
• **Secret Santa:** Фишер-Йейтс + проверка fixed points = практический derangement-генератор
• **Sieve of Eratosthenes:** буквальное PIE по простым делителям, основа быстрого факторинг-теста
• **RSA шифрование:** φ(n) = (p−1)(q−1) - PIE определяет ключевую пару (e, d)
• **BPE-токенизация LLM:** Bell numbers через S(n,k) считают разбиения merge-кандидатов
• **Derandomization Naor 1990s:** PIE превращает рандомизированный алгоритм в детерминированный

Предварительные знания

• Generating Functions

Абрахам де Муавр и первая систематическая запись PIE

В 1718 году в книге "The Doctrine of Chances" де Муавр впервые выписал общую формулу для вероятности объединения n событий: знакочередующуюся сумму одиночных, попарных, тройных и далее пересечений. Та же книга разобрала задачу о совпадениях (problème des rencontres), параллельно изученную Монмором и Николаем Бернулли в 1708-1713 годах: формула P(хотя бы одно совпадение) → 1 - 1/e дала первый известный пример константы e в комбинаторной задаче. Спустя триста лет тот же знакочередующийся приём оценивает RSA-параметр φ(n), OR-cardinality в планировщике PostgreSQL и derandomization рандомизированных алгоритмов по Наору.

Формула включений-исключений (PIE): знакочередующиеся суммы

PostgreSQL обрабатывает запрос `WHERE x>10 OR y<5 OR z=42` и должен оценить cardinality - сколько строк вернёт ответ. Прямое сложение трёх селективностей завышает результат: пересечения учтены дважды. Решение - принцип включений-исключений (PIE): сложить одиночные, вычесть попарные, прибавить тройные. Тот же приём - в анализе Bloom filter: вероятность false positive раскладывается через PIE по битам хеш-функций.

Простое сложение |A| + |B| учитывает A∩B дважды. PIE правит ошибку через знакочередующиеся суммы. Эратосфен сделал это первым: его решето - буквальное PIE по простым делителям.

**Принцип включений-исключений (PIE):** |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ... Через суммы подмножеств: = Σ (−1)^(|S|+1) · |∩ᵢ∈S Aᵢ| Для двух множеств: |A ∪ B| = |A| + |B| − |A ∩ B|

Почему PIE работает? Рассмотрим элемент x, принадлежащий ровно k из n множеств. PIE учитывает его: C(k,1) − C(k,2) + C(k,3) − ... = 1 (по биномиальной теореме: (1-1)ᵏ = 0, значит Σ(-1)ʲC(k,j) = 1 при k≥1). Элементы вне всех множеств учитываются с суммой 0. В query-планировщике PostgreSQL это превращается в формулу для селективности предикатов с OR: оценщик честно вычитает попарные пересечения по corr-стате.

**Мнемоника PIE:** «добавляем - вычитаем - добавляем - вычитаем...». На каждом уровне вложенности знак меняется. Элемент в k множествах считается C(k,1)−C(k,2)+...=1 раз - ровно один. Тот же ритм в Naor (1990s) использовал для derandomization: рандомизированный алгоритм заменяется детерминированным через PIE по событиям.

Дерангементы: перестановки без неподвижных точек

Spotify Shuffle, YouTube Mix, Secret Santa - всем нужно одно и то же: перемешать список так, чтобы элемент не остался на своём месте. Дерангемент - именно такая перестановка. Доля дерангементов среди всех n! перестановок стремится к 1/e ≈ 36.8% при n→∞. Цифра не зависит от n - и это сама по себе сенсация.

Алгоритм Фишера-Йейтса даёт равномерную случайную перестановку. Но для Secret Santa нужно отбрасывать те, где кто-то вытянул себя. PIE даёт точную долю годных и среднее число попыток - примерно e ≈ 2.718. Поэтому валидация Фишера-Йейтса сводится к подсчёту фиксированных точек.

**Число дерангементов Dₙ:** Dₙ = n! · Σₖ₌₀ⁿ (-1)ᵏ/k! = n! · (1 − 1/1! + 1/2! − 1/3! + ... + (−1)ⁿ/n!) Асимптотика: Dₙ → n!/e при n→∞ Примерно 1/e ≈ 36.8% всех перестановок - дерангементы. Рекуррентность: Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂), D₁=0, D₂=1

**PIE для дерангементов:** определяем Aᵢ = «элемент i стоит на своём месте». Тогда |дерангементов| = |¬A₁ ∩ ¬A₂ ∩ ... ∩ ¬Aₙ| = n! − |A₁ ∪ ... ∪ Aₙ|. Применяем PIE к |A₁ ∪ ... ∪ Aₙ|: |Aᵢ₁∩...∩Aᵢₖ| = (n−k)! - фиксируем k позиций, остальные любые. Этот же приём в Spotify shuffle: rejection-семплинг отбраковывает плохие перестановки и держит fairness.

Сюръекции: PIE для подсчёта «на» функций

Сюръекция - функция f: A -> B, где каждый элемент B покрыт хотя бы одним элементом A. Подсчёт сюръекций = подсчёт кодовых схем без потерянных кодовых слов = подсчёт способов разложить N задач по K командам без простаивающих. И это та же машина: PIE по «не покрытым» элементам цели. Связка с числами Стирлинга S(n,k) даёт мост в BPE-токенизацию: Bell numbers Bₙ = ΣS(n,k) считают разбиения кандидатов на merge.

**Число сюръекций f: [n] -> [k]:** Surj(n, k) = Σⱼ₌₀ᵏ (−1)ʲ · C(k, j) · (k − j)ⁿ Идея PIE: пусть Aᵢ = «элемент i ∈ B не покрыт». Нужно |¬A₁ ∩ ... ∩ ¬Aₖ|. По PIE вычитаем плохие функции.

**Связь с числами Стирлинга:** число разбиений n-элементного множества на ровно k непустых подмножеств - это числа Стирлинга 2-го рода S(n,k). Сюръекции и числа Стирлинга связаны формулой: Surj(n, k) = k! · S(n, k). Bell numbers Bₙ = Σ S(n,k) считают все разбиения - в clustering, в анализе topic modeling, в подсчёте merge-стратегий BPE-токенизатора.

Функция Эйлера φ(n): PIE для взаимно простых

Функция Эйлера φ(n) - число целых от 1 до n, взаимно простых с n. Появляется в RSA-шифровании: φ(n) задаёт период мультипликативной группы ℤₙ и определяет пару (e, d). Её вычисление - буквальное приложение PIE к простым делителям. Та же идея в combinatorial optimization: подсчёт MIS (maximum independent sets) и randomized counting через альтернирующие суммы.

**Функция Эйлера через PIE:** Если n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ, то: φ(n) = n · ∏(1 − 1/pᵢ) = n · (1 − 1/p₁) · (1 − 1/p₂) · ... · (1 − 1/pₖ) Aᵢ = «делится на pᵢ». PIE даёт |A₁ ∪ ... ∪ Aₖ|, вычитаем из n.

**PIE-интерпретация φ(n):** множество [1..n]. Aᵢ = «кратно pᵢ». Взаимно простые - элементы вне всех Aᵢ. PIE даёт |A₁∪...∪Aₖ|, вычитаем из n. Множитель (1 − 1/p) - это 1 − |Aₚ|/n из PIE. Тот же приём в randomized counting (Karp-Luby 1985): альтернирующая сумма даёт unbiased estimator для DNF #P.

Ключевые идеи

• **PIE:** |A₁∪...∪Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ... Знаки чередуются, каждый элемент считается ровно 1 раз. Приложения: query optimizer, Bloom filter, sieve of Eratosthenes.
• **Дерангементы:** Dₙ = n!·Σ(−1)ᵏ/k! -> n!/e. Ровно ~36.8% перестановок - дерангементы. Фишер-Йейтс + rejection = Secret Santa, Spotify shuffle.
• **Сюръекции:** Surj(n,k) = Σⱼ(−1)ʲ·C(k,j)·(k−j)ⁿ. Связаны с числами Стирлинга: Surj(n,k) = k!·S(n,k). Bell numbers - в BPE-токенизации.
• **Функция Эйлера:** φ(n) = n·∏(1−1/pᵢ) по простым делителям. Центральная в RSA, в randomized counting Karp-Luby.

Связанные темы

PIE проходит через всю дискретную математику и стыкуется с CS-applied:

• Производящие функции — PIE выводится через OGF: знакочередующиеся суммы возникают из (1−x)ᵏ в формальном произведении
• Комбинаторика: основы — Число сочетаний C(n,k) - ключевой инструмент в формулах PIE: именно столько подмножеств размера k нужно учесть
• Теория чисел и модульная арифметика — Функция Эйлера φ(n) - центральная в теореме Эйлера: aᵠ⁽ⁿ⁾ ≡ 1 (mod n), основа RSA
• Рандомизированные алгоритмы — PIE даёт derandomization: рандомизированный алгоритм заменяется детерминированным через альтернирующие суммы
• RSA: практическая криптография — RSA полностью опирается на φ(n), вычисленную через PIE по простым делителям

Вопросы для размышления

• Как с помощью PIE подсчитать число строк длины n над алфавитом {A,B,C}, в которых каждая буква встречается хотя бы один раз?
• Почему вероятность дерангемента стремится к 1/e независимо от n? Что это говорит о структуре перестановок?
• Как функция Эйлера связана с выбором открытого ключа e в RSA - почему нужно gcd(e, φ(n)) = 1?

Связанные уроки

• dm-06 — Производящие функции дают альтернативный путь к Dₙ и Surj(n,k)
• prob-02-combinatorics — Та же знакочередующаяся сумма в задачах о совпадениях
• crypto-25-rsa-practice — RSA опирается на функцию Эйлера φ(n), вычисленную через PIE
• alg-33-randomized — PIE даёт derandomization рандомизированных алгоритмов
• aie-04-tokens-context-window — Bell numbers считают разбиения BPE-merge кандидатов