Шаблон перестановки - Permutation pattern

В комбинаторной математике и теоретической информатике , шаблон перестановок является суб-перестановка более перестановки . Любая перестановка может быть записана в однострочном формате как последовательность цифр, представляющая результат применения перестановки к последовательности цифр 123 ...; например, последовательность цифр 213 представляет собой перестановку трех элементов, которая меняет местами элементы 1 и 2. Если π и σ представляют собой две перестановки, представленные таким образом (эти имена переменных являются стандартными для перестановок и не связаны с числом пи ), то π равно говорят, что содержат σ как образец, если некоторая подпоследовательность цифр π имеет тот же относительный порядок, что и все цифры σ.

Например, перестановка π содержит шаблон 213 всякий раз, когда π имеет три цифры x , y и z, которые появляются в π в порядке x ... y ... z, но значения которых упорядочены как y  <  x  <  z , то же самое как порядок значений в перестановке 213. Перестановка 32415 на пяти элементах содержит 213 как образец несколькими различными способами: 3 ·· 15, ·· 415, 32 ·· 5, 324 ·· и · 2 · 15 все образуют тройки цифр с тем же порядком, что и 213. Каждая из подпоследовательностей 315, 415, 325, 324 и 215 называется копией, экземпляром или вхождением шаблона. Тот факт, что π содержит σ, более кратко записывается как σ ≤ π. Если перестановка π не содержит шаблона σ, то говорят, что π избегает σ. Перестановка 51342 позволяет избежать 213; он имеет 10 подпоследовательностей из трех цифр, но ни одна из этих 10 подпоследовательностей не имеет того же порядка, что и 213.

Первые результаты

Можно утверждать, что Перси Мак-Магон  ( 1915 ) был первым, кто доказал результат в этой области своим исследованием «решеточных перестановок». В частности, Мак-Магон показывает, что перестановки, которые можно разделить на две убывающие подпоследовательности (т. Е. Перестановки, избегающие 123), подсчитываются каталонскими числами .

Еще один ранний важный результат в этой области - теорема Эрдеша – Секереса ; на языке шаблонов перестановок теорема утверждает, что для любых положительных целых чисел a и b каждая перестановка длины по крайней мере должна содержать либо образец, либо образец . ${\ Displaystyle (а-1) (б-1) +1}$${\ Displaystyle 1,2,3, \ точки, а}$${\ displaystyle b, b-1, \ dots, 2,1}$

Истоки информатики

Изучение моделей перестановок началось всерьез с Дональдом Кнутом рассмотрением «s в стеке-сортировочном в 1968 г. Кнут показал , что перестановка π может быть отсортирован по стеке , если и только если π избегает 231, и что стек-сортировки перестановки перечислены по каталонским числам . Кнут также поднял вопросы о сортировке с помощью дека . В частности, вопрос Кнута о том, сколько перестановок из n элементов можно получить с использованием двухсторонней очереди, остается открытым. Вскоре после этого Роберт Тарджан  ( 1972 ) исследовал сортировку сетями стеков, в то время как Воан Пратт  ( 1973 ) показал, что перестановка π может быть отсортирована по двухсторонней очереди тогда и только тогда, когда для всех k , π избегает 5,2,7,4, ..., 4 k +1,4 k −2,3,4 k , 1 и 5,2,7,4, ..., 4 k +3,4 k , 1,4 k +2,3 , и каждая перестановка, которая может быть получена из любого из них, заменяя последние два элемента или 1 и 2. Поскольку этот набор перестановок бесконечен (фактически, это первый опубликованный пример бесконечной антицепи перестановок), не сразу понятно, сколько времени потребуется, чтобы решить, может ли перестановка быть отсортирована по двухсторонней очереди. Позже Rosenstiehl и Tarjan (1984) представили линейный (по длине π) алгоритм времени, который определяет, можно ли отсортировать π по двухсторонней очереди.

В своей статье Пратт заметил, что этот порядок паттернов перестановки «кажется единственным частичным порядком перестановок, который возникает простым и естественным образом», и в заключение отмечает, что «с абстрактной точки зрения» порядок паттернов перестановок «является даже интереснее, чем описываемые нами сети ».

Перечислительное происхождение

Важной целью в изучении паттернов перестановок является перечисление перестановок, избегая фиксированной (и обычно короткой) перестановки или набора перестановок. Пусть Av _n (B) обозначает набор перестановок длины n, которые избегают всех перестановок в множестве B (в случае, когда B одноэлементный, скажем β, вместо этого используется сокращение Av _n (β)). Как отмечалось выше, Мак-Магон и Кнут показали, что | Av _n (123) | = | Av _n (231) | = C _n , n- е каталонское число. Таким образом, это изоморфные комбинаторные классы .

