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

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)
13241, 2, 6, 23, 103, 513, 2762, 15793, ...A061552

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

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

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

Bперечисление последовательности Среднийп(В)OEISтип последовательности
123, 3211, 2, 4, 4, 0, 0, 0, 0, ...н / дконечный
213, 3211, 2, 4, 7, 11, 16, 22, 29, ...A000124полином

231, 321
132, 312
231, 312

1, 2, 4, 8, 16, 32, 64, 128, ...A000079рациональный g.f.,

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

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

Bперечисление последовательности Среднийп(В)OEISтип последовательности
321, 12341, 2, 5, 13, 25, 25, 0, 0, ...н / дконечный
321, 21341, 2, 5, 13, 30, 61, 112, 190, ...A116699многочлен
132, 43211, 2, 5, 13, 31, 66, 127, 225, ...A116701многочлен
321, 13241, 2, 5, 13, 32, 72, 148, 281, ...A179257многочлен
321, 13421, 2, 5, 13, 32, 74, 163, 347, ...A116702рациональный g.f.
321, 21431, 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, 32141, 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, 12341, 2, 6, 22, 86, 306, 882, 1764, ...A206736конечныйТеорема Эрдеша – Секереса
4312, 12341, 2, 6, 22, 86, 321, 1085, 3266, ...A116705многочленКремер и Шиу (2003)
4321, 31241, 2, 6, 22, 86, 330, 1198, 4087, ...A116708рациональный g.f.Кремер и Шиу (2003)
4312, 21341, 2, 6, 22, 86, 330, 1206, 4174, ...A116706рациональный g.f.Кремер и Шиу (2003)
4321, 13241, 2, 6, 22, 86, 332, 1217, 4140, ...A165524многочленВаттер (2012)
4321, 21431, 2, 6, 22, 86, 333, 1235, 4339, ...A165525рациональный g.f.Альберт, Аткинсон и Бриньял (2012)
4312, 13241, 2, 6, 22, 86, 335, 1266, 4598, ...A165526рациональный g.f.Альберт, Аткинсон и Бриньял (2012)
4231, 21431, 2, 6, 22, 86, 335, 1271, 4680, ...A165527рациональный g.f.Альберт, Аткинсон и Бриньялл (2011)
4231, 13241, 2, 6, 22, 86, 336, 1282, 4758, ...A165528рациональный g.f.Альберт, Аткинсон и Ваттер (2009)
4213, 23411, 2, 6, 22, 86, 336, 1290, 4870, ...A116709рациональный g.f.Кремер и Шиу (2003)
4312, 21431, 2, 6, 22, 86, 337, 1295, 4854, ...A165529рациональный g.f.Альберт, Аткинсон и Бриньялл (2012)
4213, 12431, 2, 6, 22, 86, 337, 1299, 4910, ...A116710рациональный g.f.Кремер и Шиу (2003)
4321, 31421, 2, 6, 22, 86, 338, 1314, 5046, ...A165530рациональный g.f.Ваттер (2012)
4213, 13421, 2, 6, 22, 86, 338, 1318, 5106, ...A116707рациональный g.f.Кремер и Шиу (2003)
4312, 23411, 2, 6, 22, 86, 338, 1318, 5110, ...A116704рациональный g.f.Кремер и Шиу (2003)
3412, 21431, 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, 23411, 2, 6, 22, 87, 348, 1374, 5335, ...A165531алгебраический (нерациональный) g.f.Аткинсон, Саган и Ваттер (2012)
4231, 32141, 2, 6, 22, 87, 352, 1428, 5768, ...A165532алгебраический (нерациональный) g.f.Шахтер (2016)
4213, 14321, 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, 31241, 2, 6, 22, 88, 363, 1507, 6241, ...A165534алгебраический (нерациональный) g.f.Pantone (2017)
4231, 31241, 2, 6, 22, 88, 363, 1508, 6255, ...A165535алгебраический (нерациональный) g.f.Альберт, Аткинсон и Ваттер (2014)
4312, 32141, 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, 21431, 2, 6, 22, 88, 366, 1556, 6720, ...A165537алгебраический (нерациональный) g.f.Беван (2016b)
4312, 31421, 2, 6, 22, 88, 367, 1568, 6810, ...A165538алгебраический (нерациональный) g.f.Альберт, Аткинсон и Ваттер (2014)
4213, 34211, 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, 32141, 2, 6, 22, 89, 376, 1611, 6901, ...A165540алгебраический (нерациональный) g.f.Беван (2016a)
4213, 31421, 2, 6, 22, 89, 379, 1664, 7460, ...A165541алгебраический (нерациональный) g.f.Альберт, Аткинсон и Ваттер (2014)
4231, 41231, 2, 6, 22, 89, 380, 1677, 7566, ...A165542предполагается, что не удовлетворяет ни один ADE, видеть Альберт и др. (2018)
4321, 42131, 2, 6, 22, 89, 380, 1678, 7584, ...A165543алгебраический (нерациональный) g.f.Каллан (2013b); смотрите также Блум и Ваттер (2016)
4123, 34121, 2, 6, 22, 89, 381, 1696, 7781, ...A165544алгебраический (нерациональный) g.f.Шахтер и Pantone (2018)
4312, 41231, 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, 24131, 2, 6, 22, 90, 395, 1823, 8741, ...A165546алгебраический (нерациональный) g.f.Шахтер и Pantone (2018)
4321, 42311, 2, 6, 22, 90, 396, 1837, 8864, ...A053617предполагается, что не удовлетворяет ни один ADE, видеть Альберт и др. (2018)

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

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

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

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