Birgalikda almashtirish - Skew-merged permutation

Nazariyasida almashtirish naqshlari, a qiyshiq birlashtirilgan almashtirish a almashtirish o'sib boruvchi ketma-ketlik va kamayish ketma-ketligiga bo'linishi mumkin. Ular dastlab tomonidan o'rganilgan Stankova (1994) va ularning ismlarini berilgan Atkinson (1998).

Xarakteristikasi

O'sish va kamayish ketma-ketligiga bo'linib bo'lmaydigan ikkita eng kichik almashtirishlar 3412 va 2143 dir. Stankova (1994) birinchi bo'lib qiyshiq birlashtirilgan permutatsiyani ekvivalent ravishda 3412 va 2143 naqshlaridan qochib qutulish sifatida belgilash mumkinligini aniqladi.

O'rnatish, agar unga bog'liq bo'lsa, birlashtiriladi almashtirish grafigi a ajratilgan grafik, a ga bo'linadigan grafik klik (tushayotgan ketma-ketlikka mos keladigan) va an mustaqil to'plam (ortib boruvchi ketma-ketlikka mos keladi). 3412 va 2143-yillarda qiyshiq birlashtirilgan almashtirishlar uchun taqiqlangan ikkita naqsh, taqiqlangan uchta rasmning ikkitasiga to'g'ri keladi. induktsiya qilingan subgraflar split grafikalar uchun to'rtta vertikal tsikl va ikkitasi ajratilgan qirralari bo'lgan grafik. Uchinchi taqiqlangan subgraf, besh vertikal tsikl, almashtirish grafasida mavjud bo'lishi mumkin emas (qarang) Kezdi, Snevily va Vang (1996) ).

Hisoblash

Uchun ${ displaystyle n = 1,2,3, nuqta}$ uzunlikning birlashtirilgan permutatsiyalari soni ${ displaystyle n}$ bu

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... (ketma-ketlik) A029759 ichida OEIS ).

Atkinson (1998) ekanligini birinchi bo'lib ko'rsatgan ishlab chiqarish funktsiyasi bu raqamlar

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

shundan kelib chiqadiki, uzunlikning birlashtirilgan permutatsiyalari soni ${ displaystyle n}$ formula bilan berilgan

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

va bu raqamlar takrorlanish munosabati

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

To'g'ri birlashtirilgan permutatsiyalar uchun ishlab chiqarish funktsiyasining yana bir chiqarilishi berilgan Albert va Vatter (2013).

Hisoblashning murakkabligi

Bir permutatsiyaning ikkinchisida naqsh ekanligi yoki yo'qligini sinab ko'rish, ikkita permutatsiyaning kattaroqligi birlashtirilganda samarali echilishi mumkin. Albert va boshq. (2016).

Adabiyotlar

• Albert, Maykl; Vatter, Vinsent (2013), "321 ta qochish va qiyshiq birlashtirilgan oddiy almashtirishlarni yaratish va ro'yxatga olish", Elektron kombinatorika jurnali, 20 (2): 44-qog'oz, 11-bet, JANOB  3084586.

• Albert, Maykl; Lackner, Mari-Luiza; Lackner, Martin; Vatter, Vinsent (2016), "321 ta qochish va qiyshiq birlashtirilgan almashtirishlar uchun mos keladigan naqshlarning murakkabligi", Permutation Patterns 2015, Diskret matematika va nazariy kompyuter fanlari, 18 (2): P11: 1-17, arXiv:1510.06051, Bibcode:2015arXiv151006051A, JANOB  3597961.

• Atkinson, M. D. (1998), "O'sib boruvchi va kamayib boruvchi birlashmaning birlashmasi bo'lgan ruxsatnomalar", Elektron kombinatorika jurnali, 5: RP6: 1-13, JANOB  1490467. Shuningdek, Volker Strehl tomonidan berilgan izohga qarang.

• Kezdi, Andre E.; Snevili, ovchi S .; Vang, Chi (1996), "Permutatsiyalarni ortib boruvchi va kamayuvchi keyingi qismlarga ajratish", Kombinatoriya nazariyasi jurnali, A seriyasi, 73 (2): 353–359, doi:10.1016 / S0097-3165 (96) 80012-4, JANOB  1370138

• Sloan, N. J. A. (tahrir). "A029759 ketma-ketligi". The Butun sonlar ketma-ketligining on-layn ensiklopediyasi. OEIS Foundation.

• Stankova, Zvezdelina E. (1994), "Taqiqlangan ketma-ketliklar", Diskret matematika, 132 (1–3): 291–316, doi:10.1016 / 0012-365X (94) 90242-9, JANOB  1297387. Xususan, Teorema 2.9 ga qarang, 303-304-betlar.