Перестановка Бакстера

В комбинаторной математике — перестановка Бакстера это перестановка. $\sigma \in S_{n}$ которое удовлетворяет следующему обобщенному свойству предотвращения шаблонов :

Индексов нет $i<j<k$ такой, что $\sigma (j+1)<\sigma (i)<\sigma (k)<\sigma (j)$ или $\sigma (j)<\sigma (k)<\sigma (i)<\sigma (j+1)$ .

Аналогичным образом, используя обозначение винкулярных паттернов , перестановка Бакстера — это такая перестановка, которая позволяет избежать двух пунктирных паттернов. $2-41-3$ и $3-14-2$ .

Например, перестановка $\sigma =2413$ в $S_{4}$ (записанная в однострочной записи ) не является перестановкой Бакстера, поскольку, приняв $i=1$ , $j=2$ и $k=4$ , эта перестановка нарушает первое условие.

Эти перестановки были введены Гленом Бакстером в контексте математического анализа . ^{[ 1 ]}

Перечисление

Для $n=1,2,3,\ldots$ , число $a_{n}$ перестановок Бакстера длины $n$ является

1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586,...

Это последовательность OEIS : A001181 в OEIS . В общем, $a_{n}$ имеет следующую формулу:

a_{n}\,=\,\sum _{k=1}^{n}{\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}.

^{[ 2 ]}

Фактически эта формула градуирована по числу спусков в перестановках, т. е. существуют ${\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}$ Перестановки Бакстера в $S_{n}$ с $k-1$ спуски. ^{[ 3 ]}

Другие объекты недвижимости

Число чередующихся перестановок Бакстера длины $2n$ является $(C_{n})^{2}$ , квадрат каталонского числа и длины $2n+1$ является

$C_{n}C_{n+1}$ .

Число двукратно чередующихся перестановок Бакстера длины $2n$ и $2n+1$ (т.е. те, для которых оба $\sigma$ и его инверсия $\sigma ^{-1}$ чередуются) — каталонское число $C_{n}$ . ^{[ 4 ]}
Перестановки Бакстера связаны с алгебрами Хопфа , ^{[ 5 ]} плоские графы , ^{[ 6 ]} и плитки . ^{[ 7 ]}^{[ 8 ]}

Мотивация: функции поездок на работу

Бакстер ввел перестановки Бакстера при изучении неподвижных точек коммутирующих непрерывных функций . В частности, если $f$ и $g$ являются непрерывными функциями из интервала $[0,1]$ себе такой, что $f(g(x))=g(f(x))$ для всех $x$ , и $f(g(x))=x$ для конечного числа $x$ в $[0,1]$ , затем:

число этих неподвижных точек нечетно;
если неподвижные точки $x_{1}<x_{2}<\ldots <x_{2k+1}$ затем $f$ и $g$ действуют как взаимно обратные перестановки на

$\{x_{1},x_{3},\ldots ,x_{2k+1}\}$ и $\{x_{2},x_{4},\ldots ,x_{2k}\}$ ;

перестановка, вызванная $f$ на $\{x_{1},x_{3},\ldots ,x_{2k+1}\}$ однозначно определяет перестановку, индуцированную

$f$ на $\{x_{2}<,x_{4},\ldots ,x_{2k}\}$ ;

под естественной перемаркировкой $x_{1}\to 1$ , $x_{3}\to 2$ и т. д., перестановка, индуцированная на $\{1,2,\ldots ,k+1\}$ является перестановкой Бакстера.

См. также

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

Ссылки

