В комбинаторной математике и теоретической информатике , шаблон перестановок является суб-перестановка более перестановки . Любая перестановка может быть записана в однострочном формате как последовательность цифр, представляющая результат применения перестановки к последовательности цифр 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 ) был первым, кто доказал результат в этой области своим исследованием «решеточных перестановок». [1] В частности, Мак-Магон показывает, что перестановки, которые можно разделить на две убывающие подпоследовательности (т. Е. Перестановки, избегающие 123), подсчитываются каталонскими числами . [2]
Еще один ранний важный результат в этой области - теорема Эрдеша – Секереса ; на языке шаблонов перестановок теорема утверждает, что для любых натуральных чисел a и b каждая перестановка длины не менее должен содержать либо образец или узор .
Истоки информатики
Изучение моделей перестановок началось всерьез с Дональдом Кнутом рассмотрением «s из стека сортировки в 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] Поскольку этот набор перестановок бесконечен (фактически, это первый опубликованный пример бесконечной антицепи перестановок), не сразу понятно, сколько времени потребуется, чтобы решить, может ли перестановка быть отсортирована по двухсторонней очереди. Позже Rosenstiehl и Tarjan (1984) представили линейный (по длине π) алгоритм времени, который определяет, можно ли отсортировать π по двухсторонней очереди. [8]
В своей статье Пратт заметил, что этот порядок паттернов перестановки «кажется единственным частичным порядком перестановок, который возникает простым и естественным образом», и в заключение отмечает, что «с абстрактной точки зрения» порядок паттернов перестановок «является даже интереснее, чем описываемые нами сети ». [7]
Перечислительное происхождение
Важной целью изучения паттернов перестановок является перечисление перестановок, избегая фиксированной (и обычно короткой) перестановки или набора перестановок. Пусть Av n (B) обозначает набор перестановок длины n, которые избегают всех перестановок в наборе B (в случае, когда B одноэлементный, скажем β, вместо него используется сокращение Av n (β)). Как отмечалось выше, Мак-Магон и Кнут показали, что | Av n (123) | = | Av n (231) | = C n , n- е каталонское число. Таким образом, это изоморфные комбинаторные классы .
Simion & Schmidt (1985) была первой статьей, в которой основное внимание уделялось исключительно перечислению. Среди других результатов Симион и Шмидт подсчитали четные и нечетные перестановки, избегая шаблона длины три, подсчитали перестановки, избегая двух шаблонов длины три , и дали первое биективное доказательство того, что перестановки, избегающие 123 и 231, равносильны. [9] Со времени публикации их статьи было дано много других взаимных предположений , см. Обзор Claesson & Kitaev (2008) . [10]
В общем, если | Av n (β) | = | Av n (σ) | для всех n , то β и σ называются Wilf-эквивалентными . Многие эквивалентности Вильфа проистекают из тривиального факта, что | Av n (β) | = | Av n ( β −1 ) | = | Av n (β об. ) | для всех n , где β -1 обозначает обратное β, а β rev обозначает обратное β. (Эти две операции порождают группу диэдра D 8 с естественным действием на матрицы перестановок .) Однако есть также многочисленные примеры нетривиальных эквивалентностей Вильфа (например, между 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, ... | A022558 | Бона (1997) [14] |
1234 | 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... | A005802 | Гессель (1990) [15] |
1324 | 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... | A061552 | не пронумерованный |
В конце 1980-х Ричард Стэнли и Герберт Уилф предположили, что для каждой перестановки β существует некоторая константа K такая, что | Av n (β) | < K n . Это было известно как гипотеза Стэнли – Уилфа, пока не была доказана Адамом Маркусом и Габором Тардосом . [16]
Закрытые классы
Замкнутый класс , также известный как класс рисунка , класс перестановок , или просто класс перестановок является Downset в порядке перестановки шаблона. Каждый класс может быть определен минимальными перестановками, которые не лежат внутри него, его основы . Таким образом, базис для перестановок, сортируемых по стеку, равен {231}, а базис для перестановок, сортируемых по стеку, бесконечен. Производящая функция для класса Σ х | π | где сумма берется по всем перестановкам π в классе.
Функция Мёбиуса
Поскольку набор перестановок в соответствии с порядком включения образует элементарный набор, естественно спросить о его функции Мёбиуса , цель, впервые явно указанная Вилфом (2002) . [17] Цель таких исследований - найти формулу для функции Мёбиуса интервала [σ, π] в шаблоне перестановки poset, которая более эффективна, чем наивное рекурсивное определение. Первый такой результат был установлен Саганом и Ваттером (2006) , которые дали формулу для функции Мебиуса интервала слоистых перестановок . [18] Позже Бурштейн и др. (2011) обобщили этот результат на интервалы разделимых перестановок . [19]
Известно, что асимптотически не менее 39,95% всех перестановок π длины n удовлетворяют условию μ (1, π) = 0 (то есть главная функция Мёбиуса равна нулю) [20], но для каждого n существуют перестановки π такие, что μ (1, π) является экспоненциальной функцией от n . [21]
Вычислительная сложность
Учитывая перестановку (называемый текстом ) длины и еще одна перестановка длины (называется шаблоном ), проблема сопоставления с образцом перестановки (PPM) спрашивает, есть ли содержится в . Когда оба а также рассматриваются как переменные, известно, что задача является NP-полной , а задача подсчета количества таких совпадений является # P-полной . [22] Однако PPM может быть решен за линейное время, когда k является константой. Действительно, Guillemot и Marx [23] показали, что PPM можно решить за время., что означает, что он является управляемым с фиксированными параметрами по отношению к.
Согласно обзору Брунера и Лакнера, существует несколько вариантов проблемы PPM. [24] Например, если требуется, чтобы совпадение состояло из смежных элементов, проблема может быть решена за полиномиальное время. [25]
Другой вариант - когда и шаблон, и текст ограничены правильным классом перестановки. , в этом случае проблема называется -PPM. Например, Гийемо и Виалетт [26] показали, что-PPM может быть решена в время. Альберт , Лакнер, Лакнер и Ваттер [27] позже понизили это значение дои показал, что такая же оценка верна для класса косо-слитных перестановок . Они также спросили, есть ли-Проблема PPM может быть решена за полиномиальное время для каждого фиксированного надлежащего класса перестановки .
Плотность упаковки
Перестановка π называется β- оптимальной, если никакая перестановка той же длины, что и π, не имеет большего количества копий β. В своем выступлении на собрании SIAM по дискретной математике в 1992 году Уилф определил плотность упаковки перестановки β длины k как
Неопубликованные аргументы Фреда Гэлвина показывают, что величина внутри этого предела не возрастает при n ≥ k , и поэтому предел существует. Когда β является монотонным, его плотность упаковки, очевидно, равна 1, и плотности упаковки инвариантны относительно группы симметрий, порождаемых обратной и обратной, поэтому для перестановок длины три существует только одна нетривиальная плотность упаковки. Уолтер Стромквист (неопубликованный) разрешил этот случай, показав, что плотность упаковки 132 составляет 2 √ 3 - 3, приблизительно 0,46410.
Для перестановок β длины четыре необходимо рассмотреть (из-за симметрии) семь случаев:
β | плотность упаковки | Справка |
---|---|---|
1234 | 1 | банальный |
1432 | корень x 3 - 12 x 2 + 156 x - 64 ≅ 0,42357 | Прайс (1997) [28] |
2143 | ⅜ = 0,375 | Прайс (1997) [28] |
1243 | ⅜ = 0,375 | Альберт и др. (2002) [29] |
1324 | предполагается, что ≅ 0,244 | |
1342 | предполагается, что это 0,19658 фунтов стерлингов | |
2413 | предположительно равняется 0,10474 ≅ |
Для трех неизвестных перестановок существуют оценки и предположения. Прайс (1997) использовал алгоритм аппроксимации, который предполагает, что плотность упаковки 1324 составляет около 0,244. [28] Биржан Баткеев (неопубликовано) построил семейство перестановок, показывающих, что плотность упаковки 1342, по крайней мере, является произведением плотностей упаковки 132 и 1432, приблизительно 0,19658. Предполагается, что это точная плотность упаковки 1342. Presutti & Stromquist (2010) предоставили нижнюю границу плотности упаковки 2413. Эта нижняя граница, которую можно выразить через интеграл, составляет приблизительно 0,10474, и предполагалось, что - истинная плотность упаковки. [30]
Суперпаттерны
К - superpattern перестановка , которая содержит все перестановки длины к . Например, 25314 - это 3-суперпаттерн, потому что он содержит все 6 перестановок длины 3. Известно, что k -суперпаттерны должны иметь длину не менее k 2 / e 2 , где e ≈ 2,71828 - число Эйлера , [31] и что существуют k -супершаблоны длины ⌈ ( k 2 + 1) / 2⌉. [32] Предполагается, что эта верхняя граница является наилучшей с точностью до членов нижнего порядка. [33]
Обобщения
Есть несколько способов обобщения понятия «паттерн». Например, винкулярный узор - это перестановка, содержащая дефисы, обозначающие записи, которые не обязательно должны встречаться последовательно (в обычном определении шаблона, никакие записи не должны появляться последовательно). Например, перестановка 314265 имеет две копии штрихового образца 2-31-4, заданных записями 3426 и 3425. Для штрихового образца β и любой перестановки π мы пишем β (π) для количества копий β. в π. Таким образом, количество инверсий в π равно 2-1 (π), а количество спусков - 21 (π). Далее, количество впадин в π составляет 213 (π) + 312 (π), а количество пиков составляет 231 (π) + 132 (π). Эти закономерности были введены Бабсоном и Штейнгримссоном (2000) , которые показали, что почти вся известная статистика Махона может быть выражена в терминах винкулярных перестановок. [34] Например, основной индекс π равен 1-32 (π) + 2-31 (π) + 3-21 (π) + 21 (π).
Другое обобщение - это модель с полосой , в которой некоторые входы запрещены. Для π, чтобы избежать шаблона с перемычкой, β означает, что каждый набор записей π, которые образуют копию записей без перемычек β, может быть расширен, чтобы сформировать копию всех записей β. Уэст (1993) ввел эти типы паттернов в свое исследование перестановок, которые можно было отсортировать, дважды пропустив их через стек. [35] (Обратите внимание, что определение Уэста сортировки дважды по стеку не то же самое, что сортировка с двумя последовательными стопками.) Другой пример шаблонов с перемычками встречается в работе Bousquet-Mélou & Butler (2007) , которые показали, что Многообразие Шуберта, соответствующее π, является локально факториальным тогда и только тогда, когда π избегает 1324 и 21 3 54. [36]
Рекомендации
- ^ Мак-Магон, Перси А. (1915), комбинаторный анализ , Лондон: Cambridge University Press, том I, раздел III, глава V.
- ↑ MacMahon (1915) , пункты 97 и 98.
- ^ Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Эддисон-Уэсли, ISBN 0-201-89683-4, Руководство по ремонту 0286317 , OCLC 155842391..
- ↑ Knuth (1968) , раздел 2.2.1, упражнения 4 и 5.
- ^ Knuth (1968) , раздел 2.2.1, упражнение 13, в первом издании получил рейтинг M49, а во втором - M48.
- ^ Тарьян, Роберт (1972), "сортировка с использованием сетей очередей и стеков", Журнал ACM , 19 (2): 341-346, DOI : 10,1145 / 321694,321704 , MR 0298803 , S2CID 13608929.
- ^ а б Пратт, Воан Р. (1973), "Вычисление перестановок с двусторонними очередями. Параллельные стеки и параллельные очереди", Proc. Пятый ежегодный ACM симпозиум по теории вычислений (Остин, штат Техас, 1973) . С. 268-277,. Дои : 10,1145 / 800125,804058 , MR 0489115 , S2CID 15740957.
- ^ Розенштиль, Пьер ; Тарьян, Роберт (1984), «Коды Гаусса, плоские гамильтоновы графы и перестановки, сортируемые по стеку», Журнал алгоритмов , 5 (3): 375–390, DOI : 10.1016 / 0196-6774 (84) 90018-X , MR 0756164.
- ^ Симион, Родика ; Шмидт, Фрэнк В. (1985), "Restricted перестановок", Европейский журнал комбинаторика , 6 (4): 383-406, DOI : 10.1016 / s0195-6698 (85) 80052-4 , MR 0829358.
- ^ Клаэссон, Андерс; Китаев, Сергей (2008), «Классификация биекций между 321- и 132-избегающими перестановками» (PDF) , Séminaire Lotharingien de Combinatoire , 60 : B60d, arXiv : 0805.1325 , Bibcode : 2008arXiv0805.1325C , MR 2465405.
- ^ Станково, Звезделин (1994), "Запрещенные подпоследовательности", дискретная математика , 132 (1-3): 291-316, DOI : 10.1016 / 0012-365X (94) 90242-9 , МР 1297387.
- ^ Станкова, Звезделина; Уэст, Джулиан (2002), «Новый класс перестановок, эквивалентных Уилфу», Журнал алгебраической комбинаторики , 15 (3): 271–290, arXiv : math / 0103152 , doi : 10.1023 / A: 1015016625432 , MR 1900628 , S2CID 13921676.
- ^ Бакелин, Йорген; Уэст, Джулиан; Синь, Guoce (2007), "Уилф-эквивалентность для одноэлементных классов", Прогресс в области прикладной математики , 38 (2): 133-149, DOI : 10.1016 / j.aam.2004.11.006 , МР 2290807.
- ^ Бона, Миклош (1997), "Точное перечисление 1342-избегающих перестановок: тесная связь с помеченными деревьями и планарными картами", Журнал комбинаторной теории , серия A, 80 (2): 257–272, arXiv : math / 9702223 , Bibcode : 1997math ...... 2223B , DOI : 10,1006 / jcta.1997.2800 , МР 1485138 , S2CID 18352890.
- ^ Гессель, Ира М. (1990), «Симметричные функции и P- рекурсивность», Журнал комбинаторной теории , серия A, 53 (2): 257–285, DOI : 10.1016 / 0097-3165 (90) 90060-A , MR 1041448.
- ^ Маркус, Адам; Тардос, Габор (2004), "Исключенные матрицы перестановок и Стенли-Уилф гипотеза", Журнал комбинаторной теории , Series A, 107 (1): 153-160, DOI : 10.1016 / j.jcta.2004.04.002 , МР 2063960.
- ^ Уилф, Герберт (2002), "Модель перестановок", дискретная математика , 257 (2): 575-583, DOI : 10.1016 / S0012-365X (02) 00515-0 , МР 1935750.
- ^ Саган, Брюс ; Ваттер, Винс (2006), "Функция Мёбиуса композиционного набора", Журнал алгебраической комбинаторики , 24 (2): 117–136, arXiv : math / 0507485 , doi : 10.1007 / s10801-006-0017-4 , MR 2259013 , S2CID 11283347.
- ^ Бурштейн, Александр; Елинек, Вит; Желинкова, Ева; Steingrimsson, Эйнар (2011), "Функция Мёбиуса разборных и разлагаемых перестановок", Журнал комбинаторной теории , Series A, 118 (1): 2346-2364, DOI : 10.1016 / j.jcta.2011.06.002 , МР 2834180 , S2CID 13978488.
- ^ Бриньялл, Роберт; Елинек, Вит; Кинчл, Ян; Марчант, Дэвид (2019), «Нули функции Мёбиуса перестановок» (PDF) , Mathematika , 65 (4): 1074–1092, DOI : 10.1112 / S0025579319000251 , MR 3992365 , S2CID 53366318
- ^ Марчант, Дэвид (2020), «2413-баллонные перестановки и рост функции Мебиуса», Электронный журнал комбинаторики , 27 (1): P1.7, doi : 10.37236 / 8554
- ^ Бозе, Просенджит ; Басс, Джонатан Ф .; Lubiw, Анна (март 1998), "соответствие шаблона для перестановок", Information Processing Letters , 65 (5): 277-283, DOI : 10.1016 / S0020-0190 (97) 00209-3
- ^ Гиймо, Сильвен; Маркс, Даниил (2014). «Нахождение небольших закономерностей в перестановках за линейное время». Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 20. arXiv : 1307.3073 . DOI : 10.1137 / 1.9781611973402.7 . ISBN 978-1-61197-338-9. S2CID 1846959 .
- ^ Брунер, Мария-Луиза; Лакнер, Мартин (2013), «Вычислительный ландшафт шаблонов перестановок», Чистая математика и приложения , 24 (2): 83–101, arXiv : 1301.0340 , Bibcode : 2013arXiv1301.0340B
- ^ Кубица, М .; Kulczyński, T .; Radoszewski, J .; Rytter, W .; Вален, Т. (2013), «Алгоритм с линейным временем для последовательного сопоставления с образцом перестановок», Письма об обработке информации , 113 (12): 430–433, DOI : 10.1016 / j.ipl.2013.03.015
- ^ Гиймо, Сильвен; Виалетт, Стефан (2009), «Сопоставление с образцом для 321-избегающих перестановок», Алгоритмы и вычисления , Примечания к лекциям по информатике, 5878 , стр. 1064–1073, arXiv : 1511.01770 , doi : 10.1007 / 978-3-642-10631 -6_107
- ^ Альберт, Майкл ; Лакнер, Мария-Луиза; Лакнер, Мартин; Ваттер, Винсент (2016), «Сложность сопоставления с образцом для перестановок, избегающих 321 и перекоса-слияния», Дискретная математика и теоретическая информатика , 18 (2), arXiv : 1510.06051 , Bibcode : 2015arXiv151006051A
- ^ а б в Прайс, Алкес (1997), Плотность упаковки многослойных узоров , доктор философии. докторская диссертация, Пенсильванский университет.
- ^ Альберт, Майкл Х .; Аткинсон, доктор медицины; Handley, CC; Holton, DA; Stromquist, W. (2002), "О плотности упаковки перестановок" , Электронный журнал комбинаторике , 9 : научная статья 5, 20 стр, DOI : 10,37236 / 1622 , MR 1887086.
- ^ Пресутти, Кэтлин Баттист; Стромквист, Уолтер (2010), «Степень упаковки мер и гипотеза для плотности упаковки 2413», Линтон, Стив; Рушкуц, Ник; Ваттер, Винсент (ред.), Шаблоны перестановок , London Math. Soc. Lecture Notes, 376 ., Cambridge University Press, стр 287-316, DOI : 10,1017 / CBO9780511902499.015.
- ^ Аррат, Ричард (1999), «О гипотезе Стенли-Уилфе для числа перестановок , избегая заданный шаблон» , Электронный журнал Комбинаторики , 6 : N1, DOI : 10,37236 / 1477 , МР 1710623.
- ^ Энген, Майкл; Vatter, Винсент (2021), "Содержит все перестановки", American Mathematical Monthly , 128 (1): 4-24, DOI : 10,1080 / 00029890.2021.1835384
- ^ Эрикссон, Хенрик; Эрикссон, Киммо; Линюссон, Сванте; Wästlund, Йохан (2007), "плотная упаковка узоры в перестановке", Анналы Комбинаторика , 11 (3-4): 459-470, DOI : 10.1007 / s00026-007-0329-7 , МР 2376116 , S2CID 2021533.
- ^ Бэбсон, Эрик; Steingrímsson, Einar (2000), "Обобщенные модели перестановок и классификация статистики Махонии" , Séminaire Lotharingien de Combinatoire , 44 : Исследовательская статья B44b, 18 стр., MR 1758852.
- ^ Уэст, Джулиан (1993), «Сортировка дважды в стеке», Теоретическая информатика , 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 г., Университет Флоренции , Флоренция, Италия.
- Паттерны перестановки 2010 г. , 9–13 августа 2010 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
- Шаблоны перестановок 2011 г. , 20–24 июня 2011 г., Калифорнийский политехнический государственный университет , Сан-Луис-Обиспо, Калифорния, США.
- Паттерны перестановки 2012 г. , 11–15 июня 2012 г., Стратклайдский университет , Глазго, Шотландия.
- Шаблоны перестановок 2013 , 1–5 июля 2013 г., Парижский университет Дидро , Париж, Франция.
- Шаблоны перестановок 2014 г. , 7–11 июля 2014 г., Государственный университет Восточного Теннесси , Джонсон-Сити, Теннесси, США.
- Паттерны перестановки 2015 г. , 15–19 июня 2015 г., De Morgan House , Лондон, Англия.
- Паттерны перестановки 2016 г. , 27 июня - 1 июля 2016 г., Университет Говарда , Вашингтон, округ Колумбия, США.
- Шаблоны перестановок 2017 г. , 26–30 июня 2017 г., Рейкьявикский университет , Рейкьявик, Исландия.
- Шаблоны перестановок 2018 , 9–13 июля 2018 г., Дартмутский колледж , Ганновер, Нью-Гэмпшир, США.
- Шаблоны перестановок 2019 , 17–21 июня 2019 г., Университет Цюриха , Цюрих, Швейцария.
- Виртуальный семинар по шаблонам перестановок 2020 , 30 июня - 1 июля 2020 г., организованный Университетом Вальпараисо, Вальпараисо, Индиана, США.
- Виртуальный семинар по шаблонам перестановок 2021 , 15–16 июня 2021 г., организованный Университетом Стратклайда , Глазго, Шотландия.
Специальные сессии Американского математического общества по шаблонам в перестановках проводились на следующих собраниях:
- Осеннее собрание Восточной секции , 22–23 сентября 2012 г., Рочестерский технологический институт , Рочестер, штат Нью-Йорк.
- Совместные встречи по математике , 12 января 2013 г., Сан-Диего, Калифорния.
- Секционное собрание Central Fall , 20–21 сентября 2014 г., Университет Висконсина - О-Клэр , О-Клэр, Висконсин.
- Весеннее восточное секционное собрание , 7–8 марта 2015 г., Джорджтаунский университет , Вашингтон, округ Колумбия.
Встречи с другими шаблонами перестановки:
- Семинар по шаблонам перестановок , 29 мая - 3 июня 2005 г., Хайфский университет , Хайфа, Израиль.
Другие ссылки:
- PermLab: программное обеспечение для шаблонов перестановок , поддерживаемое Майклом Альбертом .
- База данных избегания шаблонов перестановок , поддерживаемая Бриджит Теннер.