Комбинаторные виды - Combinatorial species

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

Сила теории проистекает из ее уровня абстракции. «Описание формат» структуры (например, смежность списка по сравнению с матрицей смежности для графов) не имеет никакого значения, потому что вид чисто алгебраические. Теория категорий предоставляет полезный язык для концепций, которые здесь возникают, но не обязательно понимать категории, прежде чем иметь возможность работать с видами.

Категория видов эквивалентна категории симметричных последовательностей в конечных множествах.

Определение вида

Схематическое изображение комбинаторной структуры видов на пяти элементах с использованием диаграммы Лабелля

Любая структура - экземпляр определенного вида - связана с некоторым набором , и часто существует много возможных структур для одного и того же набора. Например, можно построить несколько разных графов, метки узлов которых взяты из одного и того же заданного набора. При этом для постройки конструкций можно было использовать любой набор. Разница между одним видом и другим состоит в том, что они строят разный набор структур из одного и того же базового набора.

Это приводит к формальному определению комбинаторного вида . Пусть будет категория из конечных множеств , с морфизмами из категории , являющейся биекции между этими множествами. Видов является функтор ${\ displaystyle {\ mathcal {B}}}$

{\ displaystyle F \ двоеточие {\ mathcal {B}} \ to {\ mathcal {B}}.}

Для каждого конечного множества А в , конечное множество Р [ ] называется множество F -структуры на А , или множество структур вида F на A . Далее, по определению функтора, если φ является биекцией между множествами A и B , то F [φ] является биекцией между множествами F -структур F [ A ] и F [ B ], называемой переносом F- конструкции вдоль φ . ${\ displaystyle {\ mathcal {B}}}$

Например, «вид перестановок» отображает каждое конечное множество A на множество всех перестановок A , и каждая биекция из A в другое множество B естественным образом индуцирует взаимно однозначное соответствие от множества всех перестановок A к множеству всех перестановок из B . Точно так же «виды разделов» могут быть определены путем присвоения каждому конечному набору набора всех его разделов , а «виды набора мощности» назначают каждому конечному набору его набор мощности . На соседней диаграмме показана конструкция из пяти элементов: дуги соединяют структуру (красный цвет) с элементами (синий цвет), из которых он построен.

Поскольку существует взаимно однозначное соответствие между двумя конечными множествами тогда и только тогда , когда оба множества имеют одинаковую мощность (количество элементов) для каждого конечного множества А , мощность , которая конечна, зависит только от мощности A . (Это следует из формального определения функтора.) В частности, можно определить экспоненциальный производящий ряд F ( x ) вида F : ${\ displaystyle F [A]}$

{\ displaystyle F (x) = \ sum _ {n \ geq 0} \ operatorname {Card} F [n] {\ frac {x ^ {n}} {n!}}}

где - мощность для любого множества A, имеющего n элементов; например, . ${\ displaystyle \ operatorname {Card} F [n]}$ ${\ displaystyle F [A]}$ ${\ Displaystyle А = \ {1,2, \ точки, п \}}$

Некоторые примеры: письмо , ${\ displaystyle f_ {n} = \ operatorname {Card} F [n]}$

Вид множеств (традиционно называемый E от французского « ансамбль », что означает «множество») - это функтор, который отображает A в { A }. Тогда так . ${\ displaystyle f_ {n} = 1}$ ${\ Displaystyle Е (х) = е ^ {х}}$
Вид S из перестановок , описанных выше, есть . . ${\ displaystyle f_ {n} = n!}$ ${\ Displaystyle S (х) = 1 / (1-х)}$
Вид T ₂ пар (2- кортежей ) - это функтор, переводящий множество A в A ² . Потом и . ${\ displaystyle f_ {n} = n ^ {2}}$ ${\ Displaystyle T_ {2} (х) = х (х + 1) е ^ {х}}$

Исчисление видов

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

Добавление

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

Первоначальное определение вида вдохновило исследователей на три направления.

- С категориальной стороны, требуется более крупный фрейм для содержания как продукта, так и сопутствующего продукта . Цена - это потеря индекса цикла.

- Другой подход - это кольца или оснастки Burnside . Суммирование представлений Бернсайда - это формальная нотация, используемая при разработке теории таблиц оценок.

