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

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

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

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

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

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

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