Введение

В комбинаторной математике теория комбинаторных видов – это абстрактный, систематический метод вывода генерирующих функций для дискретных структур, который позволяет не только подсчитывать эти структуры, но и приводить биективные доказательства, связанные с ними. Примерами комбинаторных видов являются (конечные) графы, перестановки, деревья и так далее; каждый из них имеет соответствующую генерирующую функцию, которая подсчитывает количество структур заданного размера. Одна из целей теории видов – возможность анализировать сложные структуры, описывая их в терминах преобразований и комбинаций более простых структур. Эти операции соответствуют эквивалентным преобразованиям генерирующих функций, поэтому получение таких функций для сложных структур значительно проще, чем другими методами. Теория была разработана, тщательно детализирована и применена канадскими исследователями во главе с Андре Жуайялем. Мощность теории заключается в её уровне абстракции. "Формат описания" структуры (например, список смежности или матрица смежности для графов) несущественен, поскольку виды являются чисто алгебраическими. Теория категорий предоставляет удобный язык для возникающих здесь понятий, но для работы с видами не обязательно понимать теорию категорий. Категория видов эквивалентна категории симметричных последовательностей в конечных множествах.

Расчет видов

Арифметика генерирующих функций соответствует определенным "естественным" операциям над видами. Основными операциями являются сложение, умножение, композиция и дифференцирование; также необходимо определить равенство для видов. Теория категорий уже предоставляет способ описания того, когда два функтора эквивалентны: естественный изоморфизм. В данном контексте это означает, что для каждого множества A существует взаимно однозначное соответствие между F-структурами на A и G-структурами на A, которое "хорошо согласовано" при взаимодействии с переносом. Виды с одинаковой генерирующей функцией могут быть неизоморфными, но изоморфные виды всегда имеют одну и ту же генерирующую функцию.

Добавление

Добавление видов определяется дизъюнктным объединением множеств и соответствует выбору между структурами. Для видов F и G определим (F + G)[A] как дизъюнктное объединение (также обозначаемое "+") F[A] и G[A]. Следовательно, (F + G)(x) = F(x) + G(x). В качестве примера рассмотрим E+ как вид непустых множеств, функция-генератор которого E+(x) = ex − 1, и 1 как вид пустого множества, функция-генератор которого 1(x) = 1. Отсюда следует, что E = 1 + E+: другими словами, "множество либо пустое, либо непустое". Подобные уравнения можно интерпретировать как относящиеся как к отдельной структуре, так и ко всей совокупности структур.

Умножение

Умножение видов немного сложнее. Можно просто взять в качестве определения декартово произведение множеств, но комбинаторная интерпретация этого не совсем верна. (Подробнее об использовании этого вида произведения см. ниже.) Вместо того, чтобы объединять две несвязанные структуры на одном множестве, оператор умножения использует идею разбиения множества на два компонента, создавая структуру F на одном и структуру G на другом. Это дизъюнктное объединение по всем возможным бинарным разбиениям A. Легко показать, что умножение ассоциативно и коммутативно (с точностью до изоморфизма), и распределительно относительно сложения. Что касается образующих рядов, то (F · G)(x) = F(x)G(x). На диаграмме ниже показана одна из возможных структур (F · G) на множестве из пяти элементов. Структура F (красная) выбирает три элемента базового множества, а структура G (голубая) – остальные. Другие структуры будут иметь F и G, разбивающие множество по-другому. Множество (F · G)[A], где A – базовое множество, является дизъюнктным объединением всех таких структур. Сложение и умножение видов – наиболее полное выражение правил суммы и произведения при подсчете.

Состав

Композиция, также называемая заменой, снова более сложна. Основная идея состоит в том, чтобы заменить компоненты F структурами G, образуя (F ∘ G). Как и при умножении, это делается путем разбиения входного множества A; непересекающиеся подмножества передаются G для создания G-структур, а множество этих подмножеств передается F для создания F-структуры, связывающей G-структуры. Для корректной работы композиции необходимо, чтобы G отображало пустое множество на само себя. Формальное определение:

Здесь P – вид разбиений, поэтому P[A] – множество всех разбиений множества A. Это определение говорит, что элемент (F ∘ G)[A] состоит из F-структуры на некотором разбиении A и G-структуры на каждом компоненте этого разбиения. Одна из таких структур показана ниже. Три G-структуры (светло-синие) разделяют между собой базовое множество из пяти элементов; затем, F-структура (красная) строится для соединения G-структур. Эти две последние операции можно проиллюстрировать на примере деревьев. Во-первых, определим X как вид "одиночный элемент", чей генерирующий ряд X(x) = x. Затем вид Ar корневых деревьев (от французского "arborescence") определяется рекурсивно как Ar = X · E(Ar). Это уравнение говорит, что дерево состоит из одного корня и множества (под)деревьев. Рекурсия не нуждается в явном базовом случае: она генерирует деревья только в контексте применения к некоторому конечному множеству. Один из способов понять это – представить, что функтор Ar применяется неоднократно к "запасу" элементов из множества, каждый раз забирая один элемент для X, а остальные распределяя с помощью E между поддеревьями Ar, пока E не закончатся элементы для распределения. Это показывает, что алгебраические описания видов существенно отличаются от типовых спецификаций в языках программирования, таких как Haskell. Аналогично, вид P можно охарактеризовать как P = E(E+): "разбиение – это парами непересекающееся множество непустых множеств (использующее все элементы входного множества)". Экспоненциальный генерирующий ряд для P равен , который является рядом для чисел Белла.