Многоуровневая перестановка

В математике перестановок многослойная перестановка — это перестановка, которая меняет местами смежные блоки элементов. Эквивалентно, это прямая сумма убывающих перестановок. ^[1]

Одной из более ранних работ, устанавливающих значимость слоистых перестановок, была Бона (1999) , которая установила гипотезу Стэнли-Уилфа для классов перестановок, запрещающих слоистые перестановки, прежде чем гипотеза была доказана в более общем плане. ^[2]

Пример

Например, многоуровневые перестановки длиной четыре с перевернутыми блоками, разделенными пробелами, представляют собой восемь перестановок.

1 2 3 4

1 2 43

1 32 4

1 432

21 3 4

21 43

321 4

4321

Характеристика по запрещенным шаблонам

Многослойные перестановки также можно эквивалентно описать как перестановки, которые не содержат шаблонов перестановок 231 или 312. То есть никакие три элемента в перестановке (независимо от того, являются ли они последовательными) не имеют такого же порядка, как любая из этих запрещенных троек.

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

Многоуровневая перестановка чисел из $1$ к $n$ может быть однозначно описана подмножеством чисел из $1$ к $n-1$ это первый элемент в перевернутом блоке. (Число $n$ всегда является первым элементом в своем перевернутом блоке, поэтому для данного описания он избыточен.) Поскольку существуют $2^{n-1}$ подмножества чисел из $1$ к $n-1$ , есть также $2^{n-1}$ многоуровневая перестановка длины $n$ .

Многоуровневые перестановки эквивалентны по Уилфу другим классам перестановок, а это означает, что количество перестановок каждой длины одинаково. Например, перестановки Гилбрита подсчитываются одной и той же функцией $2^{n-1}$ . ^[3]

Суперпаттерны

Самый короткий супершаблон слоистых перестановок длины $n$ сам по себе является многоуровневой перестановкой. Его длина — это номер сортировки , количество сравнений, необходимое для сортировки двоичной вставкой для сортировки. $n+1$ элементы. ^[1]^[4] Для $n=1,2,3,\dots$ эти цифры

1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... (последовательность A001855 в OEIS )

и вообще они задаются формулой

(n+1){\bigl \lceil }\log _{2}(n+1){\bigr \rceil }-2^{\left\lceil \log _{2}(n+1)\right\rceil }+1.

^[1]

Связанные классы перестановок

Каждая многоуровневая перестановка является инволюцией . Это в точности инволюции, избегающие 231, а также инволюции, избегающие 312. ^[5]

Многоуровневые перестановки являются подмножеством перестановок с сортировкой стека , которые запрещают шаблон 231, но не шаблон 312.Как и перестановки, сортируемые стеком, они также являются подмножеством разделимых перестановок , перестановок, образованных рекурсивными комбинациями прямых и косых сумм.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с Альберт, Майкл ; Энген, Майкл; Пантоне, Джей; Ваттер, Винсент (2018), «Универсальные слоистые перестановки», Электронный журнал комбинаторики , 25 (3): P23:1–P23:5, arXiv : 1710.04240 , doi : 10.37236/7386
^ Бона, Миклош (1999), «Решение гипотезы Стэнли и Уилфа для всех слоистых моделей», Журнал комбинаторной теории , серия A, 85 (1): 96–104, doi : 10.1006/jcta.1998.2908 , MR 1659444
^ Робертсон, Аарон (2001), «Перестановки, ограниченные двумя различными шаблонами длины три», Advances in Applied Mathematics , 27 (2–3): 548–561, arXiv : math/0012029 , doi : 10.1006/aama.2001.0749 , MR 1868980
^ Грей, Дэниел (2015), «Границы супершаблонов, содержащих все многоуровневые перестановки», Graphs and Combinatorics , 31 (4): 941–952, doi : 10.1007/s00373-014-1429-x , MR 3357666
^ Эгге, Эрик С.; Мансур, Туфик (2004), «Инволюции, избегающие 231, и числа Фибоначчи», Австралазийский журнал комбинаторики , 30 : 75–84, arXiv : math/0209255 , MR 2080455

[aepv-1] Jump up to: Перейти обратно: ^а ^б ^с Альберт, Майкл ; Энген, Майкл; Пантоне, Джей; Ваттер, Винсент (2018), «Универсальные слоистые перестановки», Электронный журнал комбинаторики , 25 (3): P23:1–P23:5, arXiv : 1710.04240 , doi : 10.37236/7386

[bona-2] Бона, Миклош (1999), «Решение гипотезы Стэнли и Уилфа для всех слоистых моделей», Журнал комбинаторной теории , серия A, 85 (1): 96–104, doi : 10.1006/jcta.1998.2908 , MR 1659444

[rob-3] Робертсон, Аарон (2001), «Перестановки, ограниченные двумя различными шаблонами длины три», Advances in Applied Mathematics , 27 (2–3): 548–561, arXiv : math/0012029 , doi : 10.1006/aama.2001.0749 , MR 1868980

[gray-4] Грей, Дэниел (2015), «Границы супершаблонов, содержащих все многоуровневые перестановки», Graphs and Combinatorics , 31 (4): 941–952, doi : 10.1007/s00373-014-1429-x , MR 3357666

[em-5] Эгге, Эрик С.; Мансур, Туфик (2004), «Инволюции, избегающие 231, и числа Фибоначчи», Австралазийский журнал комбинаторики , 30 : 75–84, arXiv : math/0209255 , MR 2080455

[1]

[2]

[3]

[4]

[5]