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

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

Например, перестановка π содержит шаблон 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; он имеет десять подпоследовательностей по три записи, но ни одна из этих десяти подпоследовательностей не имеет такого же порядка, как 213.

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

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

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

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

Серьезное изучение шаблонов перестановок началось с Дональдом Кнутом рассмотрения стековой сортировки в 1968 году. ^[3] Кнут показал, что перестановка π может быть отсортирована с помощью стека тогда и только тогда, когда π избегает 231, и что перестановки, сортируемые стеком, нумеруются каталонскими числами . ^[4] Кнут также поднял вопросы о сортировке с помощью деков . В частности, вопрос Кнута о том, сколько перестановок из n элементов можно получить с помощью дека, остается открытым. ^[5] Вскоре после этого Роберт Тарьян ( 1972 ) исследовал сортировку с помощью сетей стопок. ^[6] в то время как Воан Пратт ( 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. ^[7] Поскольку эта коллекция перестановок бесконечна (фактически, это первый опубликованный пример бесконечной антицепи перестановок), не сразу понятно, сколько времени потребуется, чтобы решить, можно ли отсортировать перестановку с помощью дека. Розенштиль и Тарьян (1984) позже представили линейный (по длине π) временной алгоритм, который определяет, может ли π быть отсортировано с помощью двухсторонней очереди. ^[8]

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

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

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

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

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

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

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

б	последовательность, перечисляющая Av _n ( β )	OEIS Справочник	точная ссылка на перечисление
1342	1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...	А022558	Бона (1997) ^[14]
1234	1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...	А005802	Гессель (1990) ^[15]
1324	1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...	А061552	неисчисленный

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

Закрытые занятия

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

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

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

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

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

Учитывая перестановку $\tau$ (называемый текстом ) длины $n$ и еще одна перестановка $\pi$ длины $k$ (называемый шаблоном ), задача сопоставления шаблонов перестановок (PPM) спрашивает, $\pi$ содержится в $\tau$ . Когда оба $n$ и $k$ рассматриваются как переменные, задача известна как NP-полная , а задача подсчета количества таких совпадений — #P-полная . ^[22] Однако PPM можно решить за линейное время , когда k является константой. Действительно, Гиймо и Маркс ^[23] показал, что PPM можно решить за время $2^{O(k^{2}\log k)}\cdot n$ , что означает, что он доступен для фиксированных параметров относительно $k$ .

По мнению Брунера и Лакнера, существует несколько вариантов проблемы PPM. ^[24] Например, если требуется, чтобы совпадение состояло из смежных записей, проблему можно решить за полиномиальное время. ^[25] Другой естественный вариант получается, когда шаблон ограничен правильным классом перестановок. ${\mathcal {C}}$ . Эта проблема известна как ${\mathcal {C}}$ -Pattern PPM, и было показано, что он разрешим за полиномиальное время для разделимых перестановок . ^[22] Позже Елинек и Кынчл ^[26] полностью решена сложность ${\mbox{Av}}(\sigma )$ - Шаблон PPM, показав, что он разрешим за полиномиальное время, когда $\sigma$ равно одному из 1, 12, 21, 132, 231, 312 или 213 и NP-полно в противном случае.

Другой вариант — когда и шаблон, и текст ограничены соответствующим классом перестановок. ${\mathcal {C}}$ , и в этом случае проблема называется ${\mathcal {C}}$ -ППМ. Например, Гиймо и Виалетт. ^[27] показал, что ${\mbox{Av}}(321)$ -PPM можно решить в $O(k^{2}n^{6})$ время. Альберт , Лакнер, Лакнер и Ваттер ^[28] позже снизил это значение до $O(kn)$ и показал, что та же оценка справедлива для класса перестановок с косым слиянием . Они далее спросили, является ли ${\mathcal {C}}$ -Проблема PPM может быть решена за полиномиальное время для каждого фиксированного правильного класса перестановок. ${\mathcal {C}}$ . На этот вопрос отрицательно ответили Елинек и Кинчл, которые показали, что ${\mbox{Av}}(4321)$ -PPM фактически NP-полный. ^[26] Позже Елинек, Оплер и Пекарек. ^[29] показал, что ${\mbox{Av}}(\sigma )$ -PPM NP-полна для любого $\sigma$ длиной не менее 4, не симметричных одному из 3412, 3142, 4213, 4123 или 41352.

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

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

\lim _{n\rightarrow \infty }{\frac {{\text{number of copies of }}\beta {\text{ in a }}\beta {\text{-optimal permutation of length }}n}{\displaystyle {n \choose k}}}.

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

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

б	плотность упаковки	ссылка
1234	1	тривиальный
1432	корень $х 3 - 12 х 2 + 156 х - 64 ≅ 0,42357$	Прайс (1997) ^[30]
2143	$.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 3 / 8 ⁠ = 0.375$	Прайс (1997) ^[30]
1243	$⁠ 3 / 8 ⁠ = 0.375$	Альберт и др. (2002) ^[31]
1324	предположительно ≅ $0,244$
1342	предположительно ≅ $0,19658$
2413	предположительно ≅ $0,10474$

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

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

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

Обобщения

Определенный выше тип шаблона, в котором записи не обязательно должны появляться последовательно, называется классическим шаблоном (перестановкой).Если записи должны быть последовательными, то шаблон называется последовательным шаблоном .

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

Другое обобщение — это шаблон запрета , в котором некоторые записи запрещены. Для π избежать запретного шаблона β означает, что каждый набор записей π, которые образуют копию незапрещенных записей β, может быть расширен, чтобы сформировать копию всех записей β. Уэст (1993) представил эти типы шаблонов в своем исследовании перестановок, которые можно сортировать, дважды пропуская их через стек. ^[37] (Обратите внимание, что определение Уэста о двойной сортировке в стопке — это не то же самое, что сортировка с двумя последовательными стопками.) Другой пример шаблонов с перемычками можно найти в работе Буске-Мелу и Батлера (2007) , которые показали, что многообразие Шуберта, соответствующее до π является локально факториальным тогда и только тогда, когда π избегает 1324 и 21 3 54. ^[38]

Ссылки

^ МакМахон, Перси А. (1915), Комбинаторный анализ , Лондон: Издательство Кембриджского университета, Том I, Раздел III, Глава V.
^ Мак-Магон (1915) , пункты 97 и 98.
^ Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Аддисон-Уэсли, ISBN 0-201-89683-4 , МР 0286317 , OCLC 155842391 .
^ Кнут (1968) , Раздел 2.2.1, Упражнения 4 и 5.
^ Кнут (1968) , Раздел 2.2.1, Упражнение 13, рейтинг M49 в первом издании и M48 во втором.
^ Тарьян, Роберт (1972), «Сортировка с использованием сетей очередей и стеков», Journal of the ACM , 19 (2): 341–346, doi : 10.1145/321694.321704 , MR 0298803 , S2CID 13608929 .
↑ Перейти обратно: Перейти обратно: ^а ^б Пратт, Воган Р. (1973), «Вычисление перестановок с двусторонними очередями. Параллельные стеки и параллельные очереди», Proc. Пятый ежегодный симпозиум ACM по теории вычислений (Остин, Техас, 1973) , стр. 268–277, doi : 10.1145/800125.804058 , MR 0489115 , S2CID 15740957 .
^ Розенштиль, Пьер ; Тарьян, Роберт (1984), «Коды Гаусса, плоские гамильтоновы графы и перестановки, сортируемые стеком», Journal of Algorithms , 5 (3): 375–390, doi : 10.1016/0196-6774(84)90018-X , MR 0756164 .
^ Симион, Родика ; Шмидт, Фрэнк В. (1985), «Ограниченные перестановки», European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR 0829358 .
^ Классон, Андерс; Китаев, Сергей (2008), «Классификация биекций между 321 и 132, избегающими перестановок» , Séminaire Lotharingien de Combinatoire , 60 : B60d, 30pp, arXiv : 0805.1325 , MR 2465405 .
^ Станкова, Звезделина (1994), «Запрещенные подпоследовательности», Дискретная математика , 132 (1–3): 291–316, doi : 10.1016/0012-365X(94)90242-9 , MR 1297387 .
^ Станкова, Звезделина; Уэст, Джулиан (2002), «Новый класс перестановок, эквивалентных Уилфу», Журнал алгебраической комбинаторики , 15 (3): 271–290, arXiv : math/0103152 , doi : 10.1023/A:1015016625432 , MR 1900628 , S2CID 13921676 .
^ Бакелин, Йорген; Уэст, Джулиан; Синь, Гуосе (2007), «Эквивалентность Уилфа для одноэлементных классов», Успехи в прикладной математике , 38 (2): 133–149, doi : 10.1016/j.aam.2004.11.006 , MR 2290807 .
^ Бона, Миклош (1997), «Точное перечисление перестановок, избегающих 1342: тесная связь с помеченными деревьями и плоскими картами», Журнал комбинаторной теории , серия A, 80 (2): 257–272, arXiv : math/9702223 , doi : 10.1006/jcta.1997.2800 , MR 1485138 , S2CID 18352890 .
^ Гессель, Ира М. (1990), «Симметрические функции и P -рекурсивность», Журнал комбинаторной теории , серия A, 53 (2): 257–285, doi : 10.1016/0097-3165(90)90060-A , MR 1041448 .
^ Маркус, Адам; Тардос, Габор (2004), «Исключенные матрицы перестановок и гипотеза Стэнли-Уилфа», Журнал комбинаторной теории , серия A, 107 (1): 153–160, doi : 10.1016/j.jcta.2004.04.002 , MR 2063960 .
^ Уилф, Герберт (2002), «Шаблоны перестановок», Discrete Mathematics , 257 (2): 575–583, doi : 10.1016/S0012-365X(02)00515-0 , MR 1935750 .
^ Саган, Брюс ; Ваттер, Винс (2006), «Функция Мёбиуса композиционного частичного множества», Журнал алгебраической комбинаторики , 24 (2): 117–136, arXiv : math/0507485 , doi : 10.1007/s10801-006-0017-4 , MR 2259013 , S2CID 11283347 .
^ Бурштейн, Александр; Елинек, Вит; Елинкова, Ева; Стейнгримссон, Эйнар (2011), «Функция Мёбиуса разделимых и разложимых перестановок», Журнал комбинаторной теории , серия A, 118 (1): 2346–2364, doi : 10.1016/j.jcta.2011.06.002 , MR 2834180 , S2CID 13978488 .
^ Бригналл, Роберт; Елинек, Вит; Кынчл, Ян; Марчант, Дэвид (2019), «Нули функции Мёбиуса перестановок» (PDF) , Mathematika , 65 (4): 1074–1092, arXiv : 1810.05449 , doi : 10.1112/S0025579319000251 , MR 3992365 , S2CID 53366318
^ Маршан, Дэвид (2020), «2413-воздушные перестановки и рост функции Мёбиуса», Electronic Journal of Combinatorics , 27 (1): Статья P1.7, 18 стр., arXiv : 1812.05064 , doi : 10.37236/8554
↑ Перейти обратно: Перейти обратно: ^а ^б Бозе, Просенджит ; Басс, Джонатан Ф.; Любив, Анна (март 1998 г.), «Сопоставление шаблонов для перестановок», Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190(97)00209-3
^ Гиймо, Сильвен; Маркс, Дэниел (2014). «Нахождение небольших закономерностей в перестановках за линейное время». Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 20. arXiv : 1307.3073 . дои : 10.1137/1.9781611973402.7 . ISBN 978-1-61197-338-9 . S2CID 1846959 .
^ Брунер, Мария-Луиза; Лакнер, Мартин (2013), «Вычислительный ландшафт шаблонов перестановок», Pure Mathematics and Applications , 24 (2): 83–101, arXiv : 1301.0340
^ Кубица, М.; Кульчинский, Т.; Радошевский Дж.; Риттер, В.; Валень, Т. (2013), «Алгоритм с линейным временем для последовательного сопоставления шаблонов перестановок», Information Processing Letters , 113 (12): 430–433, doi : 10.1016/j.ipl.2013.03.015
↑ Перейти обратно: Перейти обратно: ^а ^б Елинек, Вит; Кынчл, Ян (2017). «Трудность сопоставления шаблонов перестановок». Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . СИАМ. стр. 378–396. arXiv : 1608.00529 . дои : 10.1137/1.9781611974782.24 .
^ Гиймо, Сильвен; Виалетт, Стефан (2009), «Сопоставление с образцом для перестановок, избегающих 321», Алгоритмы и вычисления , Конспекты лекций по информатике, том. 5878, стр. 1064–1073, arXiv : 1511.01770 , doi : 10.1007/978-3-642-10631-6_107 , ISBN 978-3-642-10630-9
^ Альберт, Майкл ; Лакнер, Мария-Луиза; Лакнер, Мартин; Ваттер, Винсент (2016), «Сложность сопоставления с образцом для перестановок, избегающих 321, и перестановок с перекосом», Discrete Mathematics & Theoretical Computer Science , 18 (2), arXiv : 1510.06051 , doi : 10.46298/dmtcs.1308 , S2CID 5827603
^ Елинек, Вит; Оплер, Михал; Пекарек, Якуб (2021). «Сетки перестановок и сложность сопоставления с образцом». 46-й Международный симпозиум по математическим основам информатики, MFCS 2021, 23-27 августа 2021, Таллинн, Эстония . Замок Дагштуль – Центр информатики Лейбница. стр. 65:1–65:22. arXiv : 2107.10897 . doi : 10.4230/LIPIcs.MFCS.2021.65 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Прайс, Алкес (1997), Плотность упаковки слоистых узоров , доктор философии. диссертация, Пенсильванский университет, ПроКвест 304421853 .
^ Альберт, Майкл Х .; Аткинсон, доктор медицины; Хэндли, CC; Холтон, Д.А.; Стромквист, В. (2002), «О плотностях упаковки перестановок» , Электронный журнал комбинаторики , 9 : Статья R5, 20 стр., doi : 10.37236/1622 , MR 1887086 .
^ Пресутти, Кэтлин Баттист; Стромквист, Уолтер (2010), «Скорость упаковки и гипотеза о плотности упаковки 2413» , Линтон, Стив; Рушкуц, Ник; Ваттер, Винсент (ред.), Шаблоны перестановок , London Math. Соц. Конспект лекций, том. 376, Издательство Кембриджского университета, стр. 287–316, номер документа : 10.1017/CBO9780511902499.015 , ISBN. 978-0-521-72834-8 .
^ Арратиа, Ричард (1999), «О гипотезе Стэнли-Уилфа о количестве перестановок, избегающих заданного шаблона» , Electronic Journal of Combinatorics , 6 : Статья N1, 4 стр., doi : 10.37236/1477 , MR 1710623 .
^ Энген, Майкл; Ваттер, Винсент (2021), «Содержит все перестановки», American Mathematical Monthly , 128 (1): 4–24, arXiv : 1810.08252 , doi : 10.1080/00029890.2021.1835384
^ Эрикссон, Хенрик; Эрикссон, Киммо; Линуссон, Сванте; Вестлунд, Йохан (2007), «Плотная упаковка шаблонов в перестановке», Annals of Combinatorics , 11 (3–4): 459–470, doi : 10.1007/s00026-007-0329-7 , MR 2376116 , S2CID 2021533 .
^ Бэбсон, Эрик; Стейнгримссон, Эйнар (2000), «Обобщенные шаблоны перестановок и классификация статистики Маона» , Séminaire Lotharingien de Combinatoire , 44 : Исследовательская статья B44b, 18 стр., MR 1758852 .
^ Уэст, Джулиан (1993), «Двойная сортировка по стеку», Theoretical Computer Science , 117 (1–2): 303–313, doi : 10.1016/0304-3975(93)90321-J , MR 1235186 .
^ Буске-Мелу, Мирей ; Батлер, Стив (2007), «Лесоподобные перестановки», Annals of Combinatorics , 11 (3–4): 335–354, arXiv : math/0603617 , doi : 10.1007/s00026-007-0322-1 , MR 2376109 , S2CID 31236417 .

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

Конференция по шаблонам перестановок проводится ежегодно с 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 г., Флорентийский университет , Флоренция, Италия.
Permutation Patterns 2010 , 9–13 августа 2010 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
Permutation Patterns 2011 , 20–24 июня 2011, Калифорнийский политехнический государственный университет , Сан-Луис-Обиспо, Калифорния, США.
Permutation Patterns 2012 , 11–15 июня 2012 г., Университет Стратклайда , Глазго, Шотландия.
Permutation Patterns 2013 , 1–5 июля 2013 г., Парижский университет Дидро , Париж, Франция.
Permutation Patterns 2014 , 7–11 июля 2014 г., Государственный университет Восточного Теннесси , Джонсон-Сити, Теннесси, США.
Permutation Patterns 2015 , 15–19 июня 2015 г., De Morgan House , Лондон, Англия.
Шаблоны перестановок 2016 , 27 июня – 1 июля 2016 г., Университет Говарда , Вашингтон, округ Колумбия, США.
Permutation Patterns 2017 , 26–30 июня 2017 г., Университет Рейкьявика , Рейкьявик, Исландия.
Permutation Patterns 2018 , 9–13 июля 2018 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
Permutation Patterns 2019 , 17–21 июня 2019 г., Цюрихский университет , Цюрих, Швейцария.
Виртуальный семинар Permutation Patterns 2020 , 30 июня – 1 июля 2020 г., организован Университет Вальпараисо , Вальпараисо, Индиана, США.
Виртуальный семинар «Шаблоны перестановок 2021» , 15–16 июня 2021 г., организованный Университетом Стратклайда , Глазго, Шотландия.
Permutation Patterns 2022 , 20-24 июня 2022 г., Университет Вальпараисо , Вальпараисо, Индиана, США.
Permutation Patterns 2023 , 3–7 июля 2023 г., Университет Бургундии , Дижон, Франция.

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

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

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

Семинар по шаблонам перестановок , 29 мая – 3 июня 2005 г., Хайфский университет , Хайфа, Израиль.
Избегание шаблонов и сортировка генома , 14-19 февраля 2016 г., Замок Дагштуль , Вадерн, Германия.
Геномика, предотвращение шаблонов и статистическая механика , 4–9 ноября 2018 г., Замок Дагштуль , Вадерн, Германия.
Избегание шаблонов, статистическая механика и вычислительная сложность , 19–24 марта 2023 г., Schloss Dagstuhl , Вадерн, Германия.

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

PermLab: программное обеспечение для шаблонов перестановок , поддерживаемое Майклом Альбертом .
База данных по предотвращению шаблонов перестановок , поддерживаемая Бриджит Теннер.
PermPAL: Библиотека предотвращения шаблонов перестановок , база данных алгоритмически полученных теорем о классах перестановок, поддерживаемая Кристианом Бином, Эмилем Надо, Джеем Пантоне и Хеннингом Ульфарссоном.

[1] МакМахон, Перси А. (1915), Комбинаторный анализ , Лондон: Издательство Кембриджского университета, Том I, Раздел III, Глава V.

[2] Мак-Магон (1915) , пункты 97 и 98.

[3] Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Аддисон-Уэсли, ISBN 0-201-89683-4 , МР 0286317 , OCLC 155842391 .

[4] Кнут (1968) , Раздел 2.2.1, Упражнения 4 и 5.

[5] Кнут (1968) , Раздел 2.2.1, Упражнение 13, рейтинг M49 в первом издании и M48 во втором.

[6] Тарьян, Роберт (1972), «Сортировка с использованием сетей очередей и стеков», Journal of the ACM , 19 (2): 341–346, doi : 10.1145/321694.321704 , MR 0298803 , S2CID 13608929 .

[pratt73-7] Перейти обратно: Перейти обратно: ^а ^б Пратт, Воган Р. (1973), «Вычисление перестановок с двусторонними очередями. Параллельные стеки и параллельные очереди», Proc. Пятый ежегодный симпозиум ACM по теории вычислений (Остин, Техас, 1973) , стр. 268–277, doi : 10.1145/800125.804058 , MR 0489115 , S2CID 15740957 .

[8] Розенштиль, Пьер ; Тарьян, Роберт (1984), «Коды Гаусса, плоские гамильтоновы графы и перестановки, сортируемые стеком», Journal of Algorithms , 5 (3): 375–390, doi : 10.1016/0196-6774(84)90018-X , MR 0756164 .

[9] Симион, Родика ; Шмидт, Фрэнк В. (1985), «Ограниченные перестановки», European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR 0829358 .

[10] Классон, Андерс; Китаев, Сергей (2008), «Классификация биекций между 321 и 132, избегающими перестановок» , Séminaire Lotharingien de Combinatoire , 60 : B60d, 30pp, arXiv : 0805.1325 , MR 2465405 .

[11] Станкова, Звезделина (1994), «Запрещенные подпоследовательности», Дискретная математика , 132 (1–3): 291–316, doi : 10.1016/0012-365X(94)90242-9 , MR 1297387 .

[12] Станкова, Звезделина; Уэст, Джулиан (2002), «Новый класс перестановок, эквивалентных Уилфу», Журнал алгебраической комбинаторики , 15 (3): 271–290, arXiv : math/0103152 , doi : 10.1023/A:1015016625432 , MR 1900628 , S2CID 13921676 .

[13] Бакелин, Йорген; Уэст, Джулиан; Синь, Гуосе (2007), «Эквивалентность Уилфа для одноэлементных классов», Успехи в прикладной математике , 38 (2): 133–149, doi : 10.1016/j.aam.2004.11.006 , MR 2290807 .

[14] Бона, Миклош (1997), «Точное перечисление перестановок, избегающих 1342: тесная связь с помеченными деревьями и плоскими картами», Журнал комбинаторной теории , серия A, 80 (2): 257–272, arXiv : math/9702223 , doi : 10.1006/jcta.1997.2800 , MR 1485138 , S2CID 18352890 .

[gessel90-15] Гессель, Ира М. (1990), «Симметрические функции и P -рекурсивность», Журнал комбинаторной теории , серия A, 53 (2): 257–285, doi : 10.1016/0097-3165(90)90060-A , MR 1041448 .

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

[17] Уилф, Герберт (2002), «Шаблоны перестановок», Discrete Mathematics , 257 (2): 575–583, doi : 10.1016/S0012-365X(02)00515-0 , MR 1935750 .

[18] Саган, Брюс ; Ваттер, Винс (2006), «Функция Мёбиуса композиционного частичного множества», Журнал алгебраической комбинаторики , 24 (2): 117–136, arXiv : math/0507485 , doi : 10.1007/s10801-006-0017-4 , MR 2259013 , S2CID 11283347 .

[19] Бурштейн, Александр; Елинек, Вит; Елинкова, Ева; Стейнгримссон, Эйнар (2011), «Функция Мёбиуса разделимых и разложимых перестановок», Журнал комбинаторной теории , серия A, 118 (1): 2346–2364, doi : 10.1016/j.jcta.2011.06.002 , MR 2834180 , S2CID 13978488 .

[20] Бригналл, Роберт; Елинек, Вит; Кынчл, Ян; Марчант, Дэвид (2019), «Нули функции Мёбиуса перестановок» (PDF) , Mathematika , 65 (4): 1074–1092, arXiv : 1810.05449 , doi : 10.1112/S0025579319000251 , MR 3992365 , S2CID 53366318

[21] Маршан, Дэвид (2020), «2413-воздушные перестановки и рост функции Мёбиуса», Electronic Journal of Combinatorics , 27 (1): Статья P1.7, 18 стр., arXiv : 1812.05064 , doi : 10.37236/8554

[BBL_1998-22] Перейти обратно: Перейти обратно: ^а ^б Бозе, Просенджит ; Басс, Джонатан Ф.; Любив, Анна (март 1998 г.), «Сопоставление шаблонов для перестановок», Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190(97)00209-3

[23] Гиймо, Сильвен; Маркс, Дэниел (2014). «Нахождение небольших закономерностей в перестановках за линейное время». Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 20. arXiv : 1307.3073 . дои : 10.1137/1.9781611973402.7 . ISBN 978-1-61197-338-9 . S2CID 1846959 .

[24] Брунер, Мария-Луиза; Лакнер, Мартин (2013), «Вычислительный ландшафт шаблонов перестановок», Pure Mathematics and Applications , 24 (2): 83–101, arXiv : 1301.0340

[25] Кубица, М.; Кульчинский, Т.; Радошевский Дж.; Риттер, В.; Валень, Т. (2013), «Алгоритм с линейным временем для последовательного сопоставления шаблонов перестановок», Information Processing Letters , 113 (12): 430–433, doi : 10.1016/j.ipl.2013.03.015

[JK_2017-26] Перейти обратно: Перейти обратно: ^а ^б Елинек, Вит; Кынчл, Ян (2017). «Трудность сопоставления шаблонов перестановок». Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . СИАМ. стр. 378–396. arXiv : 1608.00529 . дои : 10.1137/1.9781611974782.24 .

[27] Гиймо, Сильвен; Виалетт, Стефан (2009), «Сопоставление с образцом для перестановок, избегающих 321», Алгоритмы и вычисления , Конспекты лекций по информатике, том. 5878, стр. 1064–1073, arXiv : 1511.01770 , doi : 10.1007/978-3-642-10631-6_107 , ISBN 978-3-642-10630-9

[28] Альберт, Майкл ; Лакнер, Мария-Луиза; Лакнер, Мартин; Ваттер, Винсент (2016), «Сложность сопоставления с образцом для перестановок, избегающих 321, и перестановок с перекосом», Discrete Mathematics & Theoretical Computer Science , 18 (2), arXiv : 1510.06051 , doi : 10.46298/dmtcs.1308 , S2CID 5827603

[29] Елинек, Вит; Оплер, Михал; Пекарек, Якуб (2021). «Сетки перестановок и сложность сопоставления с образцом». 46-й Международный симпозиум по математическим основам информатики, MFCS 2021, 23-27 августа 2021, Таллинн, Эстония . Замок Дагштуль – Центр информатики Лейбница. стр. 65:1–65:22. arXiv : 2107.10897 . doi : 10.4230/LIPIcs.MFCS.2021.65 .

[price97-30] Перейти обратно: Перейти обратно: ^а ^б ^с Прайс, Алкес (1997), Плотность упаковки слоистых узоров , доктор философии. диссертация, Пенсильванский университет, ПроКвест 304421853 .

[31] Альберт, Майкл Х .; Аткинсон, доктор медицины; Хэндли, CC; Холтон, Д.А.; Стромквист, В. (2002), «О плотностях упаковки перестановок» , Электронный журнал комбинаторики , 9 : Статья R5, 20 стр., doi : 10.37236/1622 , MR 1887086 .

[32] Пресутти, Кэтлин Баттист; Стромквист, Уолтер (2010), «Скорость упаковки и гипотеза о плотности упаковки 2413» , Линтон, Стив; Рушкуц, Ник; Ваттер, Винсент (ред.), Шаблоны перестановок , London Math. Соц. Конспект лекций, том. 376, Издательство Кембриджского университета, стр. 287–316, номер документа : 10.1017/CBO9780511902499.015 , ISBN. 978-0-521-72834-8 .

[33] Арратиа, Ричард (1999), «О гипотезе Стэнли-Уилфа о количестве перестановок, избегающих заданного шаблона» , Electronic Journal of Combinatorics , 6 : Статья N1, 4 стр., doi : 10.37236/1477 , MR 1710623 .

[engenvatter-34] Энген, Майкл; Ваттер, Винсент (2021), «Содержит все перестановки», American Mathematical Monthly , 128 (1): 4–24, arXiv : 1810.08252 , doi : 10.1080/00029890.2021.1835384

[eelw-35] Эрикссон, Хенрик; Эрикссон, Киммо; Линуссон, Сванте; Вестлунд, Йохан (2007), «Плотная упаковка шаблонов в перестановке», Annals of Combinatorics , 11 (3–4): 459–470, doi : 10.1007/s00026-007-0329-7 , MR 2376116 , S2CID 2021533 .

[36] Бэбсон, Эрик; Стейнгримссон, Эйнар (2000), «Обобщенные шаблоны перестановок и классификация статистики Маона» , Séminaire Lotharingien de Combinatoire , 44 : Исследовательская статья B44b, 18 стр., MR 1758852 .

[37] Уэст, Джулиан (1993), «Двойная сортировка по стеку», Theoretical Computer Science , 117 (1–2): 303–313, doi : 10.1016/0304-3975(93)90321-J , MR 1235186 .

[38] Буске-Мелу, Мирей ; Батлер, Стив (2007), «Лесоподобные перестановки», Annals of Combinatorics , 11 (3–4): 335–354, arXiv : math/0603617 , doi : 10.1007/s00026-007-0322-1 , MR 2376109 , S2CID 31236417 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]