क्रमपरिवर्तन पैटर्न

साहचर्य और सैद्धांतिक कंप्यूटर विज्ञान में, एक क्रमचय पैटर्न एक लंबे क्रमचय का उप-क्रमपरिवर्तन है। किसी भी क्रमपरिवर्तन को Permutation#One-line_notation|एक-पंक्ति अंकन में लिखा जा सकता है, अंकों के अनुक्रम के रूप में अंक क्रम 123...; उदाहरण के लिए अंक अनुक्रम 213 तीन तत्वों पर क्रमचय का प्रतिनिधित्व करता है जो तत्वों 1 और 2 को स्वैप करता है। यदि π और σ इस तरह से प्रदर्शित दो क्रमपरिवर्तन हैं (ये परिवर्तनीय नाम क्रमपरिवर्तन के लिए मानक हैं और संख्या अनुकरणीय आई से संबंधित नहीं हैं), तो π है यदि π के अंकों के कुछ अनुक्रम में σ के सभी अंकों के समान सापेक्षिक क्रम है, तो पैटर्न के रूप में σ को शामिल करने के लिए कहा जाता है।

उदाहरण के लिए, क्रमपरिवर्तन π में पैटर्न 213 होता है जब भी π में तीन अंक x, y, और z होते हैं जो π के भीतर x...y क्रम में दिखाई देते हैं। ...z लेकिन जिनके मान y < x < z के रूप में क्रमबद्ध हैं, क्रमपरिवर्तन 213 में मानों के क्रम के समान हैं। क्रमपरिवर्तन 32415 पांच तत्वों पर 213 को कई अलग-अलग तरीकों से एक पैटर्न के रूप में शामिल किया गया है: 3··15, ··415, 32··5, 324··, और ·2·15 सभी 213 के समान क्रम के साथ अंकों के त्रिगुण बनाते हैं। इनमें से प्रत्येक बाद के 315, 415, 325, 324, और 215 को पैटर्न की प्रतिलिपि उदाहरण या घटना कहा जाता है। तथ्य यह है कि π में σ होता है, इसे σ ≤ π के रूप में अधिक संक्षिप्त रूप से लिखा जाता है। यदि एक क्रमचय π में कोई पैटर्न σ नहीं है, तो π को बचने σ कहा जाता है। क्रमपरिवर्तन 51342 213 से बचता है; इसमें तीन अंकों के 10 अनुगामी हैं, लेकिन इन 10 अनुगामी में से किसी का भी क्रम 213 के समान नहीं है।

प्रारंभिक परिणाम

ऐसा केस किया जा सकता है Percy MacMahon (1915) जाली क्रमपरिवर्तन के अपने अध्ययन के साथ क्षेत्र में परिणाम साबित करने वाले पहले व्यक्ति थे। विशेष रूप से मैकमोहन दिखाता है कि जिन क्रमपरिवर्तनों को दो घटते क्रमपरिवर्तनों में विभाजित किया जा सकता है (अर्थात्, 123 से बचने वाले क्रमपरिवर्तन) को कैटलन संख्याओं द्वारा गिना जाता है। इस क्षेत्र में एक और प्रारंभिक मील का पत्थर परिणाम है एर्दोस-ज़ेकेरेस प्रमेय#क्रमपरिवर्तन पैटर्न व्याख्या|एर्डोस-ज़ेकेरेस प्रमेय; क्रमपरिवर्तन पैटर्न भाषा में, प्रमेय कहता है कि किसी भी धनात्मक पूर्णांक a और b के लिए लंबाई का प्रत्येक क्रमपरिवर्तन कम से कम $(a-1)(b-1)+1$ या तो पैटर्न होना चाहिए $1,2,3,\dots ,a$ या पैटर्न $b,b-1,\dots ,2,1$.

कंप्यूटर विज्ञान की उत्पत्ति

