Комбинаторный класс
В математике комбинаторный класс — это счетный набор математических объектов вместе с функцией размера, отображающей каждый объект в неотрицательное целое число, так что существует конечное число объектов каждого размера. [1] [2]
Подсчет последовательностей и изоморфизм
[ редактировать ]Счетная последовательность комбинаторного класса — это последовательность чисел элементов размера i для i = 0, 1, 2, ...; ее также можно описать как производящую функцию , коэффициентами которой являются эти числа. Счетные последовательности комбинаторных классов — основной предмет изучения перечислительной комбинаторики . Два комбинаторных класса называются изоморфными, если они содержат одинаковое количество объектов каждого размера или, что то же самое, если их счетные последовательности одинаковы. [3] Часто, когда известно, что два комбинаторных класса изоморфны, биективное доказательство ищут этой эквивалентности; такое доказательство можно интерпретировать как показывающее, что объекты двух изоморфных классов криптоморфны друг другу.
Например, триангуляции правильных многоугольников (с размером, определяемым числом сторон многоугольника, и фиксированным выбором многоугольника для триангуляции для каждого размера) и набор некорневых бинарных плоских деревьев (с точностью до изоморфизма графа , с фиксированным порядок листьев и размер, определяемый количеством листьев) считаются каталонскими числами , поэтому они образуют изоморфные комбинаторные классы. Биективный изоморфизм в этом случае задается двойственностью планарного графа : триангуляция может быть биективно преобразована в дерево с листом для каждого ребра многоугольника, внутренним узлом для каждого треугольника и ребром для каждых двух (ребер многоугольника?) или треугольников. которые примыкают друг к другу. [4]
Аналитическая комбинаторика
[ редактировать ]Теория комбинаторных видов и ее расширение до аналитической комбинаторики предоставляют язык для описания многих важных комбинаторных классов, построения новых классов из комбинаций ранее определенных и автоматического получения их счетных последовательностей. [3] Например, два комбинаторных класса могут быть объединены с помощью непересекающегося объединения или конструкции декартова произведения , в которой объекты представляют собой упорядоченные пары одного объекта из каждого из двух классов, а функция размера представляет собой сумму размеров каждого объекта в пара. Эти операции соответственно образуют операции сложения и умножения полукольца на семействе комбинаторных классов (классов эквивалентности изоморфизма), в которых нулевым объектом является пустой комбинаторный класс, а единицей — класс, единственным объектом которого является пустое множество . [5]
Шаблоны перестановок
[ редактировать ]При изучении шаблонов перестановок комбинаторный класс классов перестановок , нумерованный по длине перестановки, называется классом Уилфа . [6] Изучение перечислений конкретных классов перестановок выявило неожиданную эквивалентность при подсчете последовательностей, казалось бы, несвязанных между собой классов перестановок.
Ссылки
[ редактировать ]- ^ Мартинес, Конрадо; Молинеро, Ксавьер (2001), «Общий подход к отмене ранжирования помеченных комбинаторных классов» (PDF) , Случайные структуры и алгоритмы , 19 (3–4): 472–497, doi : 10.1002/rsa.10025 , MR 1871563 .
- ^ Дюшон, Филипп ; Флажоле, Филипп; Лушар, Гай; Шеффер, Жиль (2004), «Семплеры Больцмана для случайной генерации комбинаторных структур», Combinatorics, Probability and Computing , 13 (4–5): 577–625, doi : 10.1017/S0963548304006315 , MR 2095975 .
- ^ Jump up to: Перейти обратно: а б Флажоле, Филипп ; Седжвик, Роберт (2009), Аналитическая комбинаторика , Издательство Кембриджского университета, Определение I.3, стр.19, ISBN 9781139477161 .
- ^ Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010), Триангуляции: структуры для алгоритмов и приложений , Алгоритмы и вычисления в математике, том. 25, Спрингер, Теорема 1.1.3, стр. 4–6, ISBN. 9783642129711 .
- ^ Бард, Грегори В. (2009), Алгебраический криптоанализ , Спрингер, раздел 4.2.1, «Комбинаторные классы», и далее, стр. 30–34, ISBN 9780387887579 .
- ^ Стейнгримссон, Эйнар (2013), «Некоторые открытые проблемы шаблонов перестановок», Обзоры по комбинаторике, 2013 г. , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 409, Кембриджский университет. Пресс, Кембридж, стр. 239–263, MR 3156932.