Перестановка с перекосом - Skew-merged permutation - Wikipedia

В теории шаблоны перестановок, а перестановка с перекосом это перестановка которые можно разделить на возрастающую и убывающую последовательность. Впервые они были изучены Станкова (1994) и дали свое имя Аткинсон (1998).

Характеристика

Две наименьшие перестановки, которые нельзя разделить на возрастающую и убывающую последовательность, - это 3412 и 2143. Станкова (1994) был первым, кто установил, что асимметричная перестановка также может быть эквивалентно определена как перестановка, которая избегает двух шаблонов 3412 и 2143.

Перестановка сливается с перекосом тогда и только тогда, когда она связана граф перестановок это разделенный график, граф, который можно разбить на клика (соответствующая убывающей подпоследовательности) и независимый набор (соответствует возрастающей подпоследовательности). Два запрещенных шаблона для асимметричных перестановок, 3412 и 2143, соответствуют двум из трех запрещенных индуцированные подграфы для расщепленных графов - цикл с четырьмя вершинами и граф с двумя непересекающимися ребрами соответственно. Третий запрещенный индуцированный подграф, пятивершинный цикл, не может существовать в графе перестановок (см. Кезды, Сневилы и Ван (1996) ).

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

За ${ Displaystyle п = 1,2,3, точки}$ количество перестановок длины ${ displaystyle n}$ является

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... (последовательность A029759 в OEIS ).

Аткинсон (1998) был первым, кто показал, что производящая функция из этих чисел

${ displaystyle { frac {1-3x} {(1-2x) { sqrt {1-4x}}}},}$

откуда следует, что количество несимметричных перестановок длины ${ displaystyle n}$ дается формулой

${ displaystyle { binom {2n} {n}} sum _ {m = 0} ^ {n-1} 2 ^ {n-m-1} { binom {2m} {m}}}$

и что эти числа соответствуют отношение повторения

${ Displaystyle P_ {n} = { frac {(9n-8) P_ {n-1} - (26n-46) P_ {n-2} + (24n-60) P_ {n-3}} {n }}.}$

Другой вывод производящей функции для асимметричных перестановок был дан формулой Альберт и Ваттер (2013).

Вычислительная сложность

Проверка того, является ли одна перестановка шаблоном в другой, может быть эффективно решена, когда большая из двух перестановок сливается с перекосом, как показано Альберт и др. (2016).

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

• Альберт, Майкл; Ваттер, Винсент (2013), "Генерация и перечисление простых перестановок, избегающих 321 и перекосов слияния", Электронный журнал комбинаторики, 20 (2): Документ 44, 11 с., МИСТЕР  3084586.

• Альберт, Майкл; Лакнер, Мария-Луиза; Лакнер, Мартин; Ваттер, Винсент (2016), «Сложность сопоставления с образцом для 321-избегающих и асимметричных перестановок», Шаблоны перестановок 2015, Дискретная математика и теоретическая информатика, 18 (2): P11: 1–17, arXiv:1510.06051, Bibcode:2015arXiv151006051A, МИСТЕР  3597961.

• Аткинсон, М. Д. (1998), «Перестановки, которые представляют собой объединение возрастающей и убывающей подпоследовательности», Электронный журнал комбинаторики, 5: RP6: 1–13, МИСТЕР  1490467. См. Также прикрепленный комментарий Фолькера Штреля.

• Kézdy, André E .; Сневилый, Хантер С .; Ван, Чи (1996), "Разбиение перестановок на возрастающие и убывающие подпоследовательности", Журнал комбинаторной теории, серия А, 73 (2): 353–359, Дои:10.1016 / S0097-3165 (96) 80012-4, МИСТЕР  1370138

• Слоан, Н. Дж. А. (ред.). «Последовательность A029759». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.

• Станкова, Звезделина Е. (1994), «Запрещенные подпоследовательности», Дискретная математика, 132 (1–3): 291–316, Дои:10.1016 / 0012-365X (94) 90242-9, МИСТЕР  1297387. См., В частности, теорему 2.9, стр. 303–304.