1968 में डोनाल्ड नुथ के स्टैक-सॉर्ट करने योग्य क्रमपरिवर्तन|स्टैक-सॉर्टिंग पर विचार के साथ क्रमचय पैटर्न का अध्ययन गंभीरता से शुरू हुआ। नुथ ने दिखाया कि क्रमपरिवर्तन π को स्टैक (डेटा संरचना) द्वारा क्रमबद्ध किया जा सकता है यदि और केवल अगर π 231 से बचता है, और यह कि स्टैक-क्रमांकन योग्य क्रमपरिवर्तन कैटलन संख्याओं द्वारा गणना किए जाते हैं। नुथ ने डबल-एंडेड कतार के साथ छँटाई के बारे में भी सवाल उठाए। विशेष रूप से, नूथ का यह प्रश्न कि डेक के उपयोग से n तत्वों के कितने क्रमचय प्राप्त किए जा सकते हैं, खुला रहता है। उसके बाद शीघ्र ही, Robert Tarjan (1972) स्टैक के नेटवर्क द्वारा जांच की गई छंटाई, जबकि Vaughan Pratt (1973) ने दिखाया कि क्रमचय π को डेक द्वारा क्रमबद्ध किया जा सकता है यदि और केवल यदि सभी k के लिए, π 5,2,7,4,...,4k+1,4k−2,3,4k,1, और 5 से बचता है ,2,7,4,...,4k+3,4k,1,4k+2,3, और प्रत्येक क्रमचय जो इनमें से किसी से भी पिछले दो तत्वों या 1 और 2 को बदलकर प्राप्त किया जा सकता है। क्योंकि क्रमपरिवर्तन का यह संग्रह अनंत है (वास्तव में, यह क्रमपरिवर्तन के अनंत प्रतिश्रृंखला का पहला प्रकाशित उदाहरण है), यह तुरंत स्पष्ट नहीं है कि यह तय करने में कितना समय लगता है कि एक क्रमचय को डेक द्वारा क्रमबद्ध किया जा सकता है या नहीं। Rosenstiehl & Tarjan (1984) ने बाद में एक रेखीय (π की लंबाई में) समय एल्गोरिथ्म प्रस्तुत किया जो यह निर्धारित करता है कि क्या π को एक डेक द्वारा क्रमबद्ध किया जा सकता है। अपने पेपर में, प्रैट ने टिप्पणी की कि यह क्रमचय पैटर्न क्रम "क्रमपरिवर्तन पर एकमात्र आंशिक क्रम प्रतीत होता है जो एक सरल और प्राकृतिक तरीके से उत्पन्न होता है" और यह देखते हुए निष्कर्ष निकाला कि "एक अमूर्त दृष्टिकोण से", क्रमचय पैटर्न क्रम "है हम जिन नेटवर्कों की विशेषता बता रहे थे, उनसे भी ज्यादा दिलचस्प ”।

संख्यात्मक उत्पत्ति

Main article: Enumerations of specific permutation classes

क्रमपरिवर्तन पैटर्न के अध्ययन में एक प्रमुख लक्ष्य एक निश्चित (और आमतौर पर कम) क्रमपरिवर्तन या क्रमपरिवर्तन के सेट से बचने के क्रमपरिवर्तन की गणना में है। चलो ए.वी_n(बी) लंबाई एन के क्रमपरिवर्तन के सेट को निरूपित करता है जो सेट बी में सभी क्रमपरिवर्तनों से बचता है (मामले में बी एक सिंगलटन है, β कहें, संक्षेप एवी_n(β) इसके बजाय प्रयोग किया जाता है)। जैसा कि ऊपर उल्लेख किया गया है, मैकमोहन और नुथ ने दिखाया कि |Av_n(123) | = | बंद_n(231) | = सी_n, nवां कैटलन नंबर। इस प्रकार ये आइसोमॉर्फिक संयोजन वर्ग हैं।

