Комбинаторные классы и перечислительная комбинаторика
Combinatorial class
Комбинаторные классы в математике: определения, счетные последовательности, изоморфизм и перечислительная комбинаторика. Изучение и анализ объектов и их свойств.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математике комбинаторный класс — это счетное множество математических объектов, вместе с функцией размера, которая сопоставляет каждому объекту неотрицательное целое число, при этом для каждого размера существует конечное число объектов.
In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non negative integer, such that there are finitely many objects of each size.
Подсчет последовательностей и изоморфизм
Последовательность подсчёта комбинаторного класса — это последовательность чисел элементов размера i для i = 0, 1, 2, …; её также можно описать как порождающую функцию, коэффициентами которой являются эти числа. Последовательности подсчёта комбинаторных классов являются основным предметом изучения энумеративной комбинаторики. Два комбинаторных класса называются изоморфными, если они содержат одинаковое количество объектов каждого размера, или, что эквивалентно, если их последовательности подсчёта совпадают. Часто, когда два комбинаторных класса оказываются изоморфными, ищут биективное доказательство этой эквивалентности; такое доказательство можно интерпретировать как демонстрацию того, что объекты в двух изоморфных классах криптоморфны друг другу. Например, триангуляции правильных многоугольников (с размером, определяемым числом сторон многоугольника, и фиксированным выбором многоугольника для триангуляции для каждого размера) и множество некорневых двоичных плоских деревьев (с точностью до изоморфизма графов, с фиксированным упорядочением листьев и с размером, определяемым числом листьев) оба пересчитываются числами Каталана, поэтому они образуют изоморфные комбинаторные классы. Биективный изоморфизм в этом случае задаётся двойственностью планарных графов: триангуляцию можно биективно преобразовать в дерево с листом для каждого ребра многоугольника, внутренним узлом для каждого треугольника и ребром для каждой пары (рёбер многоугольника?) или треугольников, имеющих общую сторону.
The counting sequence of a combinatorial class is the sequence of the numbers of elements of size i for i = 0, 1, 2, ; it may also be described as a generating function that has these numbers as its coefficients. The counting sequences of combinatorial classes are the main subject of study of enumerative combinatorics. Two combinatorial classes are said to be isomorphic if they have the same numbers of objects of each size, or equivalently, if their counting sequences are the same. Frequently, once two combinatorial classes are known to be isomorphic, a bijective proof of this equivalence is sought; such a proof may be interpreted as showing that the objects in the two isomorphic classes are cryptomorphic to each other. For instance, the triangulations of regular polygons (with size given by the number of sides of the polygon, and a fixed choice of polygon to triangulate for each size) and the set of unrooted binary plane trees (up to graph isomorphism, with a fixed ordering of the leaves, and with size given by the number of leaves) are both counted by the Catalan numbers, so they form isomorphic combinatorial classes. A bijective isomorphism in this case is given by planar graph duality: a triangulation can be transformed bijectively into a tree with a leaf for each polygon edge, an internal node for each triangle, and an edge for each two (polygon edges?) or triangles that are adjacent to each other.
Аналитическая комбинаторика
Теория комбинаторных видов и её расширение в аналитическую комбинаторику предоставляют язык для описания многих важных комбинаторных классов, конструирования новых классов на основе комбинаций ранее определенных и автоматического получения их счетных последовательностей.
The theory of combinatorial species and its extension to analytic combinatorics provide a language for describing many important combinatorial classes, constructing new classes from combinations of previously defined ones, and automatically deriving their counting sequences.
Схемы пермутации
В изучении шаблонов перестановок, комбинаторный класс классов перестановок, перечисляемый по длине перестановки, называется классом Уилфа. Исследование перечислений конкретных классов перестановок обнаружило неожиданные эквивалентности в последовательностях подсчёта, казалось бы, не связанных классов перестановок.
In the study of permutation patterns, a combinatorial class of permutation classes, enumerated by permutation length, is called a Wilf class. The study of enumerations of specific permutation classes has turned up unexpected equivalences in counting sequences of seemingly unrelated permutation classes.