^ Бакстер, Глен (1964), «О фиксированных точках композиции коммутирующих функций», Proceedings of the American Mathematical Society , 15 (6): 851–855, doi : 10.2307/2034894 , JSTOR 2034894 .
^ Чанг, Франция ; Грэм, РЛ ; Хоггатт, В.Е. младший ; Клейман, М. (1978), «Число перестановок Бакстера» (PDF) , Журнал комбинаторной теории , серия A, 24 (3): 382–394, doi : 10.1016/0097-3165(78)90068-7 , МР 0491652 .
^ Дюлюк, С.; Гиберт, О. (1998), «Перестановки Бакстера», Discrete Mathematics , 180 (1–3): 143–156, doi : 10.1016/S0012-365X(97)00112-X , MR 1603713 .
^ Гвиберт, Оливье; Линуссон, Сванте (2000), «Дважды чередующиеся перестановки Бакстера являются каталонскими», Discrete Mathematics , 217 (1–3): 157–166, doi : 10.1016/S0012-365X(99)00261-7 , MR 1766265 .
^ Жирудо, Самуэле (2011), «Алгебраические и комбинаторные структуры на перестановках Бакстера», 23-я Международная конференция по формальным степенным рядам и алгебраической комбинаторике (FPSAC 2011) , Дискретная математика. Теор. Вычислить. наук. Учеб., вып. АО, доц. Дискретная математика. Теор. Вычислить. Sci., Нэнси, стр. 387–398, arXiv : 1011.4288 , Bibcode : 2010arXiv1011.4288G , MR 2820726 .
^ Боничон, Николя; Буске-Мелу, Мирей ; Фюзи, Эрик (октябрь 2009 г.), «Перестановки Бакстера и плоские биполярные ориентации», Séminaire Lotharingien de Combinatoire , 61A , Art. B61Ah, 29 стр., arXiv : 0805.4180 , Bibcode : 2008arXiv0805.4180B , MR 2734180 .
^ Корн, М. (2004), Геометрические и алгебраические свойства полимино-разбиений , доктор философии. диссертация, Массачусетский технологический институт .
^ Акерман, Эяль; Бареке, Гилл; Пинтер, Рон Ю. (2006), «Биекция между перестановками и планами этажей и ее приложения», Discrete Applied Mathematics , 154 (12): 1674–1684, doi : 10.1016/j.dam.2006.03.018 , MR 2233287 .

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

Последовательность OEIS A001181 (количество перестановок Бакстера длины n)

[1] Бакстер, Глен (1964), «О фиксированных точках композиции коммутирующих функций», Proceedings of the American Mathematical Society , 15 (6): 851–855, doi : 10.2307/2034894 , JSTOR 2034894 .

[2] Чанг, Франция ; Грэм, РЛ ; Хоггатт, В.Е. младший ; Клейман, М. (1978), «Число перестановок Бакстера» (PDF) , Журнал комбинаторной теории , серия A, 24 (3): 382–394, doi : 10.1016/0097-3165(78)90068-7 , МР 0491652 .

[3] Дюлюк, С.; Гиберт, О. (1998), «Перестановки Бакстера», Discrete Mathematics , 180 (1–3): 143–156, doi : 10.1016/S0012-365X(97)00112-X , MR 1603713 .

[4] Гвиберт, Оливье; Линуссон, Сванте (2000), «Дважды чередующиеся перестановки Бакстера являются каталонскими», Discrete Mathematics , 217 (1–3): 157–166, doi : 10.1016/S0012-365X(99)00261-7 , MR 1766265 .

[5] Жирудо, Самуэле (2011), «Алгебраические и комбинаторные структуры на перестановках Бакстера», 23-я Международная конференция по формальным степенным рядам и алгебраической комбинаторике (FPSAC 2011) , Дискретная математика. Теор. Вычислить. наук. Учеб., вып. АО, доц. Дискретная математика. Теор. Вычислить. Sci., Нэнси, стр. 387–398, arXiv : 1011.4288 , Bibcode : 2010arXiv1011.4288G , MR 2820726 .

[6] Боничон, Николя; Буске-Мелу, Мирей ; Фюзи, Эрик (октябрь 2009 г.), «Перестановки Бакстера и плоские биполярные ориентации», Séminaire Lotharingien de Combinatoire , 61A , Art. B61Ah, 29 стр., arXiv : 0805.4180 , Bibcode : 2008arXiv0805.4180B , MR 2734180 .

[7] Корн, М. (2004), Геометрические и алгебраические свойства полимино-разбиений , доктор философии. диссертация, Массачусетский технологический институт .

[8] Акерман, Эяль; Бареке, Гилл; Пинтер, Рон Ю. (2006), «Биекция между перестановками и планами этажей и ее приложения», Discrete Applied Mathematics , 154 (12): 1674–1684, doi : 10.1016/j.dam.2006.03.018 , MR 2233287 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]