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

редактировать

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

Например, перестановка π содержит шаблон 213 всякий раз, когда π имеет три цифры x, y и z, которые появляются внутри π в порядке x... y... z, но значения которых упорядочены как y < x < z, the same as the ordering of the values in the permutation 213. The permutation 32415 on five elements contains 213 as a pattern in several different ways: 3··15, ··415, 32··5, 324··, and ·2·15 all form triples of digits with the same ordering as 213. Each of the subsequences 315, 415, 325, 324, and 215 is called a copy, instance, or occurrence of the pattern. The fact that π contains σ is written more concisely as σ ≤ π. If a permutation π does not contain a pattern σ, then π is said to avoid σ. The permutation 51342 avoids 213; it has 10 subsequences of three digits, but none of these 10 subsequences has the same ordering as 213.

Содержание

1 Первые результаты
2 Истоки информатики
3 Источники перечисления
4 Закрытые классы
5 Функция Мёбиуса
6 Вычислительная сложность
7 Плотность упаковки
8 Суперпаттерны
9 Обобщения
10 Ссылки
11 Внешние ссылки

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

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

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

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

Изучение паттернов перестановок всерьез началось с Дональд Кнут рассмотрел сортировку стека в 1968 году. Кнут показал, что перестановка π может быть отсортирована по стеку тогда и только тогда, когда π избегает 231, и что перестановки, сортируемые по стеку, нумеруются каталонскими числами. Кнут также поднял вопросы о сортировке с помощью дека. В частности, вопрос Кнута о том, сколько перестановок из n элементов можно получить с использованием двухсторонней очереди, остается открытым. Вскоре после этого Роберт Тарджан (1972) исследовал сортировку по сетям стопок, а Воан Пратт (1973) показал, что перестановка π может быть отсортирован по двухсторонней очереди тогда и только тогда, когда для всех k π избегает 5,2,7,4,..., 4k + 1,4k − 2,3,4k, 1 и 5,2,7,4,..., 4k + 3,4k, 1,4k + 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, где β обозначает обратное β, а β обозначает обратное β. (Эти две операции генерируют группу диэдра D 8 с естественным действием на матрицы перестановок.) Однако есть также многочисленные примеры нетривиальных эквивалентностей Уилфа (например, между 123 и 231):

Станкова (1994) доказала, что перестановки 1342 и 2413 эквивалентны Уилфу.
Станкова и Вест (2002) доказали, что для любой перестановки β, перестановки 231 ⊕ β и 312 ⊕ β эквивалентны Уилфу, где ⊕ обозначает операцию прямой суммы.
Backelin, West Xin (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	Gessel (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950,...	A061552	ненумерованный

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

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

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

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

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

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

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

При перестановке $τ {\ displaystyle \ tau}$ $\ tau$ (называемый текстом) длины $n {\ displaystyle n}$ $n$ и другая перестановка $π {\ displaystyle \ pi}$ $\ pi$ длины $k {\ displaystyle k}$ $k$ (называемая шаблоном), шаблон перестановки Задача сопоставления (PPM) спрашивает, содержится ли $π {\ displaystyle \ pi}$ $\ pi$ в $τ {\ displaystyle \ tau}$ $\ tau$ . Когда и $n {\ displaystyle n}$ $n$ , и $k {\ displaystyle k}$ $k$ рассматриваются как переменные, известно, что проблема NP-полная., а проблема подсчета количества таких совпадений - # P-complete. Однако PPM можно решить за линейное время, когда k является постоянным. Действительно, Гийемо и Маркс показали, что PPM может быть решена за время $2 O (k 2 log ⁡ k) ⋅ n {\ displaystyle 2 ^ {O (k ^ {2} \ log k)} \ cdot n}$ $2 ^ {O (k ^ {2} \ log k)} \ cdot n$ , что означает, что она управляема с фиксированными параметрами по отношению к $k {\ displaystyle k}$ $k$ .

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

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

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

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

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

\ 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 - 12x + 156x - 64 ≅ 0,42357	Прайс (1997)
2143	⅜ = 0,375	Прайс (1997)
1243	⅜ = 0,375	Albert et al. (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, и предполагается, что это истинная плотность упаковки.

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

k- суперсаттерн - это перестановка, которая содержит все перестановки длины k. Например, 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 (π). Эти шаблоны были введены Babson Steingrímsson (2000), которые показали, что почти все известные могут быть выражены в терминах винкулярных перестановок. Например, Главный индекс числа π равен 1-32 (π) + 2-31 (π) + 3-21 (π) + 21 (π).

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

Ссылки

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

Викискладе есть средства массовой информации, связанные с шаблонами перестановок.

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

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

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

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

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

Семинар по моделям перестановок, 29 мая – июнь 3, 2005, Университет Хайфы, Хайфа, Израиль.

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

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