- Наконец, обычное определение не принимает во внимание функториальность и тот факт, что вид, даже если рассматривать его как правило, уникален. Для правила F не существует второго правила F для получения непересекающейся суммы F + F. В этом подходе определение суммирования фактически является определением на примере. Преимущество - естественная вставка указателя цикла в качестве электроинструмента.

Умножение

Размножение видов несколько сложнее. Можно просто взять декартово произведение множеств в качестве определения, но комбинаторная интерпретация этого не совсем верна. (См. Ниже об использовании этого вида продукта.) Вместо того, чтобы складывать две несвязанные структуры в один и тот же набор, оператор умножения использует идею разделения набора на два компонента, конструируя F -структуру на одном и G - структура с другой.

{\ Displaystyle (F \ cdot G) [A] = \ sum _ {A = B + C} F [B] \ times G [C].}

Это объединение непересекающихся по всем возможным двоичным разделов 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 требуется сопоставить пустой набор с самим собой. Формальное определение:

{\ Displaystyle (F \ circ G) [A] = \ sum _ {\ pi \ in P [A]} (F [\ pi] \ times \ prod _ {B \ in \ pi} G [B]). }

Здесь Р является видом перегородок, поэтому P [ ] есть множество всех разбиений A . Это определение говорит, что элемент ( F ∘ G ) [ A ] состоит из F -структуры на некотором разбиении A и G-структуры на каждой компоненте разбиения. Производящий ряд равен . ${\ Displaystyle (F \ circ G) (х) = F (G (x))}$

Одна такая структура показана ниже. Три G-структуры (голубые) разделяют пятиэлементный базовый набор между собой; затем строится F-структура (красная) для соединения G-структур .

Эти две последние операции можно проиллюстрировать на примере деревьев. Во-первых, определите X как разновидность "одиночка", производящий ряд которой равен X ( x ) = x . Тогда вид корневых деревьев Ar (от французского « древовидность ») определяется рекурсивно как Ar = X · E ( Ar ). Это уравнение говорит, что дерево состоит из одного корня и набора (под) деревьев. Рекурсия не требует явного базового случая: она генерирует деревья только в контексте применения к некоторому конечному набору. Один из способов подумать об этом состоит в том, что функтор Ar многократно применяется к "поставке" элементов из набора - каждый раз один элемент берется X , а другие распределяются E между поддеревьями Ar , пока не будет больше не нужно отдавать E элементы . Это показывает, что алгебраические описания видов сильно отличаются от спецификаций типов в таких языках программирования, как Haskell .

Аналогично, разновидность P может быть охарактеризована как P = E ( E ⁺ ): «раздел - это попарно непересекающееся множество непустых множеств (использующее все элементы входного множества)». Экспоненциальный производящий ряд для P равен , который является рядом чисел Белла . ${\ Displaystyle Р (х) = е ^ {(е ^ {х} -1)}}$

Дифференциация

Дифференциация видов интуитивно соответствует построению «построек с дырой», как показано на иллюстрации ниже.

Формально,

