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

Задачи счёта

Комбинаторика отвечает на вопрос: «Сколько?» — сколько различных объектов данного типа существует. Это фундаментально для теории алгоритмов, криптографии, статистики.

Число сюрьекций из n-элементного во m-элементное (m ≤ n): S(n,m) = Σₖ₌₀ᵐ (−1)ᵏ C(m,k)(m−k)ⁿ.

Числа Стирлинга второго рода S(n,k) — разбиение n-элементного множества на k непустых подмножеств. Рекуррентность: S(n,k) = k·S(n−1,k) + S(n−1,k−1).

Число всех разбиений: Bₙ = Σₖ S(n,k) — числа Белла.

Разбиения чисел

Разбиение числа n — способ представить n как сумму натуральных чисел (без учёта порядка).

p(n) — число разбиений. p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, ...

Рамануджан нашёл удивительные конгруэнции: p(5k+4) ≡ 0 (mod 5). Формула Харди–Рамануджана: p(n) ~ e^{π√(2n/3)} / (4n√3) — асимптотика через аналитику.

Комбинаторное тождество Вандермонда

C(m+n, r) = Σₖ₌₀ʳ C(m,k)C(n,r−k).

Доказательство: выбор r людей из m мужчин и n женщин.

Лемма Бёрнсайда

Число орбит при действии группы G на множестве X: |X/G| = (1/|G|) Σ_{g∈G} |X^g|, где X^g — неподвижные точки g.

Применение: число ожерелий из n бусин k цветов (при вращениях): (1/n) Σ_{d|n} φ(d)·k^{n/d}. Формула Пойа обобщает это на произвольные подстановки.

Комбинаторика на словах и последовательностях

Комбинаторика на словах изучает конечные последовательности (слова) над алфавитом. Слова де Брёйна: Циклическая последовательность над k-буквенным алфавитом, в которой каждое слово длины n встречается ровно раз. Длина — kⁿ. Эквивалентна эйлерову циклу в графе де Брёйна B(k,n): вершины — слова длины n−1, рёбра — слова длины n. Применяется в ДНК-секвенировании и криптографии (LFSR, линейные регистры сдвига).

Теорема Ван дер Вардена: При любом k-красоке натуральных чисел одноцветное подмножество содержит сколь угодно длинные арифметические прогрессии. Числа Ван дер Вардена W(r;k) — наименьшее N с этим свойством. W(2;3) = 9, W(2;4) = 35, W(2;5) = 178, W(2;6) = 1132. Рост катастрофически быстрый.

Метод производящих функций для сложных перечислений

Передаточные матрицы (Transfer matrix method): Для подсчёта путей в графе, тайлингов (мозаик), допустимых конфигураций. Если A — матрица переходов, то (Aⁿ)ᵢⱼ = число путей длины n из i в j. Для тайлинга m×n прямоугольника доминошками: передаточная матрица 2^m×2^m, ответ — определённый след.

Формула Кирхгофа через производящие функции: Число остовных деревьев T(G) = Σ_{T}∏_{e∈T} wₑ (взвешенная сумма) вычисляется через определитель взвешенного лапласиана. При единичных весах это обычная теорема Кирхгофа. Взвешенная версия используется в статистической физике (модель Изинга, разбиения).

Числа Белла и разбиения множеств

Числа Белла Bₙ считают число разбиений n-элементного множества на непустые подмножества: B₀=1, B₁=1, B₂=2, B₃=5, B₄=15, B₅=52. Рекуррентность через треугольник Белла (тот же принцип, что треугольник Паскаля). Экспоненциальная производящая функция: Σₙ Bₙxⁿ/n! = e^{eˣ−1}.

Применения: число способов разбить n различимых задач на неразличимые группы. Число разбиений множества переменных при символьных вычислениях. Количество эквивалентных конфигураций в физических системах.

Теорема Пойа и перечисление с симметриями

Теорема Пойа обобщает лемму Бёрнсайда, добавляя «вес» каждой конфигурации. Цикловый индекс группы G подстановок на n позициях: Z(G; x₁,...,xₙ) = (1/|G|)Σ_{g∈G} x₁^{c₁(g)}·...·xₙ^{cₙ(g)}, где cₖ(g) — число k-циклов в g. Для подсчёта раскрасок в m цветов: подставляем xₖ = m: Z(G; m,...,m).

Для ожерелий из n бусин при группе вращений Cₙ: Z(Cₙ) = (1/n)Σ_{d|n}φ(d)x_d^{n/d}. При n=6, m=3 цвета: число ожерелий = (1/6)(3⁶ + 3 + 2·3² + 2·3³) = (1/6)(729+3+18+54) = 134. Учитывая переворот (группа диэдра D₆): (134 + ...) / 2 ≈ 92 ожерелья.

Асимптотика разбиений и формула Харди-Рамануджана

Числа разбиений p(n) растут быстро: p(1)=1, p(5)=7, p(10)=42, p(100)=190569292. Формула Харди-Рамануджана (1918): p(n) ~ (1/4n√3)·e^{π√(2n/3)}. Первое точное асимптотическое выражение для нарастающей арифметической функции — один из триумфов аналитической числовой теории. Метод «Круга» (circle method) — разложение производящей функции по Фурье и оценка через особые точки на единичной окружности — стал универсальным инструментом.

Связь с физикой: число разбиений = число состояний идеального газа фермионов/бозонов в статистической механике. p(n) — это число уровней энергии системы при фиксированной суммарной энергии n. Это объясняет интерес физиков к точной формуле Харди-Рамануджана.

Группы симметрий и применения в химии

В химии число изомеров молекулы при фиксированной формуле вычисляется как число орбит при действии группы симметрий (вращений и отражений). Для алканов CₙH₂ₙ₊₂ (деревья с раскрашенными рёбрами) — это перечислительная задача с группой S₄ (тетраэдр). Полима производящая функция Пойа для подсчёта органических молекул была вычислена в 1930-е годы и подтверждена экспериментально.

Численный пример: лемма Бёрнсайда и разбиения

Задача 1: Разбиения n=6 — сколько их? Задача 2: Раскраска ожерелья из 4 бусин в 3 цвета с учётом вращений.

Шаг 1 (разбиения): Перечислим все разбиения 6: {6},{5+1},{4+2},{4+1+1},{3+3},{3+2+1},{3+1+1+1},{2+2+2},{2+2+1+1},{2+1+1+1+1},{1+1+1+1+1+1}. p(6)=11.

Шаг 2 (разбиения): Проверка рекуррентностью Эйлера: p(6)=p(5)+p(4)−p(1)=7+5−1=11. ✓

Шаг 3 (ожерелье): Группа вращений ожерелья из 4 бусин: G={e,r,r²,r³} (циклическая C₄). |G|=4. |X^e|=3⁴=81; |X^r|=3 (4 бусины одного цвета); |X^{r²}|=3²=9; |X^{r³}|=3.

Шаг 4: |X/G| = (1/4)(81+3+9+3) = 96/4 = 24 различных ожерелья. Без учёта симметрии их было бы 81; лемма Бёрнсайда сократила счёт в 3.4 раза.