Класс перестановки

При изучении перестановок и шаблонов перестановок класс перестановок — это набор перестановок, для которых каждый шаблон внутри перестановки в также находится в . Другими словами, класс перестановок — это наследственное свойство перестановок или понижение в порядке шаблона перестановки. ^[1] Класс перестановок может также называться классом шаблонов , закрытым классом или просто классом перестановок. $С$ $С$ $С$

Каждый класс перестановок может быть определен минимальными перестановками, которые не лежат внутри него, его базисом . ^[2] Главный класс перестановок — это класс, базис которого состоит только из одной перестановки. Так, например, сортируемые стеком перестановки образуют главный класс перестановок, определяемый запрещенным шаблоном 231. Однако некоторые другие классы перестановок имеют базисы с более чем одним шаблоном или даже с бесконечным множеством шаблонов.

Класс перестановок, который не включает все перестановки, называется правильным. В конце 1980-х годов Ричард Стэнли и Герберт Вильф предположили, что для каждого правильного класса перестановок существует некоторая константа , такая что число перестановок длины в классе ограничено сверху . Это было известно как гипотеза Стэнли–Вилфа , пока ее не доказали Адам Маркус и Габор Тардос . ^[3] Однако, хотя предел $С$ $К$ $|C_{n}|$ $n$ $К^{н}$

\lim _{n\to \infty }|C_{n}|^{1/n}

(жесткая граница на основе экспоненциального темпа роста) существует для всех основных классов перестановок, остается открытым вопрос, существует ли она для всех других классов перестановок. ^[4]

Два класса перестановок называются эквивалентными Вилфу , если для каждого оба имеют одинаковое количество перестановок длины . Эквивалентность Вилфа является отношением эквивалентности , а его классы эквивалентности называются классами Вилфа. Они являются комбинаторными классами классов перестановок. Известны функции подсчета и эквивалентности Вилфа среди многих конкретных классов перестановок . $n$ $n$

Ссылки

^ Китаев, Сергей (2011), Закономерности в перестановках и словах, Монографии по теоретической информатике, Гейдельберг: Springer, стр. 59, doi :10.1007/978-3-642-17333-2, ISBN 978-3-642-17332-5, МР 3012380
^ Китаев (2011), Определение 8.1.3, стр. 318.
^ Маркус, Адам; Тардос, Габор (2004), «Исключенные матрицы перестановок и гипотеза Стэнли-Вильфа», Журнал комбинаторной теории , Серия A, 107 (1): 153–160 , doi : 10.1016/j.jcta.2004.04.002 , MR 2063960.
^ Альберт, Майкл (2010), «Введение в структурные методы в шаблонах перестановок», Шаблоны перестановок , London Math. Soc. Lecture Note Ser., т. 376, Cambridge Univ. Press, Кембридж, стр. 153–170 , doi :10.1017/CBO9780511902499.008, ISBN 978-0-521-72834-8, г-н 2732828

[k-1] Китаев, Сергей (2011), Закономерности в перестановках и словах, Монографии по теоретической информатике, Гейдельберг: Springer, стр. 59, doi :10.1007/978-3-642-17333-2, ISBN 978-3-642-17332-5, МР 3012380

[2] Китаев (2011), Определение 8.1.3, стр. 318.

[mt-3] Маркус, Адам; Тардос, Габор (2004), «Исключенные матрицы перестановок и гипотеза Стэнли-Вильфа», Журнал комбинаторной теории , Серия A, 107 (1): 153–160 , doi : 10.1016/j.jcta.2004.04.002 , MR 2063960.

[ism-4] Альберт, Майкл (2010), «Введение в структурные методы в шаблонах перестановок», Шаблоны перестановок , London Math. Soc. Lecture Note Ser., т. 376, Cambridge Univ. Press, Кембридж, стр. 153–170 , doi :10.1017/CBO9780511902499.008, ISBN 978-0-521-72834-8, г-н 2732828