Комбинаторный класс - Combinatorial class - Wikipedia

В математика, а комбинаторный класс это счетный набор математических объектов вместе с функцией размера, отображающей каждый объект в неотрицательное целое число, так что существует конечное число объектов каждого размера.[1][2]

Подсчет последовательностей и изоморфизм

В последовательность подсчета комбинаторного класса - это последовательность чисел элементов размера я за я = 0, 1, 2, ...; его также можно описать как производящая функция с этими числами в качестве коэффициентов. Счетные последовательности комбинаторных классов являются основным предметом изучения перечислительная комбинаторика. Два комбинаторных класса называются изоморфными, если они имеют одинаковое количество объектов каждого размера или, что эквивалентно, если их счетные последовательности одинаковы.[3] Часто, если известно, что два комбинаторных класса изоморфны, биективное доказательство этой эквивалентности ищется; такое доказательство можно интерпретировать как показывающее, что объекты в двух изоморфных классах являются криптоморфный друг другу.

Например, триангуляции из правильные многоугольники (с размером, заданным числом сторон многоугольника, и фиксированным выбором многоугольника для триангуляции для каждого размера) и набор нерутированный двоичный файл платаны (вплоть до изоморфизм графов, с фиксированным порядком расположения листьев и размером, определяемым количеством листьев), оба учитываются Каталонские числа, поэтому они образуют изоморфные комбинаторные классы. Биективный изоморфизм в этом случае задается формулой двойственность плоского графа: триангуляцию можно биективно преобразовать в дерево с листом для каждого ребра многоугольника, внутренним узлом для каждого треугольника и ребром для каждых двух ребер многоугольника или треугольников, которые примыкают друг к другу.[4]

Аналитическая комбинаторика

Теория комбинаторные виды и его расширение на аналитическая комбинаторика предоставляют язык для описания многих важных комбинаторных классов, построения новых классов из комбинаций ранее определенных и автоматического получения их счетных последовательностей.[3] Например, два комбинаторных класса могут быть объединены несвязный союз, или Декартово произведение конструкция, в которой объекты представляют собой упорядоченные пары одного объекта из каждого из двух классов, а функция размера представляет собой сумму размеров каждого объекта в паре. Эти операции, соответственно, образуют операции сложения и умножения полукольцо на семействе комбинаторных классов (классов эквивалентности изоморфизма), в котором нулевым объектом является пустой комбинаторный класс, а единицей является класс, единственным объектом которого является пустой набор.[5]

Шаблоны перестановок

При изучении шаблоны перестановок, комбинаторный класс классы перестановок, пронумерованный длиной перестановки, называется Уилф класс.[6] Изучение перечисления конкретных классов перестановок обнаружил неожиданные эквивалентности в подсчете последовательностей, казалось бы, несвязанных классов перестановок.

Рекомендации

  1. ^ Мартинес, Конрадо; Молинеро, Ксавьер (2001), «Общий подход к разряду помеченных комбинаторных классов» (PDF), Случайные структуры и алгоритмы, 19 (3–4): 472–497, Дои:10.1002 / RSA.10025, МИСТЕР  1871563.
  2. ^ Дюшон, Филипп; Флажолет, Филипп; Лоушар, Гай; Schaeffer, Gilles (2004), «Больцмановские сэмплеры для случайной генерации комбинаторных структур», Комбинаторика, теория вероятностей и вычисления, 13 (4–5): 577–625, Дои:10.1017 / S0963548304006315, МИСТЕР  2095975.
  3. ^ а б Флажоле, Филипп; Седжвик, Роберт (2009), Аналитическая комбинаторика, Cambridge University Press, Определение I.3, стр.19, ISBN  9781139477161.
  4. ^ Де Лоэра, Хесус А.; Рамбау, Йорг; Сантос, Франциско (2010), Триангуляции: структуры для алгоритмов и приложений, Алгоритмы и вычисления в математике, 25, Springer, теорема 1.1.3, стр. 4–6, ISBN  9783642129711.
  5. ^ Бард, Грегори В. (2009), Алгебраический криптоанализ, Springer, раздел 4.2.1, «Комбинаторные классы», и далее, стр. 30–34, ISBN  9780387887579.
  6. ^ Steingrímsson, Einar (2013), "Некоторые открытые проблемы о шаблонах перестановок", Обзоры по комбинаторике 2013, Лондонская математика. Soc. Lecture Note Ser., 409, Cambridge Univ. Press, Cambridge, pp. 239–263, МИСТЕР  3156932