{\ Displaystyle (F ') [A] = F [A \ uplus \ {\ star \}],}

где какой-то выдающийся новый элемент, отсутствующий в . ${\ displaystyle \ star}$ ${\ displaystyle A}$

Чтобы дифференцировать связанный экспоненциальный ряд, последовательность коэффициентов должна быть сдвинута на одну позицию влево (потеря первого члена). Это предлагает определение вида: F ' [ A ] = F [ A + {*}], где {*} - одноэлементный набор, а «+» - дизъюнктное объединение. Более продвинутые части теории видов широко используют дифференциацию для построения и решения дифференциальных уравнений для видов и рядов. Идея добавления (или удаления) отдельной части структуры является мощной: ее можно использовать для установления отношений между, казалось бы, несвязанными видами.

Например, рассмотрим структуру вида L линейных порядков - списки элементов основного набора. Удаление элемента из списка разбивает его на две части (возможно, пустые); в символах, это L» = L · L . Экспоненциальная производящая функция L равна L ( x ) = 1 / (1 - x ), и действительно:

{\ displaystyle {\ frac {d} {dx}} {(1-x)} ^ {- 1} = {(1-x)} ^ {- 2}.}

Обобщенные формулы дифференцирования можно найти в предыдущем исследовании Н.Г. де Брюйна, опубликованном в 1964 году.

Вид С циклических перестановок принимает множество А на множество всех циклов на A . Удаление одного элемента из цикла уменьшает его в список: С» = л . Мы можем интегрировать производящую функцию L , чтобы произвести , что для C .

{\ displaystyle C (x) = \ int _ {0} ^ {x} {\ frac {dt} {1-t}} = \ log {\ frac {1} {1-x}}.}

Хорошим примером интеграции видов является завершение линии (согласованной полем) с бесконечной точкой и получение проективной линии.

Дальнейшие операции

Есть множество других манипуляций, которые можно проводить с видами. Они необходимы для выражения более сложных структур, таких как ориентированные графы или биграфы .

При наведении выделяется один элемент конструкции. Для вида F соответствующий точечный вид F ^• определяется как F ^• [ A ] = A × F [ A ]. Таким образом, каждая F ^• -структура является F-структурой с одним выделенным элементом. Указание связано с дифференцированием соотношением F ^• = X · F ' , поэтому F ^• ( x ) = x F' ( x ). Вид остроконечных множеств , E ^• , особенно важен как строительный блок для многих более сложных конструкций.

Декартово произведение двух видов является одним из видов , которые могут создавать две структуры на том же наборе в то же самое время. Он отличается от обычного оператора умножения тем, что все элементы базового набора разделяются между двумя структурами. ( F × G ) -структура может рассматриваться как суперпозиция F-структуры и G-структуры . Биграфы можно описать как суперпозицию графа и набора деревьев: каждый узел биграфа является частью графа и в то же время частью некоторого дерева, которое описывает, как узлы вложены. Производящая функция ( F × G ) ( x ) является произведением Адамара или коэффициентов F ( x ) и G ( x ).

Вид E ^• × E ^• можно рассматривать как делающий два независимых выбора из базового набора. Две точки могут совпадать, в отличие от X · X · E , где они вынуждены быть разными.

В качестве функторов виды F и G могут быть объединены функториальной композицией : (используется квадратный символ, потому что круг уже используется для подстановки). Это строит F -структуре на множестве всех G -структурами на множестве A . Например, если Р является функтор принимает набор для его набора мощности, структура из составленных видов является некоторое подмножество G -структуры на A . Если мы теперь возьмем G равным E ^• × E ^• сверху, мы получим вид ориентированных графов с разрешенными петлями. (Ориентированный граф - это набор ребер, а ребра - это пары узлов: таким образом, граф - это подмножество набора пар элементов набора узлов A. ) Другие семейства графов, а также многие другие структуры могут быть определенным таким образом. ${\ Displaystyle (F \, \ Box \, G) [A] = F [G [A]]}$

Программное обеспечение

Операции с видами поддерживаются SageMath и, с помощью специального пакета, также Haskell .

Варианты

Вид из k сортов является функтором . Здесь созданные конструкции могут иметь элементы, взятые из разных источников. ${\ Displaystyle {\ mathcal {B}} ^ {k} \ rightarrow {\ mathcal {B}}}$
Функтор к , категории R -weighted наборов для R в кольце степенных рядов, представляет собой взвешенные разновидности . ${\ displaystyle {\ mathcal {B}} _ {R}}$

Если заменить «конечные множества с биекциями» на «конечные векторные пространства с линейными преобразованиями», то получится понятие полиномиального функтора (после наложения некоторого условия конечности).

Смотрите также

Контейнер (теория типов)

Примечания

использованная литература

Андре Жоял, Теория комбинаторики серии форм , Успехи в математике 42: 1–82 (1981).
Bruijn, de, NG (1964). Теория счета Поли. В EF Beckenbach (Ed.), Applied Combinatorical

математика (стр. 144-184)

Лабель, Жак. Quelques espèces sur les ensembles de petite cardinalité. , Анна. Sc. Математика. Квебек, 9.1 (1985): 31-58.
J. Labelle и YN Yeh, Связь между кольцами Бернсайда и комбинаторными видами , Журнал комбинаторной теории, серия A 50, (1989) 269–284
Yves Chiricota, Classification des espèces moléculaires de degré 6 et 7 , Ann. Sci. Математика. Квебек 17 (1993), нет. 1, 1 л – 37.
François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structure arborescentes , LaCIM, Montréal (1994). Английская версия: Комбинаторные виды и древовидные структуры , Cambridge University Press (1998).
Кербер, Адальберт (1999), Прикладные действия конечных групп, алгоритмы и комбинаторика, 19 (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-65941-9 , MR 1716962, OCLC 247593131

Languages

In other projects