Перечисления конкретных классов перестановок

При изучении паттернов перестановок проявился значительный интерес к перечислению конкретных классов перестановок , особенно с относительно небольшим количеством базовых элементов. В этой области исследований были обнаружены неожиданные примеры эквивалентности Уилфа , когда два, казалось бы, не связанных между собой класса перестановок имеют одинаковое количество перестановок каждой длины.

Классы, избегающие одного шаблона длины 3 [ править ]

Есть два класса симметрии и один класс Уилфа для одиночных перестановок длины три.

Классы, избегающие одного шаблона длины 4 [ править ]

Существует семь классов симметрии и три класса Уилфа для одиночных перестановок длины четыре.

Не рекурсивная формула, учитывающая 1324 перестановок, избегающих перестановок, не известна. Рекурсивная формула была дана Мариновым и Радойчичем (2003) . Более эффективный алгоритм, использующий функциональные уравнения, был предложен Йоханссоном и Накамурой (2014) , который был усовершенствован Конвеем и Гуттманном (2015) , а затем дополнительно усовершенствован Конвеем, Гуттманном и Зинн-Джастином (2018), которые дали первые 50 членов перечисление.Bevan et al. (2017) предоставили нижнюю и верхнюю границы роста этого класса.

Классы, избегающие двух шаблонов длины 3 [ править ]

Существует пять классов симметрии и три класса Уилфа, и все они перечислены в Simion & Schmidt (1985) .

B	последовательность, перечисляющая Av n (B)	OEIS	тип последовательности
123, 321	1, 2, 4, 4, 0, 0, 0, 0, ...	н / д	конечный
213, 321	1, 2, 4, 7, 11, 16, 22, 29, ...	A000124	полином ${\ displaystyle {n \ choose 2} +1}$
231, 321 132, 312 231, 312	1, 2, 4, 8, 16, 32, 64, 128, ...	A000079	рациональный гс ,${\ Displaystyle 2 ^ {п-1}}$

Классы, избегающие одного шаблона длины 3 и одного шаблона длины 4 [ править ]

Существует восемнадцать классов симметрии и девять классов Уилфа, и все они перечислены. По поводу этих результатов см. Atkinson (1999) или West (1996) .

Классы, избегающие двух шаблонов длины 4 [ править ]

Существует 56 классов симметрии и 38 классов эквивалентности Вильфа. Только 3 из них остаются не пронумерованными, и их производящие функции предположительно не удовлетворяют никакому алгебраическому дифференциальному уравнению (ADE) Альберта и др. (2018) ; в частности, из их гипотезы следует, что эти производящие функции не являются D-конечными .

Внешние ссылки [ править ]

База данных Перестановка Pattern Избежание , поддерживаемом Бриджит Теннер, содержит подробную информацию о перечислении многих других классов перестановок с относительно небольшим числом базисных элементов.

См. Также [ править ]

• Перестановка Бакстера
• Перестановка в случайном порядке

Ссылки [ править ]

