Перечисления конкретных классов перестановок - Enumerations of specific permutation classes

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

Классы, избегающие одного шаблона длины 3

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

β	перечисление последовательности Среднийп(β)	OEIS	тип последовательности	ссылка на точное перечисление
123 231	1, 2, 5, 14, 42, 132, 429, 1430, ...	A000108	алгебраический (нерациональный) g.f. Каталонские числа	Мак-Магон (1916) Кнут (1968)

Классы, избегающие одного шаблона длины 4

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

β	перечисление последовательности Среднийп(β)	OEIS	тип последовательности	ссылка на точное перечисление
1342 2413	1, 2, 6, 23, 103, 512, 2740, 15485, ...	A022558	алгебраический (нерациональный) g.f.	Бона (1997)
1234 1243 1432 2143	1, 2, 6, 23, 103, 513, 2761, 15767, ...	A005802	голономный (неалгебраический) g.f.	Гессель (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, ...	A061552

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

Классы, избегающие двух шаблонов длины 3

Существует пять классов симметрии и три класса Вильфа, все из которых перечислены в Симион и Шмидт (1985).

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	рациональный g.f., ${\displaystyle 2^{n-1}}$

Классы, избегающие одного шаблона длины 3 и одного шаблона длины 4

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

B	перечисление последовательности Среднийп(В)	OEIS	тип последовательности
321, 1234	1, 2, 5, 13, 25, 25, 0, 0, ...	н / д	конечный
321, 2134	1, 2, 5, 13, 30, 61, 112, 190, ...	A116699	многочлен
132, 4321	1, 2, 5, 13, 31, 66, 127, 225, ...	A116701	многочлен
321, 1324	1, 2, 5, 13, 32, 72, 148, 281, ...	A179257	многочлен
321, 1342	1, 2, 5, 13, 32, 74, 163, 347, ...	A116702	рациональный g.f.
321, 2143	1, 2, 5, 13, 33, 80, 185, 411, ...	A088921	рациональный g.f.
132, 4312 132, 4231	1, 2, 5, 13, 33, 81, 193, 449, ...	A005183	рациональный g.f.
132, 3214	1, 2, 5, 13, 33, 82, 202, 497, ...	A116703	рациональный g.f.
321, 2341 321, 3412 321, 3142 132, 1234 132, 4213 132, 4123 132, 3124 132, 2134 132, 3412	1, 2, 5, 13, 34, 89, 233, 610, ...	A001519	рациональный g.f., чередовать Числа Фибоначчи

Классы без двух шаблонов длины 4

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

B	перечисление последовательности Среднийп(В)	OEIS	тип последовательности	ссылка на точное перечисление	кодировка вставки обычная
4321, 1234	1, 2, 6, 22, 86, 306, 882, 1764, ...	A206736	конечный	Теорема Эрдеша – Секереса	✔
4312, 1234	1, 2, 6, 22, 86, 321, 1085, 3266, ...	A116705	многочлен	Кремер и Шиу (2003)	✔
4321, 3124	1, 2, 6, 22, 86, 330, 1198, 4087, ...	A116708	рациональный g.f.	Кремер и Шиу (2003)	✔
4312, 2134	1, 2, 6, 22, 86, 330, 1206, 4174, ...	A116706	рациональный g.f.	Кремер и Шиу (2003)	✔
4321, 1324	1, 2, 6, 22, 86, 332, 1217, 4140, ...	A165524	многочлен	Ваттер (2012)	✔
4321, 2143	1, 2, 6, 22, 86, 333, 1235, 4339, ...	A165525	рациональный g.f.	Альберт, Аткинсон и Бриньял (2012)
4312, 1324	1, 2, 6, 22, 86, 335, 1266, 4598, ...	A165526	рациональный g.f.	Альберт, Аткинсон и Бриньял (2012)
4231, 2143	1, 2, 6, 22, 86, 335, 1271, 4680, ...	A165527	рациональный g.f.	Альберт, Аткинсон и Бриньялл (2011)
4231, 1324	1, 2, 6, 22, 86, 336, 1282, 4758, ...	A165528	рациональный g.f.	Альберт, Аткинсон и Ваттер (2009)
4213, 2341	1, 2, 6, 22, 86, 336, 1290, 4870, ...	A116709	рациональный g.f.	Кремер и Шиу (2003)	✔
4312, 2143	1, 2, 6, 22, 86, 337, 1295, 4854, ...	A165529	рациональный g.f.	Альберт, Аткинсон и Бриньялл (2012)
4213, 1243	1, 2, 6, 22, 86, 337, 1299, 4910, ...	A116710	рациональный g.f.	Кремер и Шиу (2003)	✔
4321, 3142	1, 2, 6, 22, 86, 338, 1314, 5046, ...	A165530	рациональный g.f.	Ваттер (2012)	✔
4213, 1342	1, 2, 6, 22, 86, 338, 1318, 5106, ...	A116707	рациональный g.f.	Кремер и Шиу (2003)	✔
4312, 2341	1, 2, 6, 22, 86, 338, 1318, 5110, ...	A116704	рациональный g.f.	Кремер и Шиу (2003)	✔
3412, 2143	1, 2, 6, 22, 86, 340, 1340, 5254, ...	A029759	алгебраический (нерациональный) g.f.	Аткинсон (1998)
4321, 4123 4321, 3412 4123, 3214 4123, 2143	1, 2, 6, 22, 86, 342, 1366, 5462, ...	A047849	рациональный g.f.	Кремер и Шиу (2003)	Верно для первых трех
4123, 2341	1, 2, 6, 22, 87, 348, 1374, 5335, ...	A165531	алгебраический (нерациональный) g.f.	Аткинсон, Саган и Ваттер (2012)
4231, 3214	1, 2, 6, 22, 87, 352, 1428, 5768, ...	A165532	алгебраический (нерациональный) g.f.	Шахтер (2016)
4213, 1432	1, 2, 6, 22, 87, 352, 1434, 5861, ...	A165533	алгебраический (нерациональный) g.f.	Шахтер (2016)
4312, 3421 4213, 2431	1, 2, 6, 22, 87, 354, 1459, 6056, ...	A164651	алгебраический (нерациональный) g.f.	Ле (2005) установил Wilf-эквивалентность; Каллан (2013a) определили перечисление.
4312, 3124	1, 2, 6, 22, 88, 363, 1507, 6241, ...	A165534	алгебраический (нерациональный) g.f.	Pantone (2017)
4231, 3124	1, 2, 6, 22, 88, 363, 1508, 6255, ...	A165535	алгебраический (нерациональный) g.f.	Альберт, Аткинсон и Ваттер (2014)
4312, 3214	1, 2, 6, 22, 88, 365, 1540, 6568, ...	A165536	алгебраический (нерациональный) g.f.	Шахтер (2016)
4231, 3412 4231, 3142 4213, 3241 4213, 3124 4213, 2314	1, 2, 6, 22, 88, 366, 1552, 6652, ...	A032351	алгебраический (нерациональный) g.f.	Бона (1998)
4213, 2143	1, 2, 6, 22, 88, 366, 1556, 6720, ...	A165537	алгебраический (нерациональный) g.f.	Беван (2016b)
4312, 3142	1, 2, 6, 22, 88, 367, 1568, 6810, ...	A165538	алгебраический (нерациональный) g.f.	Альберт, Аткинсон и Ваттер (2014)
4213, 3421	1, 2, 6, 22, 88, 367, 1571, 6861, ...	A165539	алгебраический (нерациональный) g.f.	Беван (2016a)
4213, 3412 4123, 3142	1, 2, 6, 22, 88, 368, 1584, 6968, ...	A109033	алгебраический (нерациональный) g.f.	Ле (2005)
4321, 3214	1, 2, 6, 22, 89, 376, 1611, 6901, ...	A165540	алгебраический (нерациональный) g.f.	Беван (2016a)
4213, 3142	1, 2, 6, 22, 89, 379, 1664, 7460, ...	A165541	алгебраический (нерациональный) g.f.	Альберт, Аткинсон и Ваттер (2014)
4231, 4123	1, 2, 6, 22, 89, 380, 1677, 7566, ...	A165542	предполагается, что не удовлетворяет ни один ADE, видеть Альберт и др. (2018)
4321, 4213	1, 2, 6, 22, 89, 380, 1678, 7584, ...	A165543	алгебраический (нерациональный) g.f.	Каллан (2013b); смотрите также Блум и Ваттер (2016)
4123, 3412	1, 2, 6, 22, 89, 381, 1696, 7781, ...	A165544	алгебраический (нерациональный) g.f.	Шахтер и Pantone (2018)
4312, 4123	1, 2, 6, 22, 89, 382, 1711, 7922, ...	A165545	предполагается, что не удовлетворяет ни один ADE, видеть Альберт и др. (2018)
4321, 4312 4312, 4231 4312, 4213 4312, 3412 4231, 4213 4213, 4132 4213, 4123 4213, 2413 4213, 3214 3142, 2413	1, 2, 6, 22, 90, 394, 1806, 8558, ...	A006318	Числа Шредера алгебраический (нерациональный) g.f.	Кремер (2000), Кремер (2003)
3412, 2413	1, 2, 6, 22, 90, 395, 1823, 8741, ...	A165546	алгебраический (нерациональный) g.f.	Шахтер и Pantone (2018)
4321, 4231	1, 2, 6, 22, 90, 396, 1837, 8864, ...	A053617	предполагается, что не удовлетворяет ни один ADE, видеть Альберт и др. (2018)

внешняя ссылка

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

Смотрите также

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

Рекомендации

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