Simion & Schmidt (1985) была первой статьей, в которой основное внимание уделялось исключительно перечислению. Среди других результатов Симион и Шмидт подсчитали четные и нечетные перестановки, избегая шаблона длины три, подсчитали перестановки, избегая двух шаблонов длины три , и дали первое биективное доказательство того, что перестановки, избегающие 123 и 231, равносильны. Со времени публикации их статьи было дано много других взаимных предположений , см. Обзор Claesson & Kitaev (2008) .

В общем, если | Av _n (β) | = | Av _n (σ) | для всех n , то β и σ называются Wilf-эквивалентными . Многие эквивалентности Вильфа проистекают из тривиального факта, что | Av _n (β) | = | Av _n ( β ⁻¹ ) | = | Av _n (β ^об. ) | для всех n , где β ^-1 обозначает обратное β, а β ^rev обозначает обратное β. (Эти две операции порождают группу диэдра D ₈ с естественным действием на матрицы перестановок .) Однако есть также многочисленные примеры нетривиальных эквивалентностей Вильфа (например, между 123 и 231 ):

• Станкова (1994) доказала, что перестановки 1342 и 2413 эквивалентны Вильфу.
• Станкова и Вест (2002) доказали, что для любой перестановки β перестановки 231 ⊕ β и 312 ⊕ β эквивалентны Вильфу, где ⊕ обозначает операцию прямого суммирования .
• Бакелин, Вест и Ксин (2007) доказали, что для любой перестановки β и любого натурального числа m перестановки 12 .. m ⊕ β и m ... 21 ⊕  β эквивалентны Вильфу.

Из этих двух эквивалентностей Вильфа и обратной и обратной симметрии следует, что существуют три различные последовательности | Av _n (β) | где β имеет длину четыре:

β	последовательность, перечисляющая Av n (β)	Ссылка OEIS	ссылка на точное перечисление
1342	1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...	A022558	Бона (1997)
1234	1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...	A005802	Гессель (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...	A061552	не пронумерованный

В конце 1980-х Ричард Стэнли и Герберт Уилф предположили, что для каждой перестановки β существует некоторая константа K такая, что | Av _n (β) | < K ⁿ . Это было известно как гипотеза Стэнли – Уилфа, пока не была доказана Адамом Маркусом и Габором Тардосом .

Закрытые классы

Замкнутый класс , также известный как класс рисунка , класс перестановок , или просто класс перестановок является Downset в порядке перестановки шаблона. Каждый класс может быть определен минимальными перестановками, которые не лежат внутри него, его основы . Таким образом, базис для перестановок, сортируемых по стеку, равен {231}, а базис для перестановок, сортируемых по стеку, бесконечен. Производящая функция для класса Σ х ^{| π |} где сумма берется по всем перестановкам π в классе.

Функция Мёбиуса

Поскольку набор перестановок в соответствии с порядком включения образует элементарный набор, естественно спросить о его функции Мёбиуса , цель, впервые явно указанная Вилфом (2002) . Цель таких исследований - найти формулу для функции Мёбиуса интервала [σ, π] в шаблоне перестановки poset, которая более эффективна, чем наивное рекурсивное определение. Первый такой результат был установлен Саганом и Ваттером (2006) , которые дали формулу для функции Мебиуса интервала слоистых перестановок . Позже Бурштейн и др. (2011) обобщили этот результат на интервалы разделимых перестановок .

Известно, что асимптотически не менее 39,95% всех перестановок π длины n удовлетворяют условию μ (1, π) = 0 (то есть главная функция Мёбиуса равна нулю), но для каждого n существуют перестановки π такие что μ (1, π) - экспоненциальная функция от n .

Вычислительная сложность

Учитывая перестановку (называемую текстом ) длины и другую перестановку длины (называемую шаблоном ), проблема сопоставления с образцом перестановки (PPM) спрашивает, содержится ли в . Когда оба и рассматриваются как переменные, проблема, как известно, является NP-полной , а проблема подсчета количества таких совпадений является # P-полной . Однако PPM можно решить за линейное время, когда k является константой. Действительно, Гийемо и Маркс показали, что PPM может быть решен во времени , а это означает, что это фиксированный параметр, управляемый по отношению к . ${\ Displaystyle \ тау}$${\ displaystyle n}$${\ displaystyle \ pi}$${\ displaystyle k}$${\ displaystyle \ pi}$${\ Displaystyle \ тау}$${\ displaystyle n}$${\ displaystyle k}$${\ Displaystyle 2 ^ {О (к ^ {2} \ журнал к)} \ CDOT п}$${\ displaystyle k}$

Согласно обзору Брунера и Лакнера, существует несколько вариантов проблемы PPM. Например, если требуется, чтобы совпадение состояло из смежных записей, проблема может быть решена за полиномиальное время.

Другой вариант - когда и шаблон, и текст ограничены правильным классом перестановки , и в этом случае проблема называется -PPM. Например, Guillemot и Vialette показали, что -PPM можно решить вовремя. Альберт , Лакнер, Лакнер и Ваттер позже понизили это до и показали, что такая же оценка верна для класса перестановок с перекосом слияния . Далее они спросили, может ли проблема -PPM быть решена за полиномиальное время для каждого фиксированного надлежащего класса перестановок . ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle {\ mbox {Av}} (321)}$${\ Displaystyle О (к ^ {2} п ^ {6})}$${\ displaystyle O (kn)}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle {\ mathcal {C}}}$

