Комбинаторика

Основные принципы счёта

Правило суммы: если A и B не пересекаются, |A∪B| = |A|+|B|. Правило произведения: последовательных выборов k₁, k₂, ...: k₁·k₂·...

Размещения A(n,k) = n!/(n−k)! (упорядоченный выбор k из n). Сочетания C(n,k) = n!/(k!(n−k)!) (неупорядоченный выбор).

Формула бинома Ньютона: (a+b)ⁿ = Σₖ C(n,k)aᵏbⁿ⁻ᵏ.

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

|A₁∪A₂∪...∪Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ...

Число дерangangements (перестановок без фиксированных точек): D(n) = n! Σₖ₌₀ⁿ (−1)ᵏ/k! ≈ n!/e.

Функция Эйлера φ(n) = число m ≤ n с НОД(m,n)=1 = n∏_{p|n}(1−1/p).

Через включение-исключение: φ(n) = n·(1−1/p₁)·(1−1/p₂)·...

Производящие функции

Обыкновенная производящая функция: f(x) = Σₙ aₙxⁿ.

Число разбиений n в слагаемые из множества S: коэффициент при xⁿ в ∏_{s∈S} 1/(1−xˢ).

Экспоненциальная производящая функция: f(x) = Σₙ aₙxⁿ/n! используется для меченых объектов.

Метод производящих функций превращает комбинаторные задачи в задачи анализа.

Принцип двойного счёта и тождества

Многие комбинаторные тождества доказываются двойным счётом — подсчётом одной и той же величины двумя способами. Пример: Σₖ₌₀ⁿ C(n,k) = 2ⁿ. Слева — сумма сочетаний. Справа — число подмножеств n-элементного множества (каждый элемент включён или нет: 2 выбора, 2ⁿ итого). Тождество Вандермонда C(m+n,r) = Σₖ C(m,k)C(n,r−k) доказывается выбором r людей из m мужчин и n женщин.

Тождество Паскаля: C(n,k) = C(n−1,k−1) + C(n−1,k). Смысл: k-элементный подмножество n-элементного множества либо содержит выделенный элемент (выбираем ещё k−1 из n−1), либо нет (выбираем k из n−1). Это рекуррентность для треугольника Паскаля.

Метод размещений с повторениями и мультисеты

Мультисет — коллекция с повторениями. Число k-элементных подмультисетов n-элементного множества: C(n+k−1, k) = «звёзды и палки» (stars and bars). Интерпретация: разместить k неразличимых шаров по n различимым ящикам. Пример: число решений x₁+x₂+x₃=10 в неотрицательных целых = C(12,2) = 66.

Многочленный коэффициент: C(n; k₁,k₂,...,kₘ) = n!/(k₁!k₂!...kₘ!) — число перестановок n элементов, где kᵢ элементов i-го типа. Обобщение бинома Ньютона: (x₁+...+xₘ)ⁿ = Σ C(n;k₁,...,kₘ)x₁^{k₁}...xₘ^{kₘ}.

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

Формула включений-исключений выводит точные формулы для задач с запретами. Хатчинсона числа дерангементов: D(n) = n!(1 − 1/1! + 1/2! − ... + (−1)ⁿ/n!) ≈ n!/e. При n → ∞: D(n)/n! → 1/e ≈ 0.368. Почти 37% перестановок — дерангементы.

Задача о счётчиках (problème des rencontres): Карты 1...n перемешаны, выигрываем, если i-я карта не на i-м месте ни для одного i. P(выигрыш) = D(n)/n! → 1/e. Эта задача, поставленная Монмором в 1708 году, — исторически первое применение включений-исключений.

В числовой теории функция Мёбиуса μ(n) — аналог принципа включений-исключений для мультипликативных функций: Σ_{d|n} μ(d) = [n=1]. Это позволяет «обращать» суммы: если g(n) = Σ_{d|n} f(d), то f(n) = Σ_{d|n} μ(d)g(n/d) — формула обращения Мёбиуса. Используется для подсчёта примитивных многочленов, числа взаимно простых пар и т.д.

Экстремальная комбинаторика

Теорема Турана: Максимальное число рёбер в графе из n вершин без клики Kₙ₊₁ — это граф Турана T(n,r): n вершин делятся на r равных долей, рёбра между разными долями. Число рёбер: e(T(n,r)) = (1−1/r)·n²/2. При r=2 (двудольный граф) это граф без треугольников.

Задача Завадского-Турана: Что максимальное число рёбер n-вершинного гиперграфа без полного k-дольного k-гиперграфа? Открытая задача для большинства случаев.

Лемма Сцемереди о регулярности (1975): Любой достаточно плотный граф можно разбить на ε-регулярные пары. Следствие: содержит арифметические прогрессии любой длины (теорема Сцемереди о натуральных числах). Регуляризационная лемма стала основным инструментом комбинаторики графов с плотностью.

Лемма Ловаса: метод алгебраической геометрии в комбинаторике

Теорема Ловаса о θ-функции (1979): Число независимости α(G) ≤ θ(G) ≤ χ̄(G) — введение нового параметра, вычисляемого за полиномиальное время (SDP). Доказательство теоремы Шаннона о пропускной способности пятиугольного канала. Метод полуопределённого программирования (SDP) теперь стандартен в теоретической информатике.

Коды с исправлением ошибок: конструкции

Линейный код [n,k,d]: n — длина кодового слова, k — размерность (размер сообщения), d — минимальное расстояние Хэмминга. Исправляет ⌊(d−1)/2⌋ ошибок. Граница Хэмминга: суммарный «шар» исправляемых ошибок ≤ 2ⁿ⁻ᵏ. Циклические коды: идеалы кольца ℤ₂[x]/(xⁿ−1). Порождающий многочлен g(x). БЧХ-коды: задаются корнями g(x) в расширении поля; исправляют гарантированно t ошибок при степени g ≥ 2t. Коды Рида-Соломона — частный случай БЧХ над GF(q), применяются в QR-кодах, CD/DVD.

Экстремальная комбинаторика и гипергрупповые тесты

Тест Поллинга: проверить n предметов на наличие дефектного, используя групповые тесты. Если число дефектных d мало: O(d log n) адаптивных тестов (двоичный поиск) достаточно. Неадаптивный: O(d²log n/log d) тестов (Кауц-Синглтон). Применяется в геномике (ДНК-пулинг), сетевой диагностике.

Численный пример: принцип включений-исключений

Задача: Среди чисел 1..120 найти количество кратных 2, 3 или 5.

Шаг 1: |A₂|=⌊120/2⌋=60; |A₃|=⌊120/3⌋=40; |A₅|=⌊120/5⌋=24.

Шаг 2: Попарные пересечения: |A₂∩A₃|=⌊120/6⌋=20; |A₂∩A₅|=⌊120/10⌋=12; |A₃∩A₅|=⌊120/15⌋=8.

Шаг 3: Тройное пересечение: |A₂∩A₃∩A₅|=⌊120/30⌋=4.

Шаг 4: ВИИ: |A₂∪A₃∪A₅|=60+40+24−20−12−8+4=88. Не кратных ни одному: 120−88=32. Проверка через функцию Эйлера: φ(30)=30·(1−1/2)·(1−1/3)·(1−1/5)=8 взаимно простых с 30 в каждом цикле из 30. За 4 цикла: 4·8=32 ✓. Беспорядки D(n)=n!·Σ_{k=0}^{n}(−1)ᵏ/k!: D(4)=4!·(1−1+1/2−1/6+1/24)=24·(9/24)=9 — ВИИ для перестановок без неподвижных точек.