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

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

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

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

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

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

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

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

${\displaystyle F\colon {\mathcal {B}}\to {\mathcal {B}}.}$

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

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

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

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

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

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

• Виды наборов (традиционно называемые E, от французского "ансамбль", что означает" набор ") - это функтор, отображающий А to {А}. потом ${\displaystyle f_{n}=1}$, так ${\displaystyle E(x)=e^{x}}$.
• Виды S из перестановки, описанный выше, имеет ${\displaystyle f_{n}=n!}$. ${\displaystyle S(x)=1/(1-x)}$.
• Виды Т₂ пар (2-кортежи ) - функтор, принимающий множество А к А². потом ${\displaystyle f_{n}=n^{2}}$ и ${\displaystyle T_{2}(x)=x(x+1)e^{x}}$.

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

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

Дополнение

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

Первоначальное определение вида вдохновило исследователей на три направления.^{[нужна цитата ]}

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

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

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

Умножение

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

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

Это несвязное объединение по всем возможным двоичным разбиениямА. Несложно показать, что умножение ассоциативный и коммутативный (вплоть до изоморфизм ), и распределительный сверх сложения. Что касается производящего ряда, (F · г)(Икс) = F(Икс)г(Икс).

На диаграмме ниже показан один из возможных (F · г) -конструкция на наборе из пяти элементов. В F-структура (красный) подбирает три элемента базового набора, а г-структура (голубой) берет на себя остальное. Другие конструкции будут иметь F и г разделение набора другим способом. Набор (F · г)[А], где А - базовое множество, - несвязное объединение всех таких структур.

Сложение и умножение видов - наиболее полное выражение правил подсчета суммы и произведения.

Сочинение

Сочинение, также называемая подстановкой, снова более сложна. Основная идея - заменить компоненты F с участием г-конструкции, формирующие (F∘г).^[8] Как и в случае с умножением, это делается путем разделения входного набора А; непересекающиеся подмножества задаются г делать г-структур, а множество подмножеств F, чтобы сделать F-структура, связывающая г-конструкции. Это необходимо для г чтобы сопоставить пустой набор самому себе, чтобы композиция работала. Формальное определение:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операции с видами поддерживаются SageMath^[10] и, используя специальный пакет, также Haskell.^[11][12]

Варианты

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

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

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

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

Заметки

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

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

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

• Андре Жоял, Une théorie combinatoire des séries formelles, Успехи в математике 42: 1–82 (1981).
• Лабель, Жак. Quelques espèces sur les ensembles de petite cardinalité., Анна. Sc. Математика. Квебек, 9.1 (1985): 31-58.
• Дж. Лабелль, Ю.Н. Ага, Связь между кольцами Бернсайда и комбинаторными видами, Journal of Combinatorial Theory Series A 50, (1989) 269–284.
• Ив Чирикота, Классификация espèces moléculaires de degré 6 и 7, Анна. Sci. Математика. Квебек 17 (1993), нет. 1, 1 л – 37.
• Франсуа Бержерон, Жильбер Лабель, Пьер Леру, Теория опыта и объединение арбороресценции, LaCIM, Монреаль (1994). Английская версия: Комбинаторные виды и древовидные структуры, Издательство Кембриджского университета (1998).
• Кербер, Адальберт (1999), Прикладные действия конечных групп, Алгоритмы и комбинаторика, 19 (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-65941-9, Руководство по ремонту 1716962, OCLC 247593131

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

• Вайсштейн, Эрик В. "Виды". MathWorld.
• https://ncatlab.org/nlab/show/species