Плотность упаковки

Перестановка π называется β- оптимальной, если никакая перестановка той же длины, что и π, не имеет большего количества копий β. В своем выступлении на собрании SIAM по дискретной математике в 1992 году Уилф определил плотность упаковки перестановки β длины k как

${\ displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {{\ text {количество копий}} \ beta {\ text {in a}} \ beta {\ text {-оптимальная перестановка длины}} n} {\ displaystyle {n \ choose k}}}.}$

Неопубликованные аргументы Фреда Гэлвина показывают, что величина внутри этого предела не возрастает при n ≥ k , и поэтому предел существует. Когда β является монотонным, его плотность упаковки, очевидно, равна 1, а плотности упаковки инвариантны относительно группы симметрий, порождаемых обратной и обратной, поэтому для перестановок длины три существует только одна нетривиальная плотность упаковки. Уолтер Стромквист (неопубликованный) разрешил этот случай, показав, что плотность упаковки 132 составляет 2 √ 3  - 3, приблизительно 0,46410.

Для перестановок β длины четыре необходимо рассмотреть (из-за симметрии) семь случаев:

β	плотность упаковки	Справка
1234	1	банальный
1432	корень x 3 - 12 x 2 + 156 x - 64 ≅ 0,42357	Цена (1997)
2143	⅜ = 0,375	Цена (1997)
1243	⅜ = 0,375	Альберт и др. (2002)
1324	предполагается, что ≅ 0,244
1342	предполагается, что это 0,19658 фунтов стерлингов
2413	предположительно равняется 0,10474 ≅

Для трех неизвестных перестановок существуют оценки и предположения. Прайс (1997) использовал алгоритм аппроксимации, который предполагает, что плотность упаковки 1324 составляет около 0,244. Биржан Баткеев (неопубликовано) построил семейство перестановок, показывающих, что плотность упаковки 1342, по крайней мере, является произведением плотностей упаковки 132 и 1432, приблизительно 0,19658. Предполагается, что это точная плотность упаковки 1342. Presutti & Stromquist (2010) предоставили нижнюю границу плотности упаковки 2413. Эта нижняя граница, которая может быть выражена через интеграл, составляет приблизительно 0,10474 и предположительно - истинная плотность упаковки.

Суперпаттерны

К - superpattern перестановка , которая содержит все перестановки длины к . Например, 25314 - это 3-суперпаттерн, потому что он содержит все 6 перестановок длины 3. Известно, что k -суперпаттерны должны иметь длину не менее k ² / e ² , где e  ≈ 2,71828 - число Эйлера , и что существует k -супершаблоны длины ⌈ ( k ²  + 1) / 2⌉. Предполагается, что эта верхняя граница является наилучшей с точностью до членов нижнего порядка.

Обобщения

Есть несколько способов обобщения понятия «паттерн». Например, винкулярный узор - это перестановка, содержащая дефисы, обозначающие записи, которые не обязательно должны появляться последовательно (в обычном определении шаблона не требуется, чтобы записи происходили последовательно). Например, перестановка 314265 имеет две копии пунктирного шаблона 2-31-4, заданных записями 3426 и 3425. Для штрихового шаблона β и любой перестановки π мы пишем β (π) для количества копий β. в π. Таким образом, количество инверсий в π равно 2-1 (π), а количество спусков - 21 (π). Далее, количество впадин в π составляет 213 (π) + 312 (π), а количество пиков составляет 231 (π) + 132 (π). Эти закономерности были введены Бабсоном и Штейнгримссоном (2000) , которые показали, что почти вся известная статистика Махона может быть выражена в терминах винкулярных перестановок. Например, основной индекс π равен 1-32 (π) + 2-31 (π) + 3-21 (π) + 21 (π).

