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

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

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

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

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

Любой вид состоит из индивидуальных комбинаторных структур, построенных на элементах некоторого конечного множества: например, комбинаторный граф — это структура ребер среди заданного множества вершин, а вид графов включает все графы на всех конечных множествах. Более того, член вида может иметь свой базовый набор, перемаркированный элементами любого другого равновеликого множества, например, перемаркировка вершин графа дает «ту же самую структуру графа» на новых вершинах, т. е. изоморфный граф.

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

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

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

Например, «вид перестановок» ^[4] отображает каждое конечное множество A в множество S [ A ] всех перестановок A (всех способов упорядочения A в список), и каждая биекция f из A в другое множество B естественным образом индуцирует биекцию (перемаркировку), переводящую каждую перестановку A в соответствующую перестановку B , а именно биекцию . Аналогично, «вид разделов» можно определить, присвоив каждому конечному множеству множество всех его разделов , а «вид набора мощности» присвоит каждому конечному множеству его набор мощности . На соседней диаграмме показана структура (представленная красной точкой), построенная на множестве из пяти различных элементов (представленных синими точками); соответствующая структура может быть построена из любых пяти элементов. $S[f]:S[A]\to S[B]$

Два конечных множества находятся во взаимно однозначном соответствии, если они имеют одинаковую мощность (количество элементов); таким образом, по определению соответствующие видовые множества также находятся во взаимно однозначном соответствии, а (конечная) мощность зависит только от мощности A. ^{[примечание 2]} В частности, можно определить экспоненциальный порождающий ряд F ( x ) вида F : ^[5] $F[A]$

F(x)=\sum _{n\geq 0}\operatorname {Карта} F[n]{\frac {x^{n}}{n!}}

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

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

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

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

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

Добавление

Добавление видов определяется несвязным объединением множеств и соответствует выбору между структурами. ^[6] Для видов 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 ⁺ : словами, "множество либо пусто, либо непусто". Подобные уравнения можно читать как относящиеся к одной структуре, а также ко всему набору структур.

Умножение

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

(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 ). ^[8] Как и в случае с умножением, это делается путем разбиения входного множества A ; непересекающиеся подмножества передаются G для создания G -структур, а набор подмножеств передается F , для создания F -структуры, связывающей G -структуры. Для того, чтобы композиция работала, G требуется отобразить пустое множество на себя. Формальное определение таково:

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

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

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

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

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

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

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

Формально, ^[9]

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

где находится некоторый выдающийся новый элемент, отсутствующий в . $\звезда$ $А$

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

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

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

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

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

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

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

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

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

Указание выбирает один элемент в структуре. ^[10] При наличии вида 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. Например, если F — функтор, переводящий множество в его степенное множество, структура составленного вида — это некоторое подмножество G -структур на A. Если теперь взять G как E ^• × E ^• сверху, мы получим виды направленных графов с разрешенными петлями. (Направленный граф — это множество ребер, а ребра — это пары узлов: поэтому граф — это подмножество множества пар элементов множества узлов A. ) Другие семейства графов, а также многие другие структуры могут быть определены таким образом. $(F\,\Box \,G)[A]=F[G[A]]$

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

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

Варианты

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

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

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

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

Примечания

^ Джойал предпочитает писать для , значение F в точке A . $F[A]$ $F(A)$
^ Если — биекция, то — биекция и, следовательно, имеют одинаковую мощность. $u:A\to B$ $F[u]:F[A]\to F[B]$ $F[A],F[B]$

^ Симметричная последовательность в n Lab
^ Джоял 1981, § 1.1. Определение 1.
^ Федерико Г. Ластария, Приглашение к комбинаторным видам. (2002)
^ Джоял 1981, § 1.1. Пример 3.
^ Джоял 1981, § 1.1.1.
^ Джоял 1981, § 2.1.
^ Джойал 1981, § 2.1. Определение 5
^ Джойал 1981, § 2.2. Определение 7
^ Джойал 1981, § 2.3. Определение 8
^ Флажоле, Филипп ; Седжвик, Роберт (2009). Аналитическая комбинаторика .
^ Документация Sage по комбинаторным видам.
^ Виды пакетов Haskell.
^ Брент А., Йоргей (2010). «Виды, функторы и типы, о боже!». Труды третьего симпозиума ACM Haskell по Haskell - Haskell '10 . ACM. стр. 147–158. CiteSeerX 10.1.1.165.6421 . doi :10.1145/1863523.1863542. ISBN 978-1-4503-0252-4. S2CID 511418.

Ссылки

Джоял, Андре (октябрь 1981 г.). «Комбинированная теория серий форм». Достижения в математике . 42 (1): 1–82. дои : 10.1016/0001-8708(81)90052-9.
Bruijn, de, NG (1964). Теория счета Полиа. В EF Beckenbach (ред.), Прикладная комбинаторная математика (стр. 144-184)
Лабель, Жак. Некоторые особенные ансамбли миниатюрных кардиналов. , Энн. наук. Математика. Квебек 9.1 (1985): 31–58.
Labelle, J.; Yeh, YN (1989). «Связь между кольцами Бернсайда и комбинаторными видами». Журнал комбинаторной теории . Серия A. 50 (2): 269–284. doi : 10.1016/0097-3165(89)90019-8 .
Ив Чирикота, Классификация особенных молекул 6 и 7 степени , Ann. наук. Математика. Квебек 17 (1993), вып. 1, 11–37.
Франсуа Бержерон, Жильбер Лабелль, Пьер Леру, Теория особенных и комбинационных структур древесных пород , LaCIM, Монреаль (1994). Английская версия: Комбинаторные виды и древовидные структуры. Архивировано 2 октября 2006 г. в Wayback Machine , Cambridge University Press (1998).
Кербер, Адальберт (1999), Прикладные действия конечных групп, Алгоритмы и комбинаторика, 19 (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-65941-9 , MR 1716962, OCLC 247593131

Внешние ссылки

Вайсштейн, Эрик В. «Виды». MathWorld .
виды в n Lab