В исследовании шаблонов перестановок был значительный интерес к перечислению определенных классов перестановок , особенно тех, у которых относительно мало базисных элементов. Эта область исследований обнаружила неожиданные примеры эквивалентности Вилфа , когда два, казалось бы, не связанных между собой класса перестановок имеют одинаковое количество перестановок каждой длины.
Классы, избегающие одного шаблона длиной 3
Для отдельных перестановок длины три существует два класса симметрии и один класс Вильфа .
Классы, избегающие одного шаблона длиной 4
Для отдельных перестановок длины четыре существует семь классов симметрии и три класса Вильфа.
Неизвестно ни одной нерекурсивной формулы, подсчитывающей 1324 перестановок, избегающих перестановок. Рекурсивная формула была предложена Мариновым и Радойчичем (2003). Более эффективный алгоритм с использованием функциональных уравнений был предложен Йоханссоном и Накамурой (2014), который был улучшен Конвеем и Гуттманном (2015), а затем дополнительно улучшен Конвеем, Гуттманном и Зинн-Джастином (2018), которые привели первые 50 членов перечисления. Беван и др. (2017) предоставили нижние и верхние границы для роста этого класса.
Классы, избегающие двух шаблонов длины 3
Существует пять классов симметрии и три класса Вильфа, все они были перечислены в работе Симиона и Шмидта (1985).
Классы, избегающие одного шаблона длины 3 и одного шаблона длины 4
Существует восемнадцать классов симметрии и девять классов Вильфа, все из которых были перечислены. Для этих результатов см. Atkinson (1999) или West (1996).
Классы, избегающие двух шаблонов длины 4
Тепловые карты классов, избегающих двух шаблонов длины 4.
Существует 56 классов симметрии и 38 классов эквивалентности Вильфа. Только 3 из них остаются неперечисленными, и их производящие функции , как предполагают Альберт и др. (2018), не удовлетворяют никакому алгебраическому дифференциальному уравнению (ADE); в частности, их гипотеза подразумевает, что эти производящие функции не являются D-конечными .
Тепловые карты каждого из неконечных классов показаны справа. Для каждого класса используется лексикографически минимальная симметрия, а классы упорядочены в лексикографическом порядке. Для создания каждой тепловой карты из класса был равномерно случайным образом отобран один миллион перестановок длиной 300. Цвет точки показывает, сколько перестановок имеют значение в индексе . Версии с более высоким разрешением можно получить на PermPal
Альберт, Майкл Х.; Элдер, Мюррей; Рехницер, Эндрю; Уэсткотт, П.; Заброцкий, Майк (2006), «О пределе Стэнли–Уилфа для перестановок, избегающих 4231, и гипотезе Арратии», Advances in Applied Mathematics , 36 (2): 96–105, doi : 10.1016/j.aam.2005.05.007 , hdl : 10453/98769 , MR 2199982.
Альберт, Майкл Х.; Аткинсон, доктор медицины; Бригнелл, Роберт (2011), «Перечисление перестановок, избегающих 2143 и 4231» (PDF) , Чистая математика и приложения , 22 : 87–98, arXiv : 1108.0989 , MR 2924740.
Альберт, Майкл Х.; Аткинсон, доктор медицины; Бригналл, Роберт (2012), «Перечисление трех классов шаблонов с использованием классов монотонной сетки», Electronic Journal of Combinatorics , 19 (3): Paper 20, 34 pp, doi : 10.37236/2442 , MR 2967225.
Альберт, Майкл Х.; Хомбергер, Чейн; Пантоне, Джей; Шар, Натаниэль; Ваттер, Винсент (2018), «Создание перестановок с ограниченными контейнерами», Журнал комбинаторной теории, Серия A , 157 : 205–232, arXiv : 1510.00269 , doi : 10.1016/j.jcta.2018.02.006, MR 3780412.
Аткинсон, МД (1998), «Перестановки, которые являются объединением возрастающей и убывающей подпоследовательности», Электронный журнал комбинаторики , 5 : Статья 6, 13 стр., doi : 10.37236/1344 , MR 1490467.
Аткинсон, МД (1999), «Ограниченные перестановки», Дискретная математика , 195 (1–3): 27–38, doi :10.1016/S0012-365X(98)00162-9, MR 1663866.
Беван, Дэвид (2015), «Перестановки, избегающие 1324, и закономерности в путях Лукасевича», J. London Math. Soc. , 92 (1): 105–122, arXiv : 1406.2890 , doi : 10.1112/jlms/jdv020, MR 3384507.
Беван, Дэвид ; Бригналл, Роберт; Элви Прайс, Эндрю; Пантоне, Джей (2017), Структурная характеристика Av(1324) и новые границы его темпов роста , arXiv : 1711.10325 , Bibcode : 2017arXiv171110325B.
Бона, Миклош (1997), «Точное перечисление перестановок, избегающих 1342: тесная связь с помеченными деревьями и планарными картами», Журнал комбинаторной теории, Серия A , 80 (2): 257–272, arXiv : math/9702223 , doi : 10.1006/jcta.1997.2800, MR 1485138.
Бона, Миклош (2015), «Новый рекорд для 1324-избегающих перестановок», European Journal of Mathematics , 1 (1): 198–206, arXiv : 1404.4033 , doi : 10.1007/s40879-014-0020-6, MR 3386234.
Каллан, Дэвид (2013a), «Число перестановок, избегающих {1243, 2134}», Дискретная математика и теоретическая информатика , arXiv : 1303.3857 , Bibcode : 2013arXiv1303.3857C, doi : 10.46298/dmtcs.5287.
Каллан, Дэвид (2013b), «Перестановки, избегающие 4321 и 3241, имеют алгебраическую производящую функцию», Дискретная математика и теоретическая информатика , arXiv : 1306.3193 , Bibcode : 2013arXiv1306.3193C, doi : 10.46298/dmtcs.5286.
Конвей, Эндрю; Гуттманн, Энтони (2015), «О 1324-избегающих перестановках», Успехи в прикладной математике , 64 : 50–69, doi :10.1016/j.aam.2014.12.004, MR 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 in Applied Mathematics , 56 : 20–34, arXiv : 1309.7117 , doi : 10.1016/j.aam.2014.01.006, MR 3194205.
Кремер, Дарла (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.
Кремер, Дарла; Шиу, Вай Чи (2003), «Конечные матрицы перехода для перестановок, избегающих пар шаблонов длины четыре», Дискретная математика , 268 (1–3): 171–183, doi :10.1016/S0012-365X(03)00042-6, MR 1983276.
Le, Ian (2005), "Классы Вильфа пар перестановок длины 4", Electronic Journal of Combinatorics , 12 : Paper 25, 27 pp, doi : 10.37236/1922 , MR 2156679.
MacMahon, Percy A. (1916), Комбинаторный анализ , Лондон: Cambridge University Press, MR 0141605.
Маринов, Дарко; Радоичич, Радош (2003), «Подсчет 1324 перестановок, избегающих перестановок», Электронный журнал комбинаторики , 9 (2): Статья 13, 9 стр., doi : 10.37236/1685 , MR 2028282.
Майнер, Сэм (2016), Перечисление нескольких классов два на четыре , arXiv : 1610.01908 , Bibcode : 2016arXiv161001908M.
Майнер, Сэм; Пантоне, Джей (2018), Завершение структурного анализа классов перестановок 2x4 , arXiv : 1802.00483 , Bibcode : 2018arXiv180200483M.
Pantone, Jay (2017), «Перечисление перестановок, избегающих 3124 и 4312», Annals of Combinatorics , 21 (2): 293–315, arXiv : 1309.0832 , doi : 10.1007/s00026-017-0352-2.
Vatter, Vincent (2012), «Поиск регулярных кодировок вставки для классов перестановки», Journal of Symbolic Computation , 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.
Внешние ссылки
База данных по избеганию шаблонов перестановок, поддерживаемая Бриджит Теннер , содержит подробную информацию о перечислении многих других классов перестановок с относительно небольшим количеством базисных элементов.