Simion & Schmidt (1985) पहला पेपर था जिसमें पूरी तरह से एन्यूमरेशन पर फोकस किया गया था। अन्य परिणामों में, सिमियन और श्मिट ने लंबाई तीन के एक पैटर्न से परहेज करते हुए एक क्रमचय की समता की गणना की, विशिष्ट क्रमपरिवर्तन वर्गों की गणना से बचने वाले क्रमपरिवर्तनों की गणना की # कक्षाओं ने लंबाई 3 के दो पैटर्न से परहेज किया, और पहला विशेषण प्रमाण दिया कि 123- और 231-क्रमपरिवर्तन से बचना समतुल्य हैं। उनके पेपर के बाद से और भी कई आपत्तियां दी गई हैं, देखें Claesson & Kitaev (2008) सर्वेक्षण के लिए। सामान्य तौर पर, यदि |Av_n(β) | = | बंद_n(σ) | सभी n के लिए, फिर β और σ को विलफ समतुल्य कहा जाता है|विल्फ-समतुल्य। कई विलफ-तुल्यताएँ इस तुच्छ तथ्य से उत्पन्न होती हैं कि |Av_n(β) | = | बंद_n(बी^-1)| = | बंद_n(बी^रेव)| सभी n के लिए, जहाँ β⁻¹ क्रमचय#उत्पाद और β और β का व्युत्क्रम दर्शाता है^Rev β के विपरीत को दर्शाता है। (ये दो ऑपरेशन समूहों के उदाहरण उत्पन्न करते हैं # एक वर्ग का समरूपता समूह - क्रम 8 का डायहेड्रल समूह | डायहेड्रल समूह डी₈क्रमचय मेट्रिसेस पर एक प्राकृतिक क्रिया के साथ।) हालांकि, गैर-तुच्छ विलफ-तुल्यता के कई उदाहरण भी हैं (जैसे कि 123 और 231 के बीच):

• Stankova (1994) ने सिद्ध किया कि क्रमचय 1342 और 2413 विलफ-तुल्य हैं।
• Stankova & West (2002) ने साबित किया कि किसी भी क्रमपरिवर्तन β के लिए, क्रमपरिवर्तन 231 ⊕ β और 312 ⊕ β विल्फ-समतुल्य हैं, जहां ⊕ क्रमपरिवर्तन संचालन के प्रत्यक्ष योग को दर्शाता है।
• Backelin, West & Xin (2007) ने सिद्ध किया कि किसी भी क्रमचय β और किसी धनात्मक पूर्णांक m के लिए, क्रमचय 12..m ⊕ β और m...21 ⊕ β विलफ़-समतुल्य हैं।

इन दो विल्फ-तुल्यताओं और व्युत्क्रम और विपरीत समरूपताओं से, यह इस प्रकार है कि तीन अलग-अलग क्रम हैं।_n(β) | जहां β की लंबाई चार है:

β	sequence enumerating Avn(β)	OEIS reference	exact enumeration reference
1342	1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...	A022558	Bóna (1997)
1234	1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...	A005802	Gessel (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...	A061552	unenumerated

1980 के दशक के अंत में, रिचर्ड पी. स्टेनली और हर्बर्ट विल्फ ने अनुमान लगाया कि प्रत्येक क्रमचय β के लिए, कुछ स्थिर K ऐसा है कि |Av_n(बी) | <के^एन. एडम मार्कस (गणितज्ञ) और गैबोर टार्डोस द्वारा सिद्ध किए जाने तक इसे स्टेनली-विल्फ अनुमान के रूप में जाना जाता था।

बंद कक्षाएं

Main article: Permutation class

एक बंद वर्ग, जिसे एक पैटर्न वर्ग, क्रमपरिवर्तन वर्ग, या केवल क्रमपरिवर्तन की कक्षा के रूप में भी जाना जाता है, क्रमपरिवर्तन पैटर्न क्रम में एक आदर्श (आदेश सिद्धांत) है। प्रत्येक वर्ग को न्यूनतम क्रमचय द्वारा परिभाषित किया जा सकता है जो इसके अंदर नहीं है, इसका आधार। इस प्रकार स्टैक-सॉर्टेबल क्रमपरिवर्तन का आधार {231} है, जबकि डेक-सॉर्टेबल क्रमपरिवर्तन का आधार अनंत है। एक वर्ग के लिए जनरेटिंग फ़ंक्शन Σ x है^|π| जहां कक्षा में सभी क्रमपरिवर्तन π पर योग लिया जाता है।

मोबियस फ़ंक्शन

चूंकि रोकथाम आदेश के तहत क्रमपरिवर्तन का सेट आंशिक रूप से आदेशित सेट बनाता है, इसलिए इसकी घटना बीजगणित के बारे में पूछना स्वाभाविक है # विशेष तत्व | मोबियस फ़ंक्शन, एक लक्ष्य जिसे पहले स्पष्ट रूप से प्रस्तुत किया गया था Wilf (2002). इस तरह की जांच में लक्ष्य एक अंतराल [σ, π] के मोबियस फ़ंक्शन के लिए क्रमचय पैटर्न पोसेट में एक सूत्र खोजना है जो भोली पुनरावर्ती परिभाषा से अधिक कुशल है। इस तरह का पहला परिणाम द्वारा स्थापित किया गया था Sagan & Vatter (2006), जिन्होंने स्तरित क्रमपरिवर्तन के अंतराल के मोबियस फ़ंक्शन के लिए एक सूत्र दिया। बाद में, Burstein et al. (2011) ने इस परिणाम को वियोज्य क्रमपरिवर्तन के अंतराल के लिए सामान्यीकृत किया। यह ज्ञात है कि, स्पर्शोन्मुख रूप से, n लंबाई के सभी क्रमपरिवर्तन π का ​​कम से कम 39.95% μ(1, π)=0 को संतुष्ट करता है (अर्थात, प्रमुख मोबियस फ़ंक्शन शून्य के बराबर है), लेकिन प्रत्येक एन के लिए क्रमपरिवर्तन π मौजूद है जैसे कि μ(1, π) एन का एक घातीय कार्य है।

कम्प्यूटेशनल जटिलता

एक क्रमपरिवर्तन दिया $\tau$ (पाठ कहा जाता है) लंबाई का $n$ और दूसरा क्रमपरिवर्तन $\pi$ लंबाई का $k$ (पैटर्न कहा जाता है), क्रमपरिवर्तन पैटर्न मिलान (पीपीएम) समस्या पूछती है कि क्या $\pi$ में निहित है $\tau$. कब दोनों $n$ और $k$ चर के रूप में माना जाता है, समस्या को एनपी-पूर्ण के रूप में जाना जाता है, और ऐसे मिलानों की संख्या की गणना करने की समस्या तीव्र-पी-पूर्ण|#पी-पूर्ण है। हालाँकि, पीपीएम को रैखिक समय में हल किया जा सकता है जब k स्थिर हो। दरअसल, गुइलमोट और मार्क्स दिखाया कि पीपीएम को समय पर हल किया जा सकता है $2^{O(k^{2}\log k)}\cdot n$, जिसका अर्थ है कि यह निश्चित-पैरामीटर के संबंध में ट्रैक्टेबल है $k$.

पीपीएम समस्या पर कई प्रकार हैं, जैसा कि ब्रूनर और लैकनर द्वारा सर्वेक्षण किया गया है। उदाहरण के लिए, यदि मैच में सन्निहित प्रविष्टियों को शामिल करना आवश्यक है तो समस्या को बहुपद समय में हल किया जा सकता है। एक अन्य संस्करण तब होता है जब पैटर्न और पाठ दोनों एक उचित क्रमचय वर्ग तक सीमित होते हैं ${\mathcal {C}}$, जिस स्थिति में समस्या कहा जाता है ${\mathcal {C}}$-पीपीएम। उदाहरण के लिए, गुइलमोट और वायलेट पता चला है कि ${\mbox{Av}}(321)$-पीपीएम में हल किया जा सकता है $O(k^{2}n^{6})$ समय। माइकल एच। अल्बर्ट, लैकनर, लैकनर और वैटर बाद में इसे कम कर दिया $O(kn)$ और दिखाया कि तिरछा-विलय किए गए क्रमपरिवर्तन के वर्ग के लिए समान सीमा लागू होती है। उन्होंने आगे पूछा कि क्या ${\mathcal {C}}$-पीपीएम समस्या को हर निश्चित उचित क्रमपरिवर्तन वर्ग के लिए बहुपद समय में हल किया जा सकता है ${\mathcal {C}}$.

पैकिंग घनत्व

क्रमचय π को β-इष्टतम कहा जाता है यदि π के समान लंबाई का कोई क्रमचय नहीं है जिसमें β की अधिक प्रतियां हैं। 1992 में असतत गणित पर SIAM की बैठक में अपने संबोधन में, विल्फ ने लंबाई k के क्रमचय β के पैकिंग घनत्व को परिभाषित किया

$\lim _{n\rightarrow \infty }{\frac {{\text{number of copies of }}\beta {\text{ in a }}\beta {\text{-optimal permutation of length }}n}{\displaystyle {n \choose k}}}.$

फ्रेड गैल्विन के एक अप्रकाशित तर्क से पता चलता है कि अनुक्रम की इस सीमा के भीतर की मात्रा n ≥ k के लिए गैर-बढ़ती है, और इसलिए सीमा मौजूद है। जब β मोनोटोन होता है, तो इसका पैकिंग घनत्व स्पष्ट रूप से 1 होता है, और पैकिंग घनत्व व्युत्क्रम और रिवर्स द्वारा उत्पन्न समरूपता के समूह के अंतर्गत अपरिवर्तनीय होते हैं, इसलिए लंबाई तीन के क्रमपरिवर्तन के लिए, केवल एक गैर-तुच्छ पैकिंग घनत्व होता है। वाल्टर स्ट्रोमक्विस्ट (अप्रकाशित) ने यह दिखाकर इस मामले को सुलझाया कि 132 की पैकिंग घनत्व 2 है√3 − 3, लगभग 0.46410।

लंबाई चार के क्रमपरिवर्तन β के लिए, (समरूपता के कारण) विचार करने के लिए सात मामले हैं:

β	packing density	reference
1234	1	trivial
1432	root of x3 − 12x2 + 156x − 64 ≅ 0.42357	Price (1997)
2143	⅜ = 0.375	Price (1997)
1243	⅜ = 0.375	Albert et al. (2002)
1324	conjectured to be ≅ 0.244
1342	conjectured to be ≅ 0.19658
2413	conjectured to be ≅ 0.10474

तीन अज्ञात क्रमचय के लिए सीमाएँ और अनुमान हैं। Price (1997) ने एक सन्निकटन एल्गोरिथम का उपयोग किया जो बताता है कि 1324 का पैकिंग घनत्व लगभग 0.244 है। बिर्जन बटकेयेव (अप्रकाशित) ने क्रमपरिवर्तन के एक परिवार का निर्माण किया, जिसमें दिखाया गया है कि 1342 का पैकिंग घनत्व कम से कम 132 और 1432 के पैकिंग घनत्व का उत्पाद है, लगभग 0.19658। यह 1342 की सटीक पैकिंग घनत्व होने का अनुमान है। Presutti & Stromquist (2010) ने 2413 के पैकिंग घनत्व पर एक निचली सीमा प्रदान की। यह निचली सीमा, जिसे एक अभिन्न के रूप में व्यक्त किया जा सकता है, लगभग 0.10474 है, और वास्तविक पैकिंग घनत्व होने का अनुमान लगाया गया है।

सुपरपैटर्न

Main article: Superpattern

एक k-'सुपरपैटर्न' एक क्रमचय है जिसमें लंबाई k के सभी क्रमपरिवर्तन शामिल हैं। उदाहरण के लिए, 25314 एक 3-सुपरपैटर्न है क्योंकि इसमें लंबाई 3 के सभी 6 क्रमपरिवर्तन शामिल हैं। यह ज्ञात है कि k-सुपरपैटर्न की लंबाई कम से कम k होनी चाहिए।²/ई², जहां e ≈ 2.71828 e (गणितीय स्थिरांक) है|यूलर की संख्या, और यह कि लंबाई ⌈(k.) के k-सुपरपैटर्न मौजूद हैं² + 1)/2⌉. यह ऊपरी सीमा निचले क्रम की शर्तों तक सर्वोत्तम संभव होने का अनुमान लगाया गया है।

सामान्यीकरण

ऐसे कई तरीके हैं जिनमें पैटर्न की धारणा को सामान्यीकृत किया गया है। उदाहरण के लिए, एक विनकुलर पैटर्न एक क्रमचय है जिसमें डैश होते हैं जो प्रविष्टियों को इंगित करते हैं जो लगातार होने की आवश्यकता नहीं होती है (सामान्य पैटर्न परिभाषा में, कोई प्रविष्टि लगातार होने की आवश्यकता नहीं होती है)। उदाहरण के लिए, क्रमपरिवर्तन 314265 में धराशायी पैटर्न 2-31-4 की दो प्रतियां हैं, जो 3426 और 3425 प्रविष्टियों द्वारा दी गई हैं। धराशायी पैटर्न β और किसी भी क्रमपरिवर्तन π के लिए, हम β की प्रतियों की संख्या के लिए β(π) लिखते हैं। π में। इस प्रकार π में व्युत्क्रमों की संख्या 2-1(π) है, जबकि अवरोहण की संख्या 21(π) है। आगे जाकर, π में घाटियों की संख्या 213(π) + 312(π) है, जबकि चोटियों की संख्या 231(π) + 132(π) है। ये पैटर्न द्वारा पेश किए गए थे Babson & Steingrímsson (2000), जिन्होंने दिखाया कि लगभग सभी ज्ञात Mahonian आँकड़े vincular permutations के संदर्भ में व्यक्त किए जा सकते हैं। उदाहरण के लिए, π का ​​प्रमुख सूचकांक 1-32(π) + 2-31(π) + 3-21(π) + 21(π) के बराबर है।

एक अन्य सामान्यीकरण वर्जित पैटर्न का है, जिसमें कुछ प्रविष्टियाँ वर्जित हैं। π के लिए वर्जित पैटर्न से बचने के लिए β का अर्थ है कि π की प्रविष्टियों का प्रत्येक सेट जो β की गैर-वर्जित प्रविष्टियों की प्रतिलिपि बनाता है, को β की सभी प्रविष्टियों की प्रतिलिपि बनाने के लिए बढ़ाया जा सकता है। West (1993) ने क्रमचय के अपने अध्ययन में इस प्रकार के पैटर्न पेश किए जिन्हें एक ढेर के माध्यम से दो बार पास करके क्रमबद्ध किया जा सकता है। (ध्यान दें कि स्टैक के माध्यम से दो बार सॉर्ट करने की पश्चिम की परिभाषा श्रृंखला में दो स्टैक्स के साथ सॉर्ट करने के समान नहीं है।) वर्जित पैटर्न का एक और उदाहरण के काम में होता है Bousquet-Mélou & Butler (2007), जिन्होंने दिखाया कि π के अनुरूप शूबर्ट विविधता Schubert किस्म है#स्थानीय रूप से फैक्टोरियल अगर और केवल अगर π 1324 और 21 से बचता है354.

बाहरी संबंध

A conference on permutation patterns has been held annually since 2003:

1. Permutation Patterns 2003, February 10–14, 2003, University of Otago, Dunedin, New Zealand.
2. Permutation Patterns 2004, July 5–9, 2004, Malaspina University-College, Nanaimo, British Columbia, Canada.
3. Permutation Patterns 2005, March 7–11, 2005, University of Florida, Gainesville, Florida, USA.
4. Permutation Patterns 2006, June 12–16, 2006, Reykjavík University, Reykjavík, Iceland.
5. Permutation Patterns 2007, June 11–15, 2007, University of St. Andrews, St. Andrews, Scotland.
6. Permutation Patterns 2008, June 16–20, 2008, University of Otago, Dunedin, New Zealand.
7. Permutation Patterns 2009, July 13–17, 2009, Università di Firenze, Florence, Italy.
8. Permutation Patterns 2010, August 9–13, 2010, Dartmouth College, Hanover, New Hampshire, USA.
9. Permutation Patterns 2011, June 20–24, 2011, California Polytechnic State University, San Luis Obispo, California, USA.
10. Permutation Patterns 2012, June 11–15, 2012, University of Strathclyde, Glasgow, Scotland.
11. Permutation Patterns 2013, July 1–5, 2013, Université Paris Diderot, Paris, France.
12. Permutation Patterns 2014, July 7–11, 2014, East Tennessee State University, Johnson City, Tennessee, USA.
13. Permutation Patterns 2015, June 15–19, 2015, De Morgan House, London, England.
14. Permutation Patterns 2016, June 27–July 1, 2016, Howard University, Washington, DC, USA.
15. Permutation Patterns 2017, June 26–30, 2017, Reykjavík University, Reykjavík, Iceland.
16. Permutation Patterns 2018, July 9–13, 2018, Dartmouth College, Hanover, New Hampshire, USA.
17. Permutation Patterns 2019, June 17–21, 2019, Universität Zürich, Zürich, Switzerland.
18. Permutation Patterns 2020 Virtual Workshop, June 30–July 1, 2020, hosted by Valparaiso University, Valparaiso, Indiana, USA.
19. Permutation Patterns 2021 Virtual Workshop, June 15–16, 2021, hosted by University of Strathclyde, Glasgow, Scotland.
20. Permutation Patterns 2022, June 20-24, 2022, Valparaiso University, Valparaiso, Indiana, USA.
21. Permutation Patterns 2023, July 3-7, 2023, University of Burgundy, Dijon, France.

American Mathematical Society Special Sessions on Patterns in Permutations have been held at the following meetings:

• Fall Eastern Sectional Meeting, September 22–23, 2012, Rochester Institute of Technology, Rochester, NY.
• Joint Mathematics Meetings, January 12, 2013, San Diego, CA.
• Central Fall Sectional Meeting, September 20–21, 2014, University of Wisconsin-Eau Claire, Eau Claire, WI.
• Spring Eastern Sectional Meeting, March 7–8, 2015, Georgetown University, Washington, DC.

Other permutation patterns meetings:

• Workshop on Permutation Patterns, May 29–June 3, 2005, University of Haifa, Haifa, Israel.
• Pattern Avoidance and Genome Sorting, February 14-19, 2016, Schloss Dagstuhl, Wadern, Germany.
• Genomics, Pattern Avoidance, and Statistical Mechanics, November 4-9, 2018, Schloss Dagstuhl, Wadern, Germany.
• Pattern Avoidance, Statistical Mechanics and Computational Complexity, March 19-24, 2023, Schloss Dagstuhl, Wadern, Germany.

Other links:

• PermLab: software for permutation patterns, maintained by Michael Albert.
• Database of Permutation Pattern Avoidance, maintained by Bridget Tenner.
• PermPAL: The Permutation Pattern Avoidance Library, a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.