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

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

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

Пример [ править ]

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

1 2 3 4

1 2 43

1 32 4

1 432

21 3 4

21 43

321 4

4321

Характеризация запрещенными образцами [ править ]

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

Перечисление [ править ]

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

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

Суперпаттерны [ править ]

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

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

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

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

Связанные классы перестановок [ править ]

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

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

Ссылки [ править ]