• Альберт, Майкл Х .; Старейшина, Мюррей; Речницер, Эндрю; Westcott, P .; Zabrocki, Майк (2006), "О пределе Стенли-Уилф из 4231 избегающих перестановок и гипотезы Арратья", Успехи прикладной математики , 36 (2): 96-105, DOI : 10.1016 / j.aam.2005.05. 007 , Руководство MR  2199982.
• Альберт, Майкл Х .; Аткинсон, доктор медицины; Бриньялл, Роберт (2011), «Перечисление перестановок, избегающих 2143 и 4231» (PDF) , Чистая математика и приложения , 22 : 87–98, MR  2924740.
• Альберт, Майкл Х .; Аткинсон, доктор медицины; Бриньял, Роберт (2012), «Перечисление трех классов шаблонов с использованием классов монотонной сетки» , Electronic Journal of Combinatorics , 19 (3): Paper 20, 34 pp, MR  2967225.
• Альберт, Майкл Х .; Аткинсон, доктор медицины; Ваттер, Винсент (2009), «Подсчет 1324, избегание 4231 перестановок» , Электронный журнал комбинаторики , 16 (1): Paper 136, 9 pp, MR  2577304.
• Альберт, Майкл Х .; Аткинсон, доктор медицины; Ваттер, Винсент (2014), «Раздутие классов геометрической сетки: три тематических исследования» (PDF) , Австралазийский журнал комбинаторики , 58 (1): 27–47, MR  3211768.
• Альберт, Майкл Х .; Хомбергер, Чейн; Пантоне, Джей; Шар, Натаниэль; Ваттер, Винсент (2018), «Генерация перестановок с ограниченными контейнерами», Журнал комбинаторной теории, серия A , 157 : 205–232, arXiv : 1510.00269 , doi : 10.1016 / j.jcta.2018.02.006 , MR  3780412.
• Аткинсон, доктор медицины (1998), «Перестановки, которые представляют собой объединение возрастающей и убывающей подпоследовательности» , Electronic Journal of Combinatorics , 5 : Paper 6, 13 pp, MR  1490467.
• Аткинсон, Мэриленд (1999), «Ограниченные перестановки», Дискретная математика , 195 (1–3): 27–38, DOI : 10.1016 / S0012-365X (98) 00162-9 , MR  1663866.
• Аткинсон, доктор медицины; Саган, Брюс Э .; Ваттер, Винсент (2012), "Подсчет (3 + 1) -avoiding перестановок", Европейский журнал Комбинаторика , 33 : 49-61, DOI : 10.1016 / j.ejc.2011.06.006 , МР  2854630.
• Беван, Дэвид (2015), «Перестановки, избегающие 1324 и закономерности в путях Лукасевича», J. London Math. Soc. , 92 (1): 105-122, Arxiv : 1406,2890 , DOI : 10.1112 / jlms / jdv020 , МР  3384507.
• Беван, Дэвид (2016a), «Классы перестановок Av (1234,2341) и Av (1243,2314)» (PDF) , Австралийский журнал комбинаторики , 64 (1): 3–20, MR  3426209.
• Беван, Дэвид (2016b), «Класс перестановок Av (4213,2143)» , Дискретная математика и теоретическая информатика , 18 (2): 14 стр..
• Беван, Дэвид ; Бриньял, Роберт; Элви Прайс, Эндрю; Пантоне, Джей (2017), Структурная характеристика Av (1324) и новые границы скорости его роста , arXiv : 1711.10325 , Bibcode : 2017arXiv171110325B.
• Блум, Джонатан; Ваттер, Винсент (2016), «Две виньетки о расстановке полных ладей» (PDF) , Австралазийский журнал комбинаторики , 64 (1): 77–87, MR  3426214.
• Бона, Миклош (1997), "Точное перечисление 1342-избегающих перестановок: тесная связь с помеченными деревьями и планарными картами", Журнал комбинаторной теории, серия A , 80 (2): 257–272, arXiv : math / 9702223 , DOI : 10,1006 / jcta.1997.2800 , МР  1485138 CS1 maint: обескураженный параметр ( ссылка ).
• Бона, Миклош (1998), "Классы перестановок, равные гладкому классу" , Электронный журнал комбинаторики , 5 : Paper 31, 12 стр., MR  1626487 CS1 maint: обескураженный параметр ( ссылка ).
• Бона, Миклош (2015), «Новый рекорд для 1324-избегающих перестановок», European Journal of Mathematics , 1 (1): 198–206, arXiv : 1404.4033 , doi : 10.1007 / s40879-014-0020-6 , MR  3386234 CS1 maint: обескураженный параметр ( ссылка ).
• Каллан, Дэвид (2013a), Число 1243, 2134-избегающих перестановок , arXiv : 1303.3857 , Bibcode : 2013arXiv1303.3857C.
• Каллан, Дэвид (2013b), Перестановки, избегающие 4321 и 3241, имеют алгебраическую производящую функцию , arXiv : 1306.3193 , Bibcode : 2013arXiv1306.3193C.
• Конвей, Эндрю; Гуттманн, Энтони (2015), "О 1324-избегая перестановок", Успехи прикладной математики , 64 : 50-69, DOI : 10.1016 / j.aam.2014.12.004 , МР  3300327.
• Конвей, Эндрю; Гуттманн, Энтони; Зинн-Джастин, Пол (2018), « Повторное обращение к предотвращению 1324 перестановок», Достижения в прикладной математике , 96 : 312–333, arXiv : 1709.01248 , doi : 10.1016 / j.aam.2018.01.002.
• Гессель, Ира М. (1990), «Симметричные функции и P-рекурсивность», Журнал комбинаторной теории, серия A , 53 (2): 257–285, DOI : 10.1016 / 0097-3165 (90) 90060-A , MR  1041448.
• Йоханссон, Фредрик; Накамура, Брайан (2014), "Использование функциональных уравнений для перечисления 1324-избегая перестановок", Advances в области прикладной математики , 56 : 20-34, Arxiv : 1309,7117 , DOI : 10.1016 / j.aam.2014.01.006 , МР  3194205.
• Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Эддисон-Уэсли, ISBN 978-0-201-89683-1, Руководство по ремонту  0286317 , OCLC  155842391.
• Кремер, Дарла (2000), «Перестановки с запрещенными подпоследовательностями и обобщенное число Шредера», Дискретная математика , 218 (1–3): 121–130, DOI : 10.1016 / S0012-365X (99) 00302-7 , MR  1754331.
• Кремер, Дарла (2003), «Постскриптум:« Перестановки с запрещенными подпоследовательностями и обобщенное число Шредера » », Дискретная математика , 270 (1–3): 333–334, DOI : 10.1016 / S0012-365X (03) 00124-9 , MR  1997910.
• Кремер, Дарла; Shiu, Вай Ч (2003), "Конечные матрицы перехода для перестановок избегая пар длиной четыре модели", дискретная математика , 268 (1-3): 171-183, DOI : 10.1016 / S0012-365X (03) 00042-6 , Руководство по ремонту  1983276.
• Ле, Ян (2005), "Классы Уилфа пар перестановок длины 4" , Electronic Journal of Combinatorics , 12 : Paper 25, 27 pp, MR  2156679.
• Мак-Магон, Перси А. (1916), комбинаторный анализ , Лондон: Cambridge University Press, MR  0141605.
• Маринов, Дарко; Радойчич, Радош (2003), «Подсчет 1324-избегающих перестановок» , Электронный журнал комбинаторики , 9 (2): Paper 13, 9 pp, MR  2028282.
• Майнер, Сэм (2016), Перечисление нескольких классов два на четыре , arXiv : 1610.01908 , Bibcode : 2016arXiv161001908M.
• Шахтер, Сэм; Pantone, Jay (2018), Завершение структурного анализа классов перестановок 2x4 , arXiv : 1802.00483 , Bibcode : 2018arXiv180200483M.
• Pantone, Джей (2017), "Перечисление перестановок избегая 3124 и 4312", Анналы Комбинаторика , 21 (2): 293-315, Arxiv : 1309,0832 , DOI : 10.1007 / s00026-017-0352-2.
• Симион, Родика ; Шмидт, Фрэнк В. (1985), "Restricted перестановок", Европейский журнал комбинаторика , 6 (4): 383-406, DOI : 10.1016 / s0195-6698 (85) 80052-4 , MR  0829358.
• Ваттер, Винсент (2012), «Поиск регулярных кодировок вставки для классов перестановок», Журнал символических вычислений , 47 (3): 259–265, arXiv : 0911.2683 , doi : 10.1016 / j.jsc.2011.11.002 , MR  2869320.
• Запад, Джулиан (1996), "Генерация дерева и запрещенная подпоследовательность", Дискретная математика , 157 (1-3): 363-374, DOI : 10.1016 / S0012-365X (96) 83023-8 , MR  1417303.