Другое обобщение - это модель с полосой , в которой некоторые входы запрещены. Для π, чтобы избежать шаблона с перемычкой, β означает, что каждый набор записей π, которые образуют копию записей без перемычки β, может быть расширен, чтобы сформировать копию всех записей β. Уэст (1993) ввел эти типы паттернов в свое исследование перестановок, которые можно было отсортировать, дважды пропустив их через стек. (Обратите внимание, что определение Уэста сортировки дважды по стопке не то же самое, что сортировка с двумя последовательными стопками.) Другой пример полосатых шаблонов встречается в работе Bousquet-Mélou & Butler (2007) , которые показали, что многообразие Шуберта соответствует to π локально факториально тогда и только тогда, когда π избегает 1324 и 21 3 54.

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

Внешние ссылки

Конференция по шаблонам перестановок проводится ежегодно с 2003 года :

1. Паттерны перестановки 2003 г. , 10–14 февраля 2003 г., Университет Отаго , Данидин, Новая Зеландия.
2. Паттерны перестановки 2004 г. , 5–9 июля 2004 г., Университет-колледж Маласпины , Нанаймо, Британская Колумбия, Канада.
3. Паттерны перестановки 2005 г. , 7–11 марта 2005 г., Университет Флориды , Гейнсвилл, Флорида, США.
4. Паттерны перестановки 2006 г. , 12–16 июня 2006 г., Рейкьявикский университет , Рейкьявик, Исландия.
5. Паттерны перестановки 2007 г. , 11–15 июня 2007 г., Университет Сент-Эндрюс , Сент-Эндрюс, Шотландия.
6. Паттерны перестановки 2008 г. , 16–20 июня 2008 г., Университет Отаго , Данидин, Новая Зеландия.
7. Паттерны перестановки 2009 г. , 13–17 июля 2009 г., Университет Флоренции , Флоренция, Италия.
8. Паттерны перестановки 2010 г. , 9–13 августа 2010 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
9. Шаблоны перестановок 2011 г. , 20–24 июня 2011 г., Калифорнийский политехнический государственный университет , Сан-Луис-Обиспо, Калифорния, США.
10. Паттерны перестановки 2012 г. , 11–15 июня 2012 г., Стратклайдский университет , Глазго, Шотландия.
11. Шаблоны перестановок 2013 , 1–5 июля 2013 г., Парижский университет Дидро , Париж, Франция.
12. Шаблоны перестановок 2014 г. , 7–11 июля 2014 г., Государственный университет Восточного Теннесси , Джонсон-Сити, Теннесси, США.
13. Паттерны перестановки 2015 г. , 15–19 июня 2015 г., De Morgan House , Лондон, Англия.
14. Паттерны перестановки 2016 г. , 27 июня - 1 июля 2016 г., Университет Говарда , Вашингтон, округ Колумбия, США.
15. Шаблоны перестановок 2017 г. , 26–30 июня 2017 г., Рейкьявикский университет , Рейкьявик, Исландия.
16. Шаблоны перестановок 2018 , 9–13 июля 2018 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
17. Шаблоны перестановок 2019 , 17–21 июня 2019 г., Университет Цюриха , Цюрих, Швейцария.
18. Виртуальный семинар по шаблонам перестановок 2020 , 30 июня - 1 июля 2020 г., организованный Университетом Вальпараисо, Вальпараисо, Индиана, США.
19. Виртуальный семинар по шаблонам перестановок 2021 , 15–16 июня 2021 г., организованный Университетом Стратклайда , Глазго, Шотландия.

Специальные сессии Американского математического общества по шаблонам в перестановках проводились на следующих собраниях:

• Осеннее собрание Восточной секции , 22–23 сентября 2012 г., Рочестерский технологический институт , Рочестер, штат Нью-Йорк.
• Совместные встречи по математике , 12 января 2013 г., Сан-Диего, Калифорния.
• Секционное собрание Central Fall , 20–21 сентября 2014 г., Университет Висконсин-О-Клэр , О-Клэр, Висконсин.
• Весеннее восточное секционное собрание , 7–8 марта 2015 г., Джорджтаунский университет , Вашингтон, округ Колумбия.

Встречи с другими шаблонами перестановки:

• Семинар по шаблонам перестановок , 29 мая - 3 июня 2005 г., Хайфский университет , Хайфа, Израиль.

Другие ссылки:

• PermLab: программное обеспечение для шаблонов перестановок , поддерживаемое Майклом Альбертом .
• База данных избегания шаблонов перестановок , поддерживаемая Бриджит Теннер.