Permutatsiya sxemasi - Permutation pattern

Yilda kombinatoriya matematikasi va nazariy informatika, a almashtirish tartibi uzunroq submututatsiya almashtirish. Har qanday almashtirishni yozish mumkin bir qatorli yozuv 123 raqamli ketma-ketlikka almashtirishni qo'llash natijasini ifodalovchi raqamlar ketma-ketligi sifatida ... ...; Masalan, 213 raqamli ketma-ketlik 1 va 2 elementlarni almashtiradigan uchta elementdagi almashinuvni aks ettiradi. Agar $ p $ va $ g $ shu tarzda ifodalangan ikkita almashtirish bo'lsa (bu o'zgaruvchilar nomlari almashtirish uchun standart va raqam bilan bog'liq emas) pi ), keyin π deyiladi o'z ichiga oladi σ sifatida naqsh agar π raqamlarining ba'zi bir ketma-ketliklari σ ning barcha raqamlari bilan bir xil nisbiy tartibga ega bo'lsa.

Masalan, π permutation π uchta raqamga ega bo'lganda 213 naqshni o'z ichiga oladi x, yva z tartibida π ichida paydo bo'ladi x...y...z ammo uning qiymatlari quyidagicha tartiblangan y < x < z, 213 almashtirishdagi qiymatlarning tartibi bilan bir xil. Beshta elementdagi 32415 almashtirish 213 ni naqsh sifatida bir necha xil usulda o'z ichiga oladi: 3 ·· 15, ·· 415, 32 ·· 5, 324 ·· va · 2 · 15 barchasi 213 bilan tartiblangan uchta uchlikdan iborat. 315, 415, 325, 324 va 215 pastki qismlarining har biri a deb ataladi nusxa ko'chirish, misol, yoki voqea naqshning Π tarkibida σ borligi σ ≤ π kabi aniqroq yozilgan. Agar m almashtirishda σ naqsh bo'lmasa, u holda π deyiladi qochmoq σ. 51342 permutatsiyasi 213 dan qochadi; u uchta raqamdan iborat 10 ta ketma-ketlikka ega, ammo bu 10 ta ketma-ketlikning hech biri 213-ga o'xshash tartibga ega emas.

Dastlabki natijalar

