Введение

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

В комбинаторике символический метод — это техника для подсчёта комбинаторных объектов. Он использует внутреннюю структуру объектов для вывода формул для их порождающих функций. Метод тесно связан с Филиппом Флажоле и подробно описан в части А его книги, написанной в соавторстве с Робертом Седжвиком, «Аналитическая комбинаторика», в то время как остальная часть книги объясняет, как использовать комплексный анализ для получения асимптотических и вероятностных результатов для соответствующих порождающих функций. На протяжении двух столетий порождающие функции возникали через соответствующие рекуррентные соотношения на их коэффициентах (что можно увидеть в основополагающих работах Бернулли, Эйлера, Артура Кейли, Шрёдера, Рамануджана, Риордана, Кнута, Комте и др.). Затем постепенно стало ясно, что порождающие функции отражают многие другие аспекты исходных дискретных комбинаторных объектов, и что это можно сделать более прямым и формальным способом: рекурсивная природа некоторых комбинаторных структур преобразуется, посредством определённых изоморфизмов, в замечательные тождества для соответствующих порождающих функций. Продолжая работы По́ли, дальнейшие успехи в этом направлении были достигнуты в 1970-х годах с использованием языков для спецификации комбинаторных классов и их порождающих функций, как это представлено в работах Фоата и Шютценбергера по перестановкам, Бендера и Голдмана по префабам и Джояля по комбинаторным видам. Следует отметить, что этот символический метод в перечислении не связан с «символическим методом Блиссара», который является просто другим старым названием для умбрального исчисления. Символический метод в комбинаторике представляет собой первый шаг во многих анализах комбинаторных структур, который затем может привести к быстрым вычислительным схемам, асимптотическим свойствам и предельным законам, случайной генерации, все из которых подходят для автоматизации с помощью компьютерной алгебры.

Процедура

Обычно начинают с нейтрального класса, содержащего один объект размера 0 (нейтральный объект, часто обозначаемый ), и одного или нескольких атомных классов, каждый из которых содержит один объект размера 1. Далее, отношения теории множеств, включающие различные простые операции, такие как непересекающиеся объединения, произведения, множества, последовательности и мультимножества, определяют более сложные классы в терминах уже определенных классов. Эти отношения могут быть рекурсивными. Элегантность символической комбинаторики заключается в том, что отношения теории множеств, или символические отношения, напрямую переводятся в алгебраические отношения, включающие генерирующие функции. В этой статье мы будем придерживаться условности использования прописных букв, написанных курсивом, для обозначения комбинаторных классов и соответствующих обычных букв для генерирующих функций (так что класс имеет генерирующую функцию ). Существует два типа генерирующих функций, обычно используемых в символической комбинаторике: обычные генерирующие функции, используемые для комбинаторных классов немаркированных объектов, и экспоненциальные генерирующие функции, используемые для классов маркированных объектов. Легко показать, что генерирующие функции (обычные или экспоненциальные) для и являются и , соответственно. Непересекающееся объединение также просто — для непересекающихся множеств и , влечет за собой . Отношения, соответствующие другим операциям, зависят от того, рассматриваем ли мы маркированные или немаркированные структуры (и обычные или экспоненциальные генерирующие функции).

Комбинаторная сумма

Ограничение объединений на непересекающиеся объединения является важным; однако, в формальной спецификации символической комбинаторики слишком трудоемко отслеживать, какие множества не пересекаются. Вместо этого мы используем конструкцию, которая гарантирует отсутствие пересечения (осторожно, однако, это также влияет на семантику операции). При определении комбинаторной суммы двух множеств A и B, мы помечаем элементы каждого множества различным маркером, например, a для элементов A и b для элементов B. Комбинаторная сумма тогда:

Это операция, которая формально соответствует сложению.

Немаркированные конструкции

При немаркированных структурах используется обычная порождающая функция (ОПФ). ОПФ последовательности определяется как

Спецификация и определяемые классы

Элементарные конструкции, упомянутые выше, позволяют нам определить понятие спецификации. Эта спецификация позволяет использовать набор рекурсивных уравнений, включающих несколько комбинаторных классов. Формально, спецификация для набора комбинаторных классов – это набор уравнений , где – выражение, атомами которого являются и , а операторами – элементарные конструкции, перечисленные выше. Комбинаторный класс считается конструктивным или специфицируемым, если для него существует спецификация. Например, множество деревьев, у которых глубина листьев четная (соответственно, нечетная), можно определить с помощью спецификации, содержащей два класса и . Эти классы должны удовлетворять уравнениям и .

Обозначенные конструкции

Объект слабо маркирован, если каждый из его атомов имеет неотрицательную целочисленную метку, и все эти метки различны. Объект (сильно или корректно) маркирован, если, кроме того, эти метки состоят из последовательных целых чисел. Примечание: некоторые комбинаторные классы лучше всего задаются как маркированные или немаркированные структуры, но некоторые допускают оба способа задания. Хорошим примером маркированных структур является класс маркированных графов. Для маркированных структур используется экспоненциальная генерирующая функция (EGF). EGF последовательности определяется как

Настройка

В помеченных структурах множеству элементов соответствует ровно одна последовательность. Это отличается от непомеченного случая, где некоторые перестановки могут совпадать. Таким образом, для n у нас есть…

Цикл

Циклы также проще, чем в случае без меток. Цикл длины *k* соответствует *k* различным последовательностям. Таким образом, для *k* > 1, у нас есть…

Пример

Увеличивающееся дерево Кейли — это помеченное не плоское и укорененное дерево, для которого метки вдоль любой ветви, исходящей из корня, образуют возрастающую последовательность. Пусть 𝒞 — класс таких деревьев. Рекурсивное определение следующее: