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

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

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

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

б	последовательность, перечисляющая Av _n (β)	ОЭИС	тип последовательности	точная ссылка на перечисление
123 231	1, 2, 5, 14, 42, 132, 429, 1430, ...	А000108	алгебраический (нерациональный) gf Каталонские цифры	МакМахон (1916) Кнут (1968)

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

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

б	последовательность, перечисляющая Av _n (β)	ОЭИС	тип последовательности	точная ссылка на перечисление
1342 2413	1, 2, 6, 23, 103, 512, 2740, 15485, ...	А022558	алгебраический (нерациональный) gf	Бона (1997)
1234 1243 1432 2143	1, 2, 6, 23, 103, 513, 2761, 15767, ...	А005802	голономный (неалгебраический) gf	Гессель (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, ...	А061552

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

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

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

Б	последовательность, перечисляющая Av _n (B)	ОЭИС	тип последовательности
123, 321	1, 2, 4, 4, 0, 0, 0, 0, ...	н/д	конечный
213, 321	1, 2, 4, 7, 11, 16, 22, 29, ...	А000124	полином, ${n \choose 2}+1$
231, 321 132, 312 231, 312	1, 2, 4, 8, 16, 32, 64, 128, ...	А000079	рациональная подруга , $2^{n-1}$

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

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

Б	последовательность, перечисляющая Av _n (B)	ОЭИС	тип последовательности
321, 1234	1, 2, 5, 13, 25, 25, 0, 0, ...	н/д	конечный
321, 2134	1, 2, 5, 13, 30, 61, 112, 190, ...	А116699	полиномиальный
132, 4321	1, 2, 5, 13, 31, 66, 127, 225, ...	А116701	полиномиальный
321, 1324	1, 2, 5, 13, 32, 72, 148, 281, ...	А179257	полиномиальный
321, 1342	1, 2, 5, 13, 32, 74, 163, 347, ...	А116702	рациональная подруга
321, 2143	1, 2, 5, 13, 33, 80, 185, 411, ...	А088921	рациональная подруга
132, 4312 132, 4231	1, 2, 5, 13, 33, 81, 193, 449, ...	А005183	рациональная подруга
132, 3214	1, 2, 5, 13, 33, 82, 202, 497, ...	А116703	рациональная подруга
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, ...	А001519	рациональная подруга , альтернативные числа Фибоначчи

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

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

Справа показаны тепловые карты каждого из неконечных классов. Для каждого класса используется лексикографически минимальная симметрия, классы упорядочиваются в лексикографическом порядке. Для создания каждой тепловой карты из класса равномерно случайным образом выбирался один миллион перестановок длиной 300. Цвет точки $(i,j)$ представляет, сколько перестановок имеют значение $j$ по индексу $i$ . Версии с более высоким разрешением можно получить на PermPal.

Б	последовательность, перечисляющая Av _n (B)	ОЭИС	тип последовательности	точная ссылка на перечисление
4321, 1234	1, 2, 6, 22, 86, 306, 882, 1764, ...	А206736	конечный	Теорема Эрдеша – Секереша
4312, 1234	1, 2, 6, 22, 86, 321, 1085, 3266, ...	А116705	полиномиальный	Кремер и Шиу (2003)
4321, 3124	1, 2, 6, 22, 86, 330, 1198, 4087, ...	А116708	рациональная подруга	Кремер и Шиу (2003)
4312, 2134	1, 2, 6, 22, 86, 330, 1206, 4174, ...	А116706	рациональная подруга	Кремер и Шиу (2003)
4321, 1324	1, 2, 6, 22, 86, 332, 1217, 4140, ...	А165524	полиномиальный	Отец (2012)
4321, 2143	1, 2, 6, 22, 86, 333, 1235, 4339, ...	А165525	рациональная подруга	Альберт, Аткинсон и Бригналл (2012)
4312, 1324	1, 2, 6, 22, 86, 335, 1266, 4598, ...	А165526	рациональная подруга	Альберт, Аткинсон и Бригналл (2012)
4231, 2143	1, 2, 6, 22, 86, 335, 1271, 4680, ...	А165527	рациональная подруга	Альберт, Аткинсон и Бригналл (2011)
4231, 1324	1, 2, 6, 22, 86, 336, 1282, 4758, ...	А165528	рациональная подруга	Альберт, Аткинсон и Ваттер (2009)
4213, 2341	1, 2, 6, 22, 86, 336, 1290, 4870, ...	А116709	рациональная подруга	Кремер и Шиу (2003)
4312, 2143	1, 2, 6, 22, 86, 337, 1295, 4854, ...	А165529	рациональная подруга	Альберт, Аткинсон и Бригналл (2012)
4213, 1243	1, 2, 6, 22, 86, 337, 1299, 4910, ...	А116710	рациональная подруга	Кремер и Шиу (2003)
4321, 3142	1, 2, 6, 22, 86, 338, 1314, 5046, ...	А165530	рациональная подруга	Отец (2012)
4213, 1342	1, 2, 6, 22, 86, 338, 1318, 5106, ...	А116707	рациональная подруга	Кремер и Шиу (2003)
4312, 2341	1, 2, 6, 22, 86, 338, 1318, 5110, ...	А116704	рациональная подруга	Кремер и Шиу (2003)
3412, 2143	1, 2, 6, 22, 86, 340, 1340, 5254, ...	А029759	алгебраический (нерациональный) gf	Аткинсон (1998)
4321, 4123 4321, 3412 4123, 3214 4123, 2143	1, 2, 6, 22, 86, 342, 1366, 5462, ...	А047849	рациональная подруга	Кремер и Шиу (2003)
4123, 2341	1, 2, 6, 22, 87, 348, 1374, 5335, ...	А165531	алгебраический (нерациональный) gf	Аткинсон, Саган и Ваттер (2012)
4231, 3214	1, 2, 6, 22, 87, 352, 1428, 5768, ...	А165532	алгебраический (нерациональный) gf	Шахтер (2016)
4213, 1432	1, 2, 6, 22, 87, 352, 1434, 5861, ...	А165533	алгебраический (нерациональный) gf	Шахтер (2016)
4312, 3421 4213, 2431	1, 2, 6, 22, 87, 354, 1459, 6056, ...	А164651	алгебраический (нерациональный) gf	Ле (2005) установил эквивалентность Уилфа; Каллан (2013a) определил подсчет.
4312, 3124	1, 2, 6, 22, 88, 363, 1507, 6241, ...	А165534	алгебраический (нерациональный) gf	Пантон (2017)
4231, 3124	1, 2, 6, 22, 88, 363, 1508, 6255, ...	А165535	алгебраический (нерациональный) gf	Альберт, Аткинсон и Ваттер (2014)
4312, 3214	1, 2, 6, 22, 88, 365, 1540, 6568, ...	А165536	алгебраический (нерациональный) gf	Шахтер (2016)
4231, 3412 4231, 3142 4213, 3241 4213, 3124 4213, 2314	1, 2, 6, 22, 88, 366, 1552, 6652, ...	А032351	алгебраический (нерациональный) gf	Бона (1998)
4213, 2143	1, 2, 6, 22, 88, 366, 1556, 6720, ...	А165537	алгебраический (нерациональный) gf	Беван (2016b)
4312, 3142	1, 2, 6, 22, 88, 367, 1568, 6810, ...	А165538	алгебраический (нерациональный) gf	Альберт, Аткинсон и Ваттер (2014)
4213, 3421	1, 2, 6, 22, 88, 367, 1571, 6861, ...	А165539	алгебраический (нерациональный) gf	Беван (2016а)
4213, 3412 4123, 3142	1, 2, 6, 22, 88, 368, 1584, 6968, ...	А109033	алгебраический (нерациональный) gf	(2005)
4321, 3214	1, 2, 6, 22, 89, 376, 1611, 6901, ...	А165540	алгебраический (нерациональный) gf	Беван (2016а)
4213, 3142	1, 2, 6, 22, 89, 379, 1664, 7460, ...	А165541	алгебраический (нерациональный) gf	Альберт, Аткинсон и Ваттер (2014)
4231, 4123	1, 2, 6, 22, 89, 380, 1677, 7566, ...	А165542	предположительно не удовлетворяет никакому ADE , см. Albert et al. (2018)
4321, 4213	1, 2, 6, 22, 89, 380, 1678, 7584, ...	А165543	алгебраический (нерациональный) gf	Каллан (2013b) ; см. также Блум и Ваттер (2016).
4123, 3412	1, 2, 6, 22, 89, 381, 1696, 7781, ...	А165544	алгебраический (нерациональный) gf	Шахтер и Pantone (2018)
4312, 4123	1, 2, 6, 22, 89, 382, 1711, 7922, ...	А165545	предположительно не удовлетворяет никакому ADE , см. Albert et al. (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, ...	А006318	Числа Шредера алгебраический (нерациональный) gf	Кремер (2000) , Кремер (2003)
3412, 2413	1, 2, 6, 22, 90, 395, 1823, 8741, ...	А165546	алгебраический (нерациональный) gf	Шахтер и Pantone (2018)
4321, 4231	1, 2, 6, 22, 90, 396, 1837, 8864, ...	А053617	предположительно не удовлетворяет никакому ADE , см. Albert et al. (2018)

См. также

Ссылки

Альберт, Майкл Х .; Старейшина, Мюррей; Рехницер, Эндрю; Уэсткотт, П.; Заброцки, Майк (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) , Pure Mathematics and Applications , 22 : 87–98, arXiv : 1108.0989 , MR 2924740 .
Альберт, Майкл Х .; Аткинсон, доктор медицины; Бригналл, Роберт (2012), «Перечисление трех классов шаблонов с использованием классов монотонной сетки» , Electronic Journal of Combinatorics , 19 (3): Paper 20, 34 стр., doi : 10.37236/2442 , MR 2967225 .
Альберт, Майкл Х .; Аткинсон, доктор медицины; Ваттер, Винсент (2009), «Подсчет 1324, 4231 — избежание перестановок» , Electronic Journal of Combinatorics , 16 (1): Paper 136, 9 стр., arXiv : 1102.5568 , doi : 10.37236/225 , 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), «Перестановки, которые представляют собой объединение возрастающей и убывающей подпоследовательности» , Электронный журнал комбинаторики , 5 : Статья 6, 13 стр., doi : 10.37236/1344 , MR 1490467 .
Аткинсон, доктор медицинских наук (1999), «Ограниченные перестановки», Discrete Mathematics , 195 (1–3): 27–38, doi : 10.1016/S0012-365X(98)00162-9 , MR 1663866 .
Аткинсон, доктор медицины; Саган, Брюс Э .; Ваттер, Винсент (2012), «Подсчет перестановок, избегающих (3+1)», European Journal of Combinatorics , 33 : 49–61, doi : 10.1016/j.ejc.2011.06.006 , MR 2854630 .
Беван, Дэвид (2015), «Перестановки, избегающие числа 1324, и закономерности в путях Лукасевича», J. London Math. Соц. , 92 (1): 105–122, arXiv : 1406.2890 , doi : 10.1112/jlms/jdv020 , MR 3384507 .
Беван, Дэвид (2016a), «Классы перестановок Av (1234,2341) и Av (1243,2314)» (PDF) , Австралазийский журнал комбинаторики , 64 (1): 3–20, MR 3426209 .
Беван, Дэвид (2016b), «Класс перестановок Av(4213,2143)» , Discrete Mathematics & Theoretical Computer Science , 18 (2): 14 стр., arXiv : 1510.06328 , doi : 10.46298/dmtcs.1309 .
Беван, Дэвид ; Бригналл, Роберт; Элви Прайс, Эндрю; Пантоне, Джей (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 , MR 1485138 .
Бона, Миклош (1998), «Классы перестановок, равноценные гладкому классу» , Электронный журнал комбинаторики , 5 : Статья 31, 12 стр., doi : 10.37236/1369 , MR 1626487 .
Бона, Миклош (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 , Бибкод : 2013arXiv1303.3857C , doi : 10.46298/dmtcs.5287 .
Каллан, Дэвид (2013b), «Перестановки, избегающие 4321 и 3241, имеют алгебраическую производящую функцию», Discrete Mathematics & Theoretical Computer Science , 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-пропагандирующих перестановки», Достижения в прикладной математике , 56 : 20–34, ARXIV : 1309.7117 , doi : 10.1016/j.aam.2014.01.006 , г. 319205 .
Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Аддисон-Уэсли, ISBN 978-0-201-89683-1 , МР 0286317 , OCLC 155842391 .
Кремер, Дарла (2000), «Перестановки с запрещенными подпоследовательностями и обобщенным числом Шредера», Discrete Mathematics , 218 (1–3): 121–130, doi : 10.1016/S0012-365X(99)00302-7 , MR 1754331 .
Кремер, Дарла (2003), «Постскриптум: «Перестановки с запрещенными подпоследовательностями и обобщенным числом Шредера» », Discrete Mathematics , 270 (1–3): 333–334, doi : 10.1016/S0012-365X(03)00124-9 , МР 1997910 .
Кремер, Дарла; Шиу, Вай Чи (2003), «Матрицы конечных переходов для перестановок, избегающих пар шаблонов длины четыре», Discrete Mathematics , 268 (1–3): 171–183, doi : 10.1016/S0012-365X(03)00042-6 , МР 1983276 .
Ле, Ян (2005), «Классы Уилфа пар перестановок длины 4» , Электронный журнал комбинаторики , 12 : Статья 25, 27 стр., doi : 10.37236/1922 , MR 2156679 .
МакМахон, Перси А. (1916), Комбинаторный анализ , Лондон: Издательство Кембриджского университета, 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 .
Пантоне, Джей (2017), «Перечисление перестановок, избегающих 3124 и 4312», Annals of Combinatorics , 21 (2): 293–315, arXiv : 1309.0832 , doi : 10.1007/s00026-017-0352-2 .
Симион, Родика ; Шмидт, Фрэнк В. (1985), «Ограниченные перестановки», European Journal of Combinatorics , 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), «Генерация деревьев и запрещенных подпоследовательностей», Discrete Mathematics , 157 (1–3): 363–374, doi : 10.1016/S0012-365X(96)83023-8 , MR 1417303 .

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

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