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

В исследовании перестановок и шаблонов перестановок , А класс перестановок представляет собой набор перестановок, что каждая модель в перестановке в также в . Другими словами, класс перестановок является наследственным свойством перестановок или понижением в порядке паттернов перестановок. ^[1] Класс перестановок также может называться классом шаблонов , закрытым классом или просто классом перестановок. ${\ displaystyle C}$ ${\ displaystyle C}$ ${\ displaystyle C}$

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

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

{\ Displaystyle \ lim _ {п \ к \ infty} | C_ {n} | ^ {1 / n}}

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

Два класса перестановок называются эквивалентными по Вилфу, если для каждого они имеют одинаковое количество перестановок длины . Эквивалентность Уилфа - это отношение эквивалентности, и его классы эквивалентности называются классами Уилфа. Это комбинаторные классы классов перестановок. Считающие функции и эквивалентности Уилфа среди многих конкретных классов перестановок известны. ${\ displaystyle n}$ ${\ displaystyle 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), "Исключенные матрицы перестановок и Стенли-Уилф гипотеза", Журнал комбинаторной теории , Series A, 107 (1): 153-160, DOI : 10.1016 / j.jcta.2004.04.002 , МР 2063960 .
^ Альберт, Майкл (2010), «Введение в структурные методы в шаблонах перестановок», Шаблоны перестановок , London Math. Soc. Lecture Note Ser., 376 , Cambridge Univ. Press, Cambridge, стр 153-170,. Дои : 10,1017 / CBO9780511902499.008 , MR 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), "Исключенные матрицы перестановок и Стенли-Уилф гипотеза", Журнал комбинаторной теории , Series A, 107 (1): 153-160, DOI : 10.1016 / j.jcta.2004.04.002 , МР 2063960 .

[ism-4] Альберт, Майкл (2010), «Введение в структурные методы в шаблонах перестановок», Шаблоны перестановок , London Math. Soc. Lecture Note Ser., 376 , Cambridge Univ. Press, Cambridge, стр 153-170,. Дои : 10,1017 / CBO9780511902499.008 , MR 2732828

[1]