Biror ishni bajarish mumkin Persi MakMaxon  (1915 ) sohada birinchi bo'lib "panjara almashtirishlari" ni o'rganishi bilan isbotladi.[1] Xususan, MacMahon ikkita kamayuvchi ketma-ketlikka bo'linishi mumkin bo'lgan almashtirishlarni (ya'ni 123 ta saqlanadigan permütatsiyalar) quyidagicha hisoblaydi. Kataloniya raqamlari.[2]

Bu sohadagi yana bir dastlabki muhim natijalar Erduss-Sekeres teoremasi; almashtirish naqshida, har qanday musbat tamsayılar uchun teorema ta'kidlangan a va b hech bo'lmaganda uzunlikning har bir o'zgarishi naqshni o'z ichiga olishi kerak yoki naqsh .

Informatika kelib chiqishi

Almashtirish naqshlarini o'rganish jiddiy ravishda boshlandi Donald Knuth ko'rib chiqish stack-sorting 1968 yilda.[3] Knut ko'rsatdiki, $ p $ o'rnini $ a $ bilan tartiblash mumkin suyakka agar $ f $ $ 231 $ dan qochib qutulsa va stack-sortable permutations sanab chiqilsa. Kataloniya raqamlari.[4] Knut shuningdek saralash bo'yicha savollar tug'dirdi deques. Xususan, Knutning qancha almashtirishni so'ragan savoli n elementlar deque yordamida ochiq bo'lib qoladi.[5] Ko'p o'tmay, Robert Tarjan  (1972 ) stack tarmoqlari bo'yicha saralashni o'rganib chiqdi,[6] esa Vaughan Pratt  (1973 $ Delta $ permautatsiyasini deque tomonidan tartiblash mumkinligini ko'rsatdi va agar hammasi bo'lsa k, π 5,2,7,4, ..., 4 dan qochadik+1,4k−2,3,4k, 1 va 5,2,7,4, ..., 4k+3,4k,1,4k+2,3 va har ikkala ikkinchisidan oxirgi ikkita elementni yoki 1 va 2 ni almashtirish orqali olish mumkin bo'lgan har bir almashtirish.[7] Ushbu permutatsiyalar to'plami cheksiz bo'lgani uchun (aslida bu cheksizning birinchi nashr etilgan namunasidir antichain permutations), permutatsiyani dek tomonidan saralash mumkinmi yoki yo'qligini hal qilish uchun qancha vaqt ketishi aniq emas. Rozenstiehl va Tarjan (1984) keyinchalik π deque tomonidan saralanishi mumkinligini aniqlaydigan chiziqli (a uzunlikdagi) vaqt algoritmini taqdim etdi.[8]

O'zining maqolasida Pratt ushbu almashtirish tartibining tartibi "oddiy va tabiiy tarzda paydo bo'ladigan almashtirishning yagona qisman buyrug'i bo'lib tuyuladi" deb ta'kidladi va "mavhum nuqtai nazardan", almashtirish tartibining tartibi " biz xarakterlaydigan tarmoqlardan ham qiziqroq ".[7]

Ro'yxatning kelib chiqishi

Asosiy maqola: Maxsus almashtirish sinflarining sanoqlari

O'tkazish naqshlarini o'rganishning muhim maqsadi sobit (va odatda qisqa) almashtirish yoki almashtirish majmuasidan qochib, almashtirishlarni sanab chiqishdir. Ruxsat bering Avn(B) uzunlikdagi permutatsiyalar to'plamini belgilang n to'plamdagi barcha almashtirishlardan qochishadi B (holda) B singleton, masalan, β, qisqartmasi Avn(β) o'rniga ishlatiladi). Yuqorida ta'kidlab o'tilganidek, MacMahon va Knut buni ko'rsatdilar |Avn(123)| = |Avn(231)| = Cn, nKataloniya raqami Shunday qilib, ular izomorfikdir kombinatoriya darslari.

Simion va Shmidt (1985) faqat ro'yxatga olishga e'tibor qaratgan birinchi qog'oz edi. Boshqa natijalar qatorida Simion va Shmidt ham hisoblashdi juft va toq almashtirishlar uchta uzunlikdagi naqshdan saqlanish, permütasyonlardan qochish uzunlikdagi uchta naqsh va 123 va 231 dan qochadigan almashtirishlarning teng sonli ekanligiga birinchi biektiv dalilni keltirdi.[9] O'zlarining qog'ozlaridan beri ko'plab boshqa bahslar berilgan, qarang Claesson & Kitaev (2008) so'rov uchun.[10]

Umuman olganda, agar |Avn(β) | = |Avn(σ) | Barcha uchun n, keyin β va σ deyiladi Vilfga teng. Ko'p Wilf ekvivalentsiyalari |Avn(β) | = |Avn(β−1)| = |Avn(βrev) | Barcha uchun n, qaerda β-1 belgisini bildiradi teskari β va of ningrev β ning teskari tomonini bildiradi. (Ushbu ikkita operatsiya Dihedral guruh D8 tabiiy harakat bilan almashtirish matritsalari.) Shu bilan birga, noan'anaviy Vilf ekvivalentlarining ko'plab misollari ham mavjud (masalan, ular orasidagi kabi) 123 va 231):

Ushbu ikki Vilf-ekvivalentsiyasi va teskari va teskari simmetriyalaridan uch xil ketma-ketlik borligi kelib chiqadi |Avn(β) | bu erda β to'rtinchi uzunlikka ega:

βketma-ketlikni sanab o'tish Avn(β)OEIS ma'lumotnomaaniq ro'yxatga olish ma'lumotnomasi
 1342 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...A022558Bona (1997)[14]
 1234 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...A005802Gessel (1990)[15]
 1324 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...A061552raqamsiz

1980-yillarning oxirida, Richard Stenli va Gerbert Uilf har bir almashtirish uchun $ mathbb {doimiy} $ mavjud deb taxmin qildim K shunday |Avn(β) | < Kn. Bu sifatida tanilgan edi Stenli-Uilf gumoni isbotlanmaguncha Adam Markus va Gábor Tardos.[16]

Yopiq darslar

Asosiy maqola: Permutatsiya klassi

A yopiq sinf, shuningdek, a naqsh sinfi, almashtirish sinfiyoki oddiygina sinf almashtirishlar a pasayish almashtirish tartibida. Har bir sinfni uning ichida bo'lmagan minimal almashtirishlar bilan aniqlash mumkin, uning asos. Shunday qilib, stack-sortable permutations uchun asos {231}, deque-sortable permutations uchun asos cheksizdir. The ishlab chiqarish funktsiyasi sinf uchun Σ x| π | bu erda yig'indisi sinfdagi barcha almashtirishlar bo'yicha olinadi.

Mobius funktsiyasi

Sifatida saqlash tartibida joylashgan almashtirishlar to'plami shakllanadi poset bu haqda so'rash tabiiy Mobius funktsiyasi, maqsad birinchi bo'lib aniq ko'rsatib o'tilgan Uilf (2002).[17]Bunday tekshiruvlarning maqsadi poset almashtirish rejimida [pattern, π] intervalining Mobius funktsiyasining sodda rekursiv ta'rifiga qaraganda samaraliroq bo'lgan formulasini topishdir. Birinchi shunday natija Sagan va Vatter (2006), intervalining Mobius funktsiyasi uchun formulani kim bergan qatlamli almashtirishlar.[18]Keyinchalik, Bershteyn va boshq. (2011) bu natijani intervalgacha umumlashtirdi ajratiladigan almashtirishlar.[19]

Ma'lumki, asimptotik ravishda, barcha permütatsiyalarning kamida 39,95% π uzunlik n qondirish m (1, satisf) = 0 (ya'ni asosiy Mobius funktsiyasi nolga teng)[20], lekin har biri uchun n $ mathbb {m (1, phi) $ ning eksponent funktsiyasi bo'lishi uchun $ mathbb {m} $ almashtirishlari mavjud n[21].

Hisoblashning murakkabligi

Imkoniyat berilgan (deb nomlangan matn) uzunligi va yana bir almashtirish uzunlik (deb nomlangan naqsh), the almashinish naqshini moslashtirish (PPM) muammo yo'qmi deb so'raydi tarkibida mavjud . Ikkalasi ham va o'zgaruvchilar sifatida qaraladi, muammo ma'lum To'liq emas va bunday o'yinlarning sonini hisoblash muammosi # P tugadi.[22] Biroq, PPM ni hal qilish mumkin chiziqli vaqt qachon k doimiy. Darhaqiqat, Gilyot va Marks[23] PPMni o'z vaqtida hal qilish mumkinligini ko'rsatdi , degan ma'noni anglatadi belgilangan parametrlarni boshqarish mumkin munosabat bilan .

Bruner va Lackner tomonidan o'rganilgan PPM muammosi bo'yicha bir nechta variantlar mavjud.[24] Misol uchun, agar mos keladigan yozuvlardan iborat bo'lishi kerak bo'lsa, unda masalani polinom vaqtida echish mumkin.[25]

Yana bir variant - naqsh va matn ikkalasi ham tegishli almashtirish sinfiga cheklangan bo'lsa , bu holda muammo chaqiriladi -PPM. Masalan, Guillemot va Vialette[26] buni ko'rsatdi -PPM-ni hal qilish mumkin edi vaqt. Albert, Lackner, Lackner va Vatter[27] keyinchalik buni pastga tushirdi va ning sinfi uchun bir xil chegara tutilishini ko'rsatdi qiyshiq birlashtirilgan almashtirishlar. Ular qo'shimcha ravishda so'radilar -PPM muammosi har bir belgilangan to'g'ri almashtirish sinfi uchun polinom vaqtida echilishi mumkin .

Paket zichligi

Π almashtirishga β- deyiladimaqbul agar π bilan bir xil uzunlikdagi permutatsiyada β nusxalari ko'p bo'lmasa. SIAM-ning diskret matematika bo'yicha 1992 yilgi yig'ilishidagi nutqida Uilf quyidagilarni aniqladi qadoqlash zichligi β uzunlikning o'zgarishi k kabi

Ning nashr qilinmagan argumenti Fred Galvin uning ichidagi miqdor ekanligini ko'rsatadi chegara uchun ko'paytirilmaydi n ≥ kva shuning uchun chegara mavjud. Β monoton bo'lsa, uning qadoqlash zichligi aniq 1 ga teng bo'ladi va qadoqlash zichligi teskari va teskari tomonidan hosil qilingan nosimmetrikliklar guruhi ostida o'zgarmasdir, shuning uchun uch uzunlikdagi permütatsiyalar uchun faqat bitta nrivrivial qadoqlash zichligi mavjud. Valter Stromquist (nashr qilinmagan) bu ishni 132 ning zichligi 2 ga teng ekanligini ko'rsatib hal qildi√3 - 3, taxminan 0.46410.

To'rtinchi uzunlikdagi permutatsiyalar uchun (simmetriya tufayli) ettita holatni ko'rib chiqish kerak:

βqadoqlash zichligima'lumotnoma
 1234 1ahamiyatsiz
 1432 ning ildizi x3 − 12x2 + 156x − 64 ≅ 0.42357Narx (1997)[28]
 2143 ⅜ = 0.375Narx (1997)[28]
 1243 ⅜ = 0.375Albert va boshq. (2002)[29]
 1324 g 0,44 ga teng
 1342 ≅ 0.19658 deb taxmin qilingan
 2413 ≅ 0.10474 deb taxmin qilingan

Uchta noma'lum almashtirish uchun chegaralar va taxminlar mavjud. Narx (1997) 1324 ning zichligi 0,244 atrofida ekanligini taxmin qiladigan taxminiy algoritmdan foydalanilgan.[28] Birjan Batkeyev (nashr etilmagan), 1342 ning qadoqlash zichligi, hech bo'lmaganda, 132 va 1432 qadoqlash zichligi mahsuloti, taxminan 0.19658 mahsulot ekanligini ko'rsatib, almashtirish oilasini yaratdi. Bu aniq qadoqlash zichligi 1342 bo'lishi mumkin. Presutti va Stromkist (2010) qadoqlash zichligi bo'yicha pastki chegarani 2413 ga tenglashtirdi. Bu integral bilan ifodalanadigan pastki chegara taxminan 0,10474 ga teng va haqiqiy qadoqlash zichligi deb taxmin qilinadi.[30]

Super naqshlar

Asosiy maqola: Superpattern

A k-super naqsh uzunlikning barcha almashtirishlarini o'z ichiga olgan almashtirish k. Masalan, 25314 - bu 3 superpattern, chunki u uzunlik 3 ning barcha 6 ta permutatsiyasini o'z ichiga oladi. k-superpatterns kamida uzunligi bo'lishi kerak k2/e2, qayerda e 7 2.71828 bu Eyler raqami,[31] va mavjudligini k- uzunlik namunalari ⌈ (k2 + 1)/2⌉.[32]Ushbu yuqori chegara imkon qadar past darajadagi shartlarga qadar taxmin qilinadi.[33]

Umumlashtirish

"Naqsh" tushunchasini umumlashtirishning bir necha yo'li mavjud. Masalan, a vinkulyar naqsh bu ketma-ket yuz bermasligi kerak bo'lgan yozuvlarni ko'rsatadigan tirelarni o'z ichiga olgan permutatsiya (odatdagi naqsh ta'rifida hech qanday yozuv ketma-ket kelishi shart emas). Masalan, 314265-sonli almashtirishda 3426 va 3425-sonli yozuvlar bilan berilgan 2-31-4 chiziqli naqshlarning ikkita nusxasi mavjud. Kesilgan naqsh uchun va har qanday permutatsiya π uchun biz β (π) ni β nusxalari soni uchun yozamiz. π ichida. Shunday qilib, in dagi inversiyalar soni 2-1 (π) ga teng, tushish soni esa 21 (p) ga teng. Keyinchalik, ularning soni vodiylar π da 213 (π) + 312 (π) bo'ladi, soni esa cho'qqilar 231 (π) + 132 (π) ga teng. Ushbu naqshlar tomonidan kiritilgan Babson & Steingrímsson (2000), kim deyarli hamma ma'lum ekanligini ko'rsatdi Mahoniya statistikasi vincular permutations bilan ifodalanishi mumkin edi.[34] Masalan, Asosiy indeks ning 1 1-32 (π) + 2-31 (π) + 3-21 (π) + 21 (π) ga teng.

Yana bir umumlashtirish - bu a taqiqlangan naqsh, unda ba'zi yozuvlar taqiqlangan. $ To'siq qo'yilgan naqshdan qochish uchun β degan ma'noni anglatadi, $ p $ ning barcha satrlar to'plamining nusxasini hosil qilish uchun kengaytirilgan bo'lishi mumkin. G'arbiy (1993) almashtirish usullarini o'rganishda ushbu naqsh turlarini joriy qildi, ularni ikki marta stakadan o'tkazib saralash mumkin edi.[35] (E'tibor bering, G'arbning stek orqali ikki marta saralash haqidagi ta'rifi ketma-ket ikkita stak bilan saralash bilan bir xil emas.) Taqiqlangan naqshlarning yana bir misoli Bousquet-Mélou & Butler (2007), kim buni ko'rsatdi Shubert navi π ga to'g'ri keladi mahalliy faktorial agar $ f $ va $ 1324 $ dan qochish kerak bo'lsa354.[36]

Adabiyotlar

  1. ^ MakMaxon, Persi A. (1915), Kombinatsion tahlil, London: Kembrij universiteti matbuoti, I tom, III bo'lim, V bob.
  2. ^ MacMahon (1915), 97 va 98-bandlar.
  3. ^ Knut, Donald E. (1968), Kompyuter dasturlash san'ati. 1, Boston: Addison-Uesli, ISBN  0-201-89683-4, JANOB  0286317, OCLC  155842391..
  4. ^ Knut (1968), 2.2.1-bo'lim, 4 va 5-mashq.
  5. ^ Knut (1968), 2.2.1-bo'lim, 13-mashq, birinchi bosmada M49, ikkinchisida M48 deb baholandi.
  6. ^ Tarjan, Robert (1972), "Navbat va stek tarmoqlari yordamida saralash", ACM jurnali, 19 (2): 341–346, doi:10.1145/321694.321704, JANOB  0298803, S2CID  13608929.
  7. ^ a b Pratt, Vaughan R. (1973), "Ikkala uchli navbat bilan almashtirishni hisoblash. Parallel stek va parallel navbat", Proc. Kompyuter nazariyasi bo'yicha Beshinchi yillik ACM simpoziumi (Ostin, Teks., 1973), 268–277 betlar, doi:10.1145/800125.804058, JANOB  0489115, S2CID  15740957.
  8. ^ Rozenstixl, Per; Tarjan, Robert (1984), "Gauss kodlari, planlangan Gemilton grafikalari va stack-sortable permutations", Algoritmlar jurnali, 5 (3): 375–390, doi:10.1016 / 0196-6774 (84) 90018-X, JANOB  0756164.
  9. ^ Simion, Rodika; Shmidt, Frank V. (1985), "Cheklangan almashtirishlar", Evropa Kombinatorika jurnali, 6 (4): 383–406, doi:10.1016 / s0195-6698 (85) 80052-4, JANOB  0829358.
  10. ^ Klesson, Anders; Kitaev, Sergey (2008), "321 va 132 oralig'idagi almashtirishlar tasnifi" (PDF), Séminaire Lotaringien de Kombinatuar, 60: B60d, arXiv:0805.1325, Bibcode:2008arXiv0805.1325C, JANOB  2465405.
  11. ^ Stankova, Zvezdelina (1994), "Taqiqlangan ketma-ketliklar", Diskret matematika, 132 (1–3): 291–316, doi:10.1016 / 0012-365X (94) 90242-9, JANOB  1297387.
  12. ^ Stankova, Zvezdelina; G'arbiy, Julian (2002), "Wilf-tenglashtirilgan permutatsiyalarning yangi klassi", Algebraik kombinatorika jurnali, 15 (3): 271–290, arXiv:matematik / 0103152, doi:10.1023 / A: 1015016625432, JANOB  1900628, S2CID  13921676.
  13. ^ Backelin, Yorgen; G'arbiy, Julian; Xin, Guoce (2007), "Singlton sinflari uchun Wilf-ekvivalenti", Amaliy matematikaning yutuqlari, 38 (2): 133–149, doi:10.1016 / j.aam.2004.11.006, JANOB  2290807.
  14. ^ Bona, Miklos (1997), "1342-sonli almashtirishlarni aniq ro'yxati: belgilangan daraxtlar va tekis xaritalar bilan yaqin bog'lanish", Kombinatoriya nazariyasi jurnali, A seriyasi, 80 (2): 257–272, arXiv:matematik / 9702223, Bibcode:1997 yil ...... 2223B, doi:10.1006 / jcta.1997.2800, JANOB  1485138, S2CID  18352890.
  15. ^ Gessel, Ira M. (1990), "Simmetrik funktsiyalar va P-rekursivlik ", Kombinatoriya nazariyasi jurnali, A seriyasi, 53 (2): 257–285, doi:10.1016 / 0097-3165 (90) 90060-A, JANOB  1041448.
  16. ^ Markus, Odam; Tardos, Gábor (2004), "Istisno qilingan almashtirish matritsalari va Stenli-Uilf gumoni", Kombinatoriya nazariyasi jurnali, A seriyasi, 107 (1): 153–160, doi:10.1016 / j.jcta.2004.04.002, JANOB  2063960.
  17. ^ Uilf, Gerbert (2002), "Permutatsiya naqshlari", Diskret matematika, 257 (2): 575–583, doi:10.1016 / S0012-365X (02) 00515-0, JANOB  1935750.
  18. ^ Sagan, Bryus; Vatter, Vins (2006), "Kompozitsiya posetining Mobius funktsiyasi", Algebraik kombinatorika jurnali, 24 (2): 117–136, arXiv:matematik / 0507485, doi:10.1007 / s10801-006-0017-4, JANOB  2259013, S2CID  11283347.
  19. ^ Bershteyn, Aleksandr; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (2011), "Ajraladigan va ajraladigan permütatsiyalarning Mobius funktsiyasi", Kombinatoriya nazariyasi jurnali, A seriyasi, 118 (1): 2346–2364, doi:10.1016 / j.jcta.2011.06.002, JANOB  2834180, S2CID  13978488.
  20. ^ Brignol, Robert; Jelinek, Vit; Kynchl, Yan; Marchant, Devid (2019), "Permutatsiyalarning Mobius funktsiyasining nollari" (PDF), Matematika, 65 (4): 1074–1092, doi:10.1112 / S0025579319000251, JANOB  3992365, S2CID  53366318
  21. ^ Marchant, Devid (2020), "2413-sharning almashinishi va Mobius funktsiyasining o'sishi", Elektron kombinatorika jurnali, 27 (1): P1.7, doi:10.37236/8554
  22. ^ Bose, Prosenjit; Buss, Jonathan F.; Lubiv, Anna (1998 yil mart), "Permutatsiyalar uchun naqshlarni moslashtirish", Axborotni qayta ishlash xatlari, 65 (5): 277–283, doi:10.1016 / S0020-0190 (97) 00209-3
  23. ^ Gillemot, Silveyn; Marks, Daniel (2014). "Chiziqli vaqt ichida almashtirishlarda kichik naqshlarni topish". Yigirma beshinchi yillik ACM-SIAM diskret algoritmlari bo'yicha simpoziumi materiallari.: 20. arXiv:1307.3073. doi:10.1137/1.9781611973402.7. ISBN  978-1-61197-338-9. S2CID  1846959.
  24. ^ Bruner, Mari-Luiza; Lackner, Martin (2013), "Permutatsion naqshlarning hisoblash manzarasi", Sof matematika va amaliy dasturlar, 24 (2): 83–101, arXiv:1301.0340, Bibcode:2013arXiv1301.0340B
  25. ^ Kubica, M .; Kulchitski, T .; Radoszevskiy, J .; Rytter, V.; Valeu, T. (2013), "ketma-ket joylashish naqshini moslashtirish uchun chiziqli vaqt algoritmi", Axborotni qayta ishlash xatlari, 113 (12): 430–433, doi:10.1016 / j.ipl.2013.03.015
  26. ^ Gillemot, Silveyn; Vialette, Stéphane (2009), "321 ta permütatsiya uchun mos keladigan naqsh", Algoritmlar va hisoblash, Kompyuter fanidan ma'ruza matnlari, 5878, 1064–1073-betlar, arXiv:1511.01770, doi:10.1007/978-3-642-10631-6_107
  27. ^ Albert, Maykl; Lackner, Mari-Luiza; Lackner, Martin; Vatter, Vinsent (2016), "321 ta qochish va qiyshiq birlashtirilgan almashtirishlar uchun naqshlarni moslashtirishning murakkabligi", Diskret matematika va nazariy kompyuter fanlari, 18 (2), arXiv:1510.06051, Bibcode:2015arXiv151006051A
  28. ^ a b v Narxi, Alkes (1997), Qatlamli naqshlarning zichligini qadoqlash, T.f.n. tezis, Pensilvaniya universiteti.
  29. ^ Albert, Maykl H.; Atkinson, M. D .; Xandli, C. S.; Xolton, D. A .; Stromvist, V. (2002), "O'rnatish zichligi qadoqlash to'g'risida", Elektron kombinatorika jurnali, 9: Tadqiqot maqolasi 5, 20 bet, doi:10.37236/1622, JANOB  1887086.
  30. ^ Presutti, Ketlin Battist; Stromquist, Valter (2010), "O'lchov qadoqlash stavkalari va qadoqlash zichligi uchun gumon 2413", Lintonda, Stiv; Rushkuc, Nik; Vatter, Vinsent (tahr.), Permutatsiya naqshlari, London matematikasi. Soc. Ma'ruza yozuvlari, 376, Kembrij universiteti matbuoti, 287–316 betlar, doi:10.1017 / CBO9780511902499.015.
  31. ^ Arratiya, Richard (1999), "Stenli-Uilfning taxminiy gumoniga binoan, ushbu naqshdan qochish uchun permutatsiya soni", Elektron kombinatorika jurnali, 6: N1, doi:10.37236/1477, JANOB  1710623.
  32. ^ Engen, Maykl; Vatter, Vinsent (2019), Barcha almashtirishlarni o'z ichiga olgan, arXiv:1810.08252, Bibcode:2018arXiv181008252E.
  33. ^ Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Västlund, Yoxan (2007), "Permutatsiyada naqshlarning zich qadoqlanishi", Kombinatorika yilnomalari, 11 (3–4): 459–470, doi:10.1007 / s00026-007-0329-7, JANOB  2376116, S2CID  2021533.
  34. ^ Babson, Erik; Steingrímsson, Einar (2000), "Mahalliy statistikaning umumiy joylashuvi va tasnifi", Séminaire Lotaringien de Kombinatuar, 44: Tadqiqot maqolasi B44b, 18 bet, JANOB  1758852.
  35. ^ G'arbiy, Julian (1993), "Yig'ma orqali ikki marta saralash", Nazariy kompyuter fanlari, 117 (1–2): 303–313, doi:10.1016 / 0304-3975 (93) 90321-J, JANOB  1235186.
  36. ^ Busket-Meu, Mirey; Butler, Stiv (2007), "O'rmonga o'xshash almashtirishlar", Kombinatorika yilnomalari, 11 (3–4): 335–354, arXiv:matematik / 0603617, doi:10.1007 / s00026-007-0322-1, JANOB  2376109, S2CID  31236417.

Tashqi havolalar

Permutatsiya naqshlari bo'yicha konferentsiya bo'lib o'tdi 2003 yildan beri har yili o'tkaziladi:

  1. Permutatsiya naqshlari 2003 yil, 2003 yil 10–14 fevral, Otago universiteti, Dunedin, Yangi Zelandiya.
  2. Permutatsiya naqshlari 2004 yil, 2004 yil 5-9 iyul, Malaspina universiteti-kolleji, Nanaimo, Britaniya Kolumbiyasi, Kanada.
  3. Permutatsiya naqshlari 2005 yil, 2005 yil 7–11 mart, Florida universiteti, Geynesvill, Florida, AQSh.
  4. Permutatsiya naqshlari 2006 yil, 2006 yil 12-16 iyun, Reykyavik universiteti, Reykyavik, Islandiya.
  5. Permutatsiya naqshlari 2007 yil, 2007 yil 11-15 iyun, Sent-Endryus universiteti, Sent-Endryus, Shotlandiya.
  6. Permutatsiya naqshlari 2008 yil, 2008 yil 16–20 iyun, Otago universiteti, Dunedin, Yangi Zelandiya.
  7. Permutatsiya naqshlari 2009 yil, 2009 yil 13-17 iyul, Firenze universiteti, Florensiya, Italiya.
  8. Permutatsiya naqshlari 2010 yil, 2010 yil 9-13 avgust, Dartmut kolleji, Gannover, Nyu-Xempshir, AQSh.
  9. Permutatsiya naqshlari 2011 yil, 2011 yil 20-24 iyun, Kaliforniya politexnika davlat universiteti, San-Luis Obispo, Kaliforniya, AQSh.
  10. Permutatsiya naqshlari 2012 yil, 2012 yil 11-15 iyun, Strathclyde universiteti, Glazgo, Shotlandiya.
  11. Permutatsiya naqshlari 2013 yil, 2013 yil 1-5 iyul, Université Parij Diderot, Parij, Frantsiya.
  12. Permutatsiya naqshlari 2014 yil, 2014 yil 7–11-iyul, Sharqiy Tennessi shtati universiteti, Jonson Siti, Tennessi, AQSh.
  13. Permutatsiya naqshlari 2015 yil, 2015 yil 15-19 iyun, De Morgan uyi, London, Angliya.
  14. Permutatsiya naqshlari 2016 yil, 2016 yil 27 iyun - 1 iyul, Xovard universiteti, Vashington, DC, AQSh.
  15. Permutatsiya naqshlari 2017 yil, 2017 yil 26-30 iyun, Reykyavik universiteti, Reykyavik, Islandiya.
  16. Permutatsiya naqshlari 2018, 2018 yil 9-13 iyul, Dartmut kolleji, Gannover, Nyu-Xempshir, AQSh.
  17. Permutatsiya naqshlari 2019, 2019 yil 17-21 iyun, Tsyurix universiteti, Tsyurix, Shveytsariya.
  18. Permutation Patterns 2020 Virtual Workshop, 2020 yil 30-iyun - 1-iyul, mezbonlik qiladi Valparaiso universiteti, Valparaiso, Indiana, AQSh.

Amerika matematik jamiyati Permutatsiyalardagi naqshlar bo'yicha maxsus mashg'ulotlar quyidagi uchrashuvlarda bo'lib o'tdi:

Boshqa almashtirish naqshlari uchrashuvlari:

Boshqa havolalar: