क्रमपरिवर्तन पैटर्न: Difference between revisions

From Vigyanwiki
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
साहचर्य गणित और सैद्धांतिक कंप्यूटर विज्ञान में, एक क्रमचय प्रतिमान एक लंबे क्रमचय का उप-क्रमचय है। किसी भी क्रमचय को एक-पंक्ति संकेतन में अंकों के अनुक्रम के रूप में लिखा जा सकता है, जो अंक क्रम 123... पर क्रमचय प्रयुक्त करने के परिणाम का प्रतिनिधित्व करता है; उदाहरण के लिए अंक अनुक्रम 213 तीन तत्वों पर क्रमचय का प्रतिनिधित्व करता है जो तत्वों 1 और 2 को विनिमय करता है। यदि π और σ इस तरह से प्रदर्शित दो क्रमचय हैं (ये परिवर्तनीय नाम क्रमचय के लिए मानक हैं और संख्या <math>\pi</math> से संबंधित नहीं हैं), तो π एक प्रतिमान के रूप में σ समाहित करने के लिए कहा जाता है यदि π के अंकों के कुछ क्रम में σ के सभी अंकों के समान सापेक्षिक क्रम हो।
साहचर्य गणित और सैद्धांतिक कंप्यूटर विज्ञान में, '''क्रमचय पैटर्न''' एक लंबे क्रमचय का उप-क्रमचय है। किसी भी क्रमचय को एक-पंक्ति संकेतन में अंकों के अनुक्रम के रूप में लिखा जा सकता है, जो अंक क्रम 123... पर क्रमचय प्रयुक्त करने के परिणाम का प्रतिनिधित्व करता है; उदाहरण के लिए अंक अनुक्रम 213 तीन तत्वों पर क्रमचय का प्रतिनिधित्व करता है जो तत्वों 1 और 2 को विनिमय करता है। यदि π और σ इस तरह से प्रदर्शित दो क्रमचय हैं (ये परिवर्तनीय नाम क्रमचय के लिए मानक हैं और संख्या <math>\pi</math> से संबंधित नहीं हैं), तो π एक पैटर्न के रूप में σ समाहित करने के लिए कहा जाता है यदि π के अंकों के कुछ क्रम में σ के सभी अंकों के समान सापेक्षिक क्रम हो।


उदाहरण के लिए, क्रमचय π में प्रतिमान 213 होता है जब भी π में तीन अंक x, y, और z होते हैं जो क्रम xy...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 के समान नहीं है।
उदाहरण के लिए, क्रमचय π में पैटर्न 213 होता है जब भी π में तीन अंक x, y, और z होते हैं जो क्रम xy...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 के समान नहीं है।


== प्रारंभिक परिणाम ==
== प्रारंभिक परिणाम ==
ऐसी स्थिति बनाई जा सकती है कि पर्सी मैकमोहन (1915) लैटिस क्रमचय के अपने अध्ययन के साथ क्षेत्र में परिणाम प्रमाणित करने वाले पहले व्यक्ति थे।<ref>{{ Citation
ऐसी स्थिति बनाई जा सकती है कि पर्सी मैकमोहन (1915) लैटिस क्रमचय के अपने अध्ययन के साथ क्षेत्र में परिणाम प्रमाणित करने वाले पहले व्यक्ति थे।<ref>{{ Citation
  | last=MacMahon
  | last=MacMahon
  | first=Percy A.
  | first=Percy A.
Line 15: Line 15:
}}.</ref> विशेष रूप से मैकमोहन दिखाता है कि जिन क्रमपरिवर्तनों को दो घटते क्रमपरिवर्तनों में विभाजित किया जा सकता है (अर्थात्, 123 से परिहरण करने वाले क्रमचय) को [[कैटलन संख्या]]ओं द्वारा गणना किए जाते है।<ref>{{harvtxt|MacMahon|1915}}, Items 97 and 98.</ref>
}}.</ref> विशेष रूप से मैकमोहन दिखाता है कि जिन क्रमपरिवर्तनों को दो घटते क्रमपरिवर्तनों में विभाजित किया जा सकता है (अर्थात्, 123 से परिहरण करने वाले क्रमचय) को [[कैटलन संख्या]]ओं द्वारा गणना किए जाते है।<ref>{{harvtxt|MacMahon|1915}}, Items 97 and 98.</ref>


इस क्षेत्र में एक और प्रारंभिक ऐतिहासिक परिणाम एर्डोस-ज़ेकेरेस प्रमेय है; क्रमचय प्रतिमान भाषा में, प्रमेय कहता है कि किसी भी धनात्मक पूर्णांक a और b के लिए लंबाई का प्रत्येक क्रमचय कम से कम <math>(a-1)(b-1) + 1 </math> या तो प्रतिमान  <math>1, 2, 3,\dots , a  </math> या प्रतिमान <math>b,b-1,\dots , 2, 1</math> होना चाहिए।  
इस क्षेत्र में एक और प्रारंभिक ऐतिहासिक परिणाम एर्डोस-ज़ेकेरेस प्रमेय है; क्रमचय पैटर्न भाषा में, प्रमेय कहता है कि किसी भी धनात्मक पूर्णांक a और b के लिए लंबाई का प्रत्येक क्रमचय कम से कम <math>(a-1)(b-1) + 1 </math> या तो पैटर्न <math>1, 2, 3,\dots , a  </math> या पैटर्न <math>b,b-1,\dots , 2, 1</math> होना चाहिए।  


== कंप्यूटर विज्ञान की उत्पत्ति ==
== कंप्यूटर विज्ञान की उत्पत्ति ==
क्रमपरिवर्तन प्रतिरूप का अध्ययन 1968 में डोनाल्ड नुथ के स्टैक- वर्गीकरण पर विचार के साथ गंभीरता से प्रारंभ हुआ।<ref>{{ Citation
क्रमचय पैटर्न का अध्ययन 1968 में डोनाल्ड नुथ के स्टैक- वर्गीकरण पर विचार के साथ महत्वपूर्ण रूप से प्रारंभ हुआ।<ref>{{ Citation
  | last=Knuth
  | last=Knuth
  | first=Donald E.
  | first=Donald E.
Line 28: Line 28:
  | isbn=0-201-89683-4
  | isbn=0-201-89683-4
  | oclc=155842391
  | oclc=155842391
  | mr= 0286317}}..</ref> नुथ ने दिखाया कि क्रमचय π को स्टैक (डेटा संरचना) द्वारा क्रमबद्ध किया जा सकता है यदि और केवल यदि π 231 से परिहरण करता है, और यह कि स्टैक-क्रमांकन योग्य क्रमचय कैटलन संख्याओं द्वारा गणना किए जाते हैं।<ref>{{harvtxt|Knuth|1968}}, Section 2.2.1, Exercises 4 and 5.</ref> नुथ ने डेक के साथ प्रवरण के बारे में भी सवाल प्रस्तुत किए। विशेष रूप से, नूथ का यह प्रश्न कि डेक के उपयोग से n तत्वों के कितने क्रमचय प्राप्त किए जा सकते हैं, और संवृत रहता है।<ref>{{harvtxt|Knuth|1968}}, Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.</ref> उसके बाद शीघ्र ही, रॉबर्ट टारजन (1972) स्टैक के नेटवर्क द्वारा प्रवरण की जांच की गई,<ref>{{Citation | last1=Tarjan | first1=Robert | author1-link=Robert Tarjan | title=Sorting using networks of queues and stacks | mr = 0298803 | year=1972 | journal=[[Journal of the ACM]] | volume=19 | issue=2 | pages=341–346 | doi = 10.1145/321694.321704| s2cid=13608929 }}.</ref> जबकि वॉन प्रैट (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 को बदलकर प्राप्त किया जा सकता है।<ref name="pratt73">{{Citation | last1=Pratt | first1=Vaughan R. | author1-link=Vaughan Pratt | contribution=Computing permutations with double-ended queues. Parallel stacks and parallel queues |mr = 0489115 | year=1973 | title=[[Symposium on Theory of Computing|Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973)]] | pages=268–277 | doi = 10.1145/800125.804058| s2cid=15740957 | doi-access=free }}.</ref> क्योंकि क्रमपरिवर्तन का यह संग्रह अनंत है (वास्तव में, यह क्रमपरिवर्तन के अनंत प्रतिश्रृंखला का पहला प्रकाशित उदाहरण है), यह तुरंत स्पष्ट नहीं है कि यह निर्धारित करने में कितना समय लगता है कि एक क्रमचय को डेक द्वारा क्रमबद्ध किया जा सकता है या नहीं किया जा सकता है। रोसेनस्टीहल और टार्जन (1984) ने बाद में एक रेखीय (π की लंबाई में) समय एल्गोरिथ्म प्रस्तुत किया जो यह निर्धारित करता है कि क्या π को एक डेक द्वारा क्रमबद्ध किया जा सकता है<ref>{{Citation | last1=Rosenstiehl | first1=Pierre | author1-link=Pierre Rosenstiehl | last2=Tarjan | first2=Robert | author2-link=Robert Tarjan | title=Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations | mr = 756164 | year=1984 | journal=Journal of Algorithms | volume=5 | issue=3 | pages=375–390 | doi = 10.1016/0196-6774(84)90018-X}}.</ref>
  | mr= 0286317}}..</ref> नुथ ने दिखाया कि क्रमचय π को स्टैक (डेटा संरचना) द्वारा क्रमबद्ध किया जा सकता है यदि और केवल यदि π 231 से परिहरण करता है, और यह कि स्टैक-क्रमांकन योग्य क्रमचय कैटलन संख्याओं द्वारा गणना किए जाते हैं।<ref>{{harvtxt|Knuth|1968}}, Section 2.2.1, Exercises 4 and 5.</ref> नुथ ने डेक के साथ संकलन के बारे में भी सवाल प्रस्तुत किए। विशेष रूप से, नूथ का यह प्रश्न कि डेक के उपयोग से n तत्वों के कितने क्रमचय प्राप्त किए जा सकते हैं, और संवृत रहता है।<ref>{{harvtxt|Knuth|1968}}, Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.</ref> उसके बाद शीघ्र ही, रॉबर्ट टारजन (1972) स्टैक के नेटवर्क द्वारा संकलन की जांच की गई,<ref>{{Citation | last1=Tarjan | first1=Robert | author1-link=Robert Tarjan | title=Sorting using networks of queues and stacks | mr = 0298803 | year=1972 | journal=[[Journal of the ACM]] | volume=19 | issue=2 | pages=341–346 | doi = 10.1145/321694.321704| s2cid=13608929 }}.</ref> जबकि वॉन प्रैट (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 को परिवर्तित करके प्राप्त किया जा सकता है।<ref name="pratt73">{{Citation | last1=Pratt | first1=Vaughan R. | author1-link=Vaughan Pratt | contribution=Computing permutations with double-ended queues. Parallel stacks and parallel queues |mr = 0489115 | year=1973 | title=[[Symposium on Theory of Computing|Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973)]] | pages=268–277 | doi = 10.1145/800125.804058| s2cid=15740957 | doi-access=free }}.</ref> क्योंकि क्रमचय का यह संग्रह अनंत है (वास्तव में, यह क्रमचय के अनंत प्रतिश्रृंखला का पहला प्रकाशित उदाहरण है), यह तुरंत स्पष्ट नहीं है कि यह निर्धारित करने में कितना समय लगता है कि एक क्रमचय को डेक द्वारा क्रमबद्ध किया जा सकता है या नहीं किया जा सकता है। रोसेनस्टीहल और टार्जन (1984) ने बाद में एक रेखीय (π की लंबाई में) समय एल्गोरिथ्म प्रस्तुत किया जो यह निर्धारित करता है कि क्या π को एक डेक द्वारा क्रमबद्ध किया जा सकता है<ref>{{Citation | last1=Rosenstiehl | first1=Pierre | author1-link=Pierre Rosenstiehl | last2=Tarjan | first2=Robert | author2-link=Robert Tarjan | title=Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations | mr = 756164 | year=1984 | journal=Journal of Algorithms | volume=5 | issue=3 | pages=375–390 | doi = 10.1016/0196-6774(84)90018-X}}.</ref>


अपने पत्र में, प्रैट ने टिप्पणी की कि यह क्रमचय प्रतिमान क्रम "क्रमचय पर एकमात्र आंशिक क्रम प्रतीत होता है जो एक सरल और प्राकृतिक तरीके से उत्पन्न होता है" और यह देखते हुए निष्कर्ष निकाला कि "एक अमूर्त दृष्टिकोण से", क्रमचय प्रतिमान क्रम "हम जिन नेटवर्कों की विशेषता बता रहे थे, उनसे कहीं अधिक रोचक है”।<ref name="pratt73" />
अपने पत्र में, प्रैट ने टिप्पणी की कि यह क्रमचय पैटर्न क्रम "क्रमचय पर एकमात्र आंशिक क्रम प्रतीत होता है जो एक सरल और प्राकृतिक तरीके से उत्पन्न होता है" और यह देखते हुए निष्कर्ष निकाला कि "एक अमूर्त दृष्टिकोण से", क्रमचय पैटर्न क्रम "हम जिन नेटवर्कों की विशेषता बता रहे थे, उनसे कहीं अधिक रोचक है”।<ref name="pratt73" />






== '''edit''' संख्यात्मक उत्पत्ति ==
== परिगणनात्‍मक उत्पत्ति ==
{{main article|Enumerations of specific permutation classes}}
{{main article|विशिष्ट क्रमचय वर्गों की गणना}}
क्रमचय प्रतिमान के अध्ययन में एक प्रमुख लक्ष्य एक निश्चित (और आमतौर पर कम) क्रमचय या क्रमचय के सेट से परिहरण करने के क्रमचय की गणना में है। चलो ए.वी<sub>n</sub>(बी) लंबाई एन के क्रमचय के सेट को निरूपित करता है जो सेट बी में सभी क्रमपरिवर्तनों से बचता है (मामले में बी एक सिंगलटन है, β कहें, संक्षेप एवी<sub>n</sub>(β) इसके बजाय प्रयोग किया जाता है)। जैसा कि ऊपर उल्लेख किया गया है, मैकमोहन और नुथ ने दिखाया कि |Av<sub>n</sub>(123) | = | बंद<sub>n</sub>(231) | = सी<sub>n</sub>, nवां कैटलन नंबर। इस प्रकार ये आइसोमॉर्फिक [[संयोजन वर्ग]] हैं।


{{harvtxt|Simion|Schmidt|1985}} पहला पेपर था जिसमें पूरी तरह से एन्यूमरेशन पर फोकस किया गया था। अन्य परिणामों में, सिमियन और श्मिट ने लंबाई तीन के एक प्रतिमान से परहेज करते हुए एक क्रमचय की समता की गणना की, विशिष्ट क्रमचय वर्गों की गणना से परिहरण करने वाले क्रमपरिवर्तनों की गणना की # कक्षाओं ने लंबाई 3 के दो प्रतिमान से परहेज किया, और पहला विशेषण प्रमाण दिया कि 123- और 231-क्रमचय से बचना समतुल्य हैं।<ref>{{Citation
क्रमचय पैटर्न के अध्ययन में एक प्रमुख लक्ष्य एक निश्चित (और सामान्य रूप से कम) क्रमचय या क्रमचय के समूह से अलग करने के क्रमचय की गणना में है। मान लीजिए कि ''Av<sub>n</sub>''(B) लंबाई n के क्रमचय के समूह को निरूपित करते हैं जो समूह B में सभी क्रमचय से अलग होते हैं (स्थिति में B एक एकल है, इसके अतिरिक्त संक्षिप्त नाम ''Av<sub>n</sub>''(B) का उपयोग किया जाता है)। जैसा कि ऊपर उल्लेख किया गया है, मैकमोहन और नुथ ने दिखाया कि |''Av<sub>n</sub>''(123)| = |''Av<sub>n</sub>''(231)| = ''C<sub>n,</sub>'' nवी कैटलन संख्या है। इस प्रकार ये समरूपी संचयविन्यास वर्ग हैं।
 
सिमोन एंड श्मिट (1985) पहला पत्र था जिसमें केवल गणना पर ध्यान केंद्रित किया गया था। अन्य परिणामों में, सिमिओन और श्मिट ने लंबाई तीन के एक पैटर्न से परिहार करते हुए सम और विषम क्रमपरिवर्तनों की गणना की, लंबाई तीन के दो प्रतिरूपों से परिहरण क्रमपरिवर्तनों की गणना की, और पहला विशेषण प्रमाण दिया कि 123- और 231-परिहार क्रमचय समतुल्य हैं।<ref>{{Citation
| last1=Simion | first1=Rodica | author1-link = Rodica Simion
| last1=Simion | first1=Rodica | author1-link = Rodica Simion
| last2=Schmidt | first2=Frank W.
| last2=Schmidt | first2=Frank W.
Line 49: Line 50:
  | doi=10.1016/s0195-6698(85)80052-4
  | doi=10.1016/s0195-6698(85)80052-4
| doi-access=free
| doi-access=free
}}.</ref> उनके पेपर के बाद से और भी कई आपत्तियां दी गई हैं, देखें {{harvtxt|Claesson|Kitaev|2008}} सर्वेक्षण के लिए।<ref>{{Citation| last1=Claesson | first1=Anders| last2=Kitaev | first2=Sergey| arxiv = 0805.1325| title=Classification of bijections between 321- and 132-avoiding permutations| year=2008| journal=[[Séminaire Lotharingien de Combinatoire]]| url = http://www.emis.de/journals/SLC/wpapers/s60claekit.pdf| volume=60| pages=B60d| mr = 2465405}}.</ref>
}}.</ref> उनके पत्र के बाद से, कई अन्य आक्षेप दिए गए हैं, सर्वेक्षण के लिए क्लेसन एंड किताएव (2008) देखें।<ref>{{Citation| last1=Claesson | first1=Anders| last2=Kitaev | first2=Sergey| arxiv = 0805.1325| title=Classification of bijections between 321- and 132-avoiding permutations| year=2008| journal=[[Séminaire Lotharingien de Combinatoire]]| url = http://www.emis.de/journals/SLC/wpapers/s60claekit.pdf| volume=60| pages=B60d| mr = 2465405}}.</ref>
सामान्य तौर पर, यदि |Av<sub>n</sub>(β) | = | बंद<sub>n</sub>(σ) | सभी n के लिए, फिर β और σ को विलफ समतुल्य कहा जाता है|विल्फ-समतुल्य। कई विलफ-तुल्यताएँ इस तुच्छ तथ्य से उत्पन्न होती हैं कि |Av<sub>n</sub>(β) | = | बंद<sub>n</sub>(बी<sup>-1</sup>)| = | बंद<sub>n</sub>(बी<sup>रेव</sup>)| सभी n के लिए, जहाँ β<sup>−1</sup> क्रमचय#उत्पाद और β और β का व्युत्क्रम दर्शाता है<sup>Rev</sup> β के विपरीत को दर्शाता है। (ये दो ऑपरेशन समूहों के उदाहरण उत्पन्न करते हैं # एक वर्ग का समरूपता समूह - क्रम 8 का डायहेड्रल समूह | डायहेड्रल समूह डी<sub>8</sub>क्रमचय मेट्रिसेस पर एक प्राकृतिक क्रिया के साथ।) हालांकि, गैर-तुच्छ विलफ-तुल्यता के कई उदाहरण भी हैं (जैसे कि 123 और 231 के बीच):


* {{harvtxt|Stankova|1994}} ने सिद्ध किया कि क्रमचय 1342 और 2413 विलफ-तुल्य हैं।<ref>{{Citation | last1=Stankova | first1=Zvezdelina | title=Forbidden subsequences | mr = 1297387 | year=1994 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] | volume=132 | issue=1–3 | pages=291–316 | doi = 10.1016/0012-365X(94)90242-9| doi-access=free }}.</ref>
सामान्य रूप से, यदि |''Av<sub>n</sub>''(''β'')| = |''Av<sub>n</sub>''(''σ'')| सभी n के लिए, तब β और σ को विलफ-तुल्य कहा जाता है। कई विल्फ-तुल्यताएँ सामान्य तथ्य से उत्पन्न होती हैं कि |''Av<sub>n</sub>''(''β'')| = |''Av<sub>n</sub>''(''β''<sup>−1</sup>)| = |''Av<sub>n</sub>''(''β''<sup>rev</sup>)| सभी n के लिए, जहां β−1 β के व्युत्क्रम को दर्शाता है और ''β''<sup>rev</sup> β के व्युत्क्रम को दर्शाता है। (ये दो संक्रिया क्रमचय आव्यूहों पर एक प्राकृतिक क्रिया के साथ द्वितल समूह D8 उत्पन्न करते हैं।) हालांकि, गैर-सामान्य विल्फ-समतुल्यता के कई उदाहरण भी हैं (जैसे कि 123 और 231 के बीच):
* {{harvtxt|Stankova|West|2002}} ने प्रमाणित किया कि किसी भी क्रमचय β के लिए, क्रमचय 231 ⊕ β और 312 ⊕ β विल्फ-समतुल्य हैं, जहां ⊕ क्रमचय संचालन के प्रत्यक्ष योग को दर्शाता है।<ref>{{Citation | last1=Stankova | first1=Zvezdelina | last2=West | first2=Julian | title=A New class of Wilf-Equivalent Permutations | mr = 1900628 | year=2002 | journal=[[Journal of Algebraic Combinatorics]] | volume=15 | issue=3 | pages=271–290 | doi = 10.1023/A:1015016625432| arxiv=math/0103152 | s2cid=13921676 }}.</ref>
 
* {{harvtxt|Backelin|West|Xin|2007}} ने सिद्ध किया कि किसी भी क्रमचय β और किसी धनात्मक पूर्णांक m के लिए, क्रमचय 12..m ⊕ β और m...21 ⊕ β विलफ़-समतुल्य हैं।<ref>{{citation | last1=Backelin | first1=Jörgen | last2=West | first2=Julian | last3=Xin | first3=Guoce | title=Wilf-equivalence for singleton classes  
* स्टैंकोवा (1994) ने प्रमाणित किया कि क्रमचय 1342 और 2413 विलफ-समतुल्य हैं।<ref>{{Citation | last1=Stankova | first1=Zvezdelina | title=Forbidden subsequences | mr = 1297387 | year=1994 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] | volume=132 | issue=1–3 | pages=291–316 | doi = 10.1016/0012-365X(94)90242-9| doi-access=free }}.</ref>
* स्टैंकोवा और वेस्ट (2002) ने प्रमाणित किया कि किसी भी क्रमचय β के लिए, क्रमचय 231 ⊕ β और 312 ⊕ β विल्फ-समतुल्य हैं, जहां ⊕ क्रमचय संचालन के प्रत्यक्ष योग को दर्शाता है।<ref>{{Citation | last1=Stankova | first1=Zvezdelina | last2=West | first2=Julian | title=A New class of Wilf-Equivalent Permutations | mr = 1900628 | year=2002 | journal=[[Journal of Algebraic Combinatorics]] | volume=15 | issue=3 | pages=271–290 | doi = 10.1023/A:1015016625432| arxiv=math/0103152 | s2cid=13921676 }}.</ref>
* बैकेलिन, वेस्ट एंड शिन (2007) ने सिद्ध किया कि किसी भी क्रमचय β और किसी धनात्मक पूर्णांक m के लिए, क्रमचय 12..m ⊕ β और m...21 ⊕ β विलफ़-समतुल्य हैं।<ref>{{citation | last1=Backelin | first1=Jörgen | last2=West | first2=Julian | last3=Xin | first3=Guoce | title=Wilf-equivalence for singleton classes  
  | mr = 2290807 | year=2007 | journal=[[Advances in Applied Mathematics]] | volume=38 | issue=2 | pages=133–149 | doi = 10.1016/j.aam.2004.11.006| doi-access=free }}.</ref>
  | mr = 2290807 | year=2007 | journal=[[Advances in Applied Mathematics]] | volume=38 | issue=2 | pages=133–149 | doi = 10.1016/j.aam.2004.11.006| doi-access=free }}.</ref>
इन दो विल्फ-तुल्यताओं और व्युत्क्रम और विपरीत समरूपताओं से, यह इस प्रकार है कि तीन अलग-अलग क्रम हैं।<sub>n</sub>(β) | जहां β की लंबाई चार है:
इन दो विलफ-तुल्यताओं और व्युत्क्रम और विपरीत समरूपताओं से, यह इस प्रकार है कि तीन अलग-अलग क्रम |''Av<sub>n</sub>''(''β'')| हैं, जहां β की लंबाई चार है:


{| class="wikitable" style="text-align:center;" border="1"
{| class="wikitable" style="text-align:center;" border="1"
|-
|-
! ''β'' !! sequence enumerating ''Av<sub>n</sub>''(''β'') !! [[On-Line Encyclopedia of Integer Sequences|OEIS]] reference !! exact enumeration reference
! ''β'' !! ''Av<sub>n</sub>''(''β'') की अनुक्रम गणना !! ओईआईएस संदर्भ !! परिशुद्ध गणना संदर्भ
|-
|-
| &nbsp;1342&nbsp; || 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ... || {{OEIS link|id=A022558}} || {{harvtxt|Bóna|1997}}<ref>{{citation | last1=Bóna | first1=Miklós | authorlink = Miklós Bóna |title=Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps | mr = 1485138 | year=1997 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=80 | issue=2 | pages=257–272 | doi = 10.1006/jcta.1997.2800| arxiv=math/9702223 | s2cid=18352890 }}.</ref>
| &nbsp;1342&nbsp; || 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ... || {{OEIS link|id=A022558}} || {{harvtxt|बोना|1997}}<ref>{{citation | last1=Bóna | first1=Miklós | authorlink = Miklós Bóna |title=Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps | mr = 1485138 | year=1997 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=80 | issue=2 | pages=257–272 | doi = 10.1006/jcta.1997.2800| arxiv=math/9702223 | s2cid=18352890 }}.</ref>
|-
|-
| &nbsp;1234&nbsp; || 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... || {{OEIS link|id=A005802}} || {{harvtxt|Gessel|1990}}<ref name="gessel90">{{Citation | last1=Gessel | first1=Ira M. | title=Symmetric functions and ''P''-recursiveness | mr = 1041448 | year=1990 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=53 | issue=2 | pages=257–285 | doi = 10.1016/0097-3165(90)90060-A| doi-access=free }}.</ref>
| &nbsp;1234&nbsp; || 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... || {{OEIS link|id=A005802}} || {{harvtxt|गेसल|1990}}<ref name="gessel90">{{Citation | last1=Gessel | first1=Ira M. | title=Symmetric functions and ''P''-recursiveness | mr = 1041448 | year=1990 | journal=[[Journal of Combinatorial Theory]]|series= Series A | volume=53 | issue=2 | pages=257–285 | doi = 10.1016/0097-3165(90)90060-A| doi-access=free }}.</ref>
|-
|-
| &nbsp;1324&nbsp; || 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... || {{OEIS link|id=A061552}} || unenumerated
| &nbsp;1324&nbsp; || 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... || {{OEIS link|id=A061552}} || अगणित
|}
|}
1980 के दशक के अंत में, रिचर्ड पी. स्टेनली और [[हर्बर्ट विल्फ]] ने अनुमान लगाया कि प्रत्येक क्रमचय β के लिए, कुछ स्थिर K ऐसा है कि |Av<sub>n</sub>(बी) | <के<sup>एन</sup>. [[एडम मार्कस (गणितज्ञ)]] और गैबोर टार्डोस द्वारा सिद्ध किए जाने तक इसे स्टेनली-विल्फ अनुमान के रूप में जाना जाता था।<ref>{{Citation | last1=Marcus | first1=Adam | last2=Tardos | first2= Gábor | author2-link=Gábor Tardos | title=Excluded permutation matrices and the Stanley-Wilf conjecture | mr = 2063960 | year=2004 | journal=[[Journal of Combinatorial Theory]]|series=Series A  | volume=107 | issue=1 | pages=153–160 | doi=10.1016/j.jcta.2004.04.002| doi-access=free }}.</ref>
1980 के दशक के अंत में, रिचर्ड पी स्टेनली और [[हर्बर्ट विल्फ]] ने अनुमान लगाया कि प्रत्येक क्रमचय β के लिए, कुछ स्थिर K है जैसे कि |''Av<sub>n</sub>''(''β'')| < ''K<sup>n</sup>'' [[एडम मार्कस (गणितज्ञ)]] और गैबोर टार्डोस द्वारा सिद्ध किए जाने तक इसे स्टेनली-विल्फ अनुमान के रूप में जाना जाता था।<ref>{{Citation | last1=Marcus | first1=Adam | last2=Tardos | first2= Gábor | author2-link=Gábor Tardos | title=Excluded permutation matrices and the Stanley-Wilf conjecture | mr = 2063960 | year=2004 | journal=[[Journal of Combinatorial Theory]]|series=Series A  | volume=107 | issue=1 | pages=153–160 | doi=10.1016/j.jcta.2004.04.002| doi-access=free }}.</ref>




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


== मोबियस फ़ंक्शन ==
संवृत्त वर्ग, जिसे एक पैटर्न वर्ग, क्रमचय वर्ग, या केवल क्रमचय की श्रेणी के रूप में भी जाना जाता है, क्रमचय पैटर्न क्रम में एक [[आदर्श (आदेश सिद्धांत)|मानक (मानक सिद्धांत)]] है। प्रत्येक वर्ग को न्यूनतम क्रमचय द्वारा परिभाषित किया जा सकता है जो इसके आधार के अंदर नहीं है। इस प्रकार स्टैक-क्रमबद्ध करने योग्य क्रमचय का आधार {231} है, जबकि डेक-क्रमबद्ध करने योग्य क्रमचय का आधार अनंत है। अतः वर्ग के लिए जनक फलन Σ x <sup>|π|</sup> है, जहां वर्ग में सभी क्रमचय π पर योग अधिक लिया जाता है।
चूंकि रोकथाम आदेश के तहत क्रमचय का सेट [[आंशिक रूप से आदेशित सेट]] बनाता है, इसलिए इसकी घटना बीजगणित के बारे में पूछना स्वाभाविक है # विशेष तत्व | मोबियस फ़ंक्शन, एक लक्ष्य जिसे पहले स्पष्ट रूप से प्रस्तुत किया गया था {{harvtxt|Wilf|2002}}.<ref>{{citation | last1=Wilf | first1=Herbert | authorlink = Herbert Wilf |title=Patterns of permutations | mr = 1935750 | year=2002 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]| volume=257 | issue=2 | pages=575–583 | doi = 10.1016/S0012-365X(02)00515-0| doi-access=free }}.</ref>
इस तरह की जांच में लक्ष्य एक अंतराल [σ, π] के मोबियस फ़ंक्शन के लिए क्रमचय प्रतिमान पोसेट में एक सूत्र खोजना है जो भोली पुनरावर्ती परिभाषा से अधिक कुशल है। इस तरह का पहला परिणाम द्वारा स्थापित किया गया था {{harvtxt|Sagan|Vatter|2006}}, जिन्होंने [[स्तरित क्रमपरिवर्तन|स्तरित क्रमचय]] के अंतराल के मोबियस फ़ंक्शन के लिए एक सूत्र दिया।<ref>{{Citation | last1=Sagan | first1=Bruce | author1-link=Bruce Sagan | last2=Vatter | first2= Vince | title=The Möbius function of a composition poset | mr = 2259013 | year=2006 | journal=[[Journal of Algebraic Combinatorics]]  | volume=24 | issue=2 | pages=117–136 | doi=10.1007/s10801-006-0017-4| arxiv=math/0507485 | s2cid=11283347 }}.</ref>
बाद में, {{harvtxt|Burstein|Jelinek|Jelinkova|Steingrimsson|2011}} ने इस परिणाम को वियोज्य क्रमचय के अंतराल के लिए सामान्यीकृत किया।<ref>{{Citation | last1=Burstein | first1=Alexander | last2=Jelinek | first2= Vit | last3=Jelinkova | first3=Eva | last4=Steingrimsson | first4= Einar |title=The Möbius function of separable and decomposable permutations | mr = 2834180 | year=2011 | journal=[[Journal of Combinatorial Theory]]|series=Series A  | volume=118 | issue=1 | pages=2346–2364 | doi=10.1016/j.jcta.2011.06.002| s2cid=13978488 | doi-access=free }}.</ref>
यह ज्ञात है कि, स्पर्शोन्मुख रूप से, n लंबाई के सभी क्रमचय π का ​​कम से कम 39.95% μ(1, π)=0 को संतुष्ट करता है (अर्थात, प्रमुख मोबियस फ़ंक्शन शून्य के बराबर है),<ref>{{citation |last1=Brignall |first1=Robert |last2=Jelínek |first2=Vit |last3=Kynčl |first3=Jan |last4=Marchant |first4=David |title=Zeros of the Möbius function of permutations | year=2019 | journal=[[Mathematika]] |volume=65 |issue=4 |pages=1074–1092 | mr=3992365 | doi=10.1112/S0025579319000251|s2cid=53366318 |url=http://oro.open.ac.uk/66369/1/181012-Marchant-v101.pdf |arxiv=1810.05449 }}</ref> लेकिन प्रत्येक एन के लिए क्रमचय π मौजूद है जैसे कि μ(1, π) एन का एक घातीय कार्य है।<ref>{{citation |last1=Marchant |first1=David |title=2413-balloon permutations and the growth of the Möbius function |journal=[[Electronic Journal of Combinatorics]] |date=2020 |volume=27 |issue=1 |page=P1.7 |doi=10.37236/8554|doi-access=free }}</ref>


== मोबियस फलन ==
चूंकि नियंत्रण क्रम के अंतर्गत क्रमचय का समूह [[आंशिक रूप से आदेशित सेट|आंशिकतः क्रमित समूह]] बनाता है, इसके मोबियस फलन के बारे में पूछना स्वाभाविक है, एक लक्ष्य जिसे पहली बार विल्फ़ (2002) द्वारा स्पष्ट रूप से प्रस्तुत किया गया था।<ref>{{citation | last1=Wilf | first1=Herbert | authorlink = Herbert Wilf |title=Patterns of permutations | mr = 1935750 | year=2002 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]| volume=257 | issue=2 | pages=575–583 | doi = 10.1016/S0012-365X(02)00515-0| doi-access=free }}.</ref> इस तरह की जांच में लक्ष्य एक अंतराल [σ, π] के मोबियस फलन के लिए क्रमचय पैटर्न आंशिकतः क्रमित समूह में एक सूत्र खोजना है जो सरल पुनरावर्ती परिभाषा से अधिक उपयुक्त है। ऐसा पहला परिणाम सागन एंड वैटर (2006) द्वारा स्थापित किया गया था, जिन्होंने स्तरित क्रमपरिवर्तन के अंतराल के मोबियस फलन के लिए एक सूत्र दिया था।<ref>{{Citation | last1=Sagan | first1=Bruce | author1-link=Bruce Sagan | last2=Vatter | first2= Vince | title=The Möbius function of a composition poset | mr = 2259013 | year=2006 | journal=[[Journal of Algebraic Combinatorics]]  | volume=24 | issue=2 | pages=117–136 | doi=10.1007/s10801-006-0017-4| arxiv=math/0507485 | s2cid=11283347 }}.</ref>बाद में, बर्स्टीन एट अल (2011) ने इस परिणाम को वियोज्य क्रमचय के अंतराल के लिए सामान्यीकृत किया।<ref>{{Citation | last1=Burstein | first1=Alexander | last2=Jelinek | first2= Vit | last3=Jelinkova | first3=Eva | last4=Steingrimsson | first4= Einar |title=The Möbius function of separable and decomposable permutations | mr = 2834180 | year=2011 | journal=[[Journal of Combinatorial Theory]]|series=Series A  | volume=118 | issue=1 | pages=2346–2364 | doi=10.1016/j.jcta.2011.06.002| s2cid=13978488 | doi-access=free }}.</ref>


== कम्प्यूटेशनल जटिलता ==
यह ज्ञात है कि, असम्बद्ध रूप से, n लंबाई के सभी क्रमचय π का ​​कम से कम 39.95% μ(1, π)=0 को संतुष्ट करता है (अर्थात, प्रमुख मोबियस फलन शून्य के समतुल्य है),<ref>{{citation |last1=Brignall |first1=Robert |last2=Jelínek |first2=Vit |last3=Kynčl |first3=Jan |last4=Marchant |first4=David |title=Zeros of the Möbius function of permutations | year=2019 | journal=[[Mathematika]] |volume=65 |issue=4 |pages=1074–1092 | mr=3992365 | doi=10.1112/S0025579319000251|s2cid=53366318 |url=http://oro.open.ac.uk/66369/1/181012-Marchant-v101.pdf |arxiv=1810.05449 }}</ref> लेकिन प्रत्येक n के लिए क्रमचय π सम्मिलित है जैसे कि μ(1, π), n का एक चरघातांकी फलन है।<ref>{{citation |last1=Marchant |first1=David |title=2413-balloon permutations and the growth of the Möbius function |journal=[[Electronic Journal of Combinatorics]] |date=2020 |volume=27 |issue=1 |page=P1.7 |doi=10.37236/8554|doi-access=free }}</ref>


एक क्रमचय दिया <math>\tau</math> (पाठ कहा जाता है) लंबाई का <math>n</math> और दूसरा क्रमचय <math>\pi</math> लंबाई का <math>k</math> (प्रतिमान कहा जाता है), क्रमचय प्रतिमान मिलान (पीपीएम) समस्या पूछती है कि क्या <math>\pi</math> में निहित है <math>\tau</math>. कब दोनों <math>n</math> और <math>k</math> चर के रूप में माना जाता है, समस्या को एनपी-पूर्ण के रूप में जाना जाता है, और ऐसे मिलानों की संख्या की गणना करने की समस्या तीव्र-पी-पूर्ण|#पी-पूर्ण है।<ref>{{citation|last1=Bose|first1=Prosenjit|author1-link=Jit Bose|last2=Buss|first2=Jonathan F.|last3=Lubiw|first3=Anna|author3-link=Anna Lubiw|title=Pattern matching for permutations|journal=[[Information Processing Letters]]|date=March 1998|volume=65|issue=5|pages=277–283|doi=10.1016/S0020-0190(97)00209-3}}</ref> हालाँकि, पीपीएम को [[रैखिक समय]] में हल किया जा सकता है जब k स्थिर हो। दरअसल, गुइलमोट और मार्क्स<ref>{{cite journal|last=Guillemot|first=Sylvain|author2=Marx, Daniel|title=रैखिक समय में क्रमपरिवर्तन में छोटे पैटर्न ढूँढना|journal=Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms|year=2014|page=20|doi=10.1137/1.9781611973402.7|arxiv=1307.3073|isbn=978-1-61197-338-9|s2cid=1846959}}</ref> दिखाया कि पीपीएम को समय पर हल किया जा सकता है <math>2^{O(k^2\log k)} \cdot n</math>, जिसका अर्थ है कि यह निश्चित-पैरामीटर के संबंध में ट्रैक्टेबल है <math>k</math>.


पीपीएम समस्या पर कई प्रकार हैं, जैसा कि ब्रूनर और लैकनर द्वारा सर्वेक्षण किया गया है।<ref>{{citation|title=The computational landscape of permutation patterns|first1=Marie-Louise|last1=Bruner|first2=Martin|last2=Lackner|year=2013|journal=Pure Mathematics and Applications|volume=24|issue=2|pages=83–101|arxiv=1301.0340}}</ref> उदाहरण के लिए, यदि मैच में सन्निहित प्रविष्टियों को सम्मिलित करना आवश्यक है तो समस्या को बहुपद समय में हल किया जा सकता है।<ref>{{citation|last1=Kubica|first1=M.|last2=Kulczyński|first2=T.|last3=Radoszewski|first3=J.|last4=Rytter|first4=W.|last5=Waleń|first5=T.|title=A linear time algorithm for consecutive permutation pattern matching|journal=[[Information Processing Letters]]|year=2013|volume=113|issue=12|pages=430–433|doi=10.1016/j.ipl.2013.03.015}}</ref>
एक अन्य संस्करण तब होता है जब प्रतिमान और पाठ दोनों एक उचित क्रमचय वर्ग तक सीमित होते हैं <math>\mathcal{C}</math>, जिस स्थिति में समस्या कहा जाता है <math>\mathcal{C}</math>-पीपीएम। उदाहरण के लिए, गुइलमोट और वायलेट<ref>{{citation|last1=Guillemot|first1=Sylvain|last2=Vialette|first2=Stéphane|contribution=Pattern matching for 321-avoiding permutations|title=Algorithms and Computation|year=2009|volume=5878|series=Lecture Notes in Computer Science|pages=1064–1073|doi=10.1007/978-3-642-10631-6_107|arxiv=1511.01770}}</ref> पता चला है कि <math>\mbox{Av}(321)</math>-पीपीएम में हल किया जा सकता है <math>O(k^2n^6)</math> समय। माइकल एच। अल्बर्ट, लैकनर, लैकनर और वैटर<ref>{{citation|last1=Albert|first1=Michael | author1-link=Michael H. Albert |last2=Lackner|first2=Marie-Louise|last3=Lackner|first3=Martin|last4=Vatter|first4=Vincent|year=2016|volume=18|issue=2|journal=Discrete Mathematics & Theoretical Computer Science|title=The complexity of pattern matching for 321-avoiding and skew-merged permutations|doi=10.46298/dmtcs.1308 |arxiv=1510.06051|s2cid=5827603 }}</ref> बाद में इसे कम कर दिया <math>O(kn)</math> और दिखाया कि तिरछा-विलय किए गए क्रमचय के वर्ग के लिए समान सीमा प्रयुक्त होती है। उन्होंने आगे पूछा कि क्या <math>\mathcal{C}</math>-पीपीएम समस्या को हर निश्चित उचित क्रमचय वर्ग के लिए बहुपद समय में हल किया जा सकता है <math>\mathcal{C}</math>.


== पैकिंग घनत्व ==
== कम्प्यूटेशनल (अभिकलनात्मक) जटिलता ==
क्रमचय π को β-इष्टतम कहा जाता है यदि π के समान लंबाई का कोई क्रमचय नहीं है जिसमें β की अधिक प्रतियां हैं। 1992 में असतत गणित पर SIAM की बैठक में अपने संबोधन में, विल्फ ने लंबाई k के क्रमचय β के पैकिंग घनत्व को परिभाषित किया
 
लंबाई n के एक क्रमचय <math>\tau</math> ( मूल कहा जाता है) और लंबाई k के एक अन्य क्रमपरिवर्तन <math>\pi</math> (पैटर्न कहा जाता है) को देखते हुए, क्रमपरिवर्तन पैटर्न सुमेलन (पीपीएम) समस्या प्रश्न है कि क्या <math>\pi</math>, <math>\tau</math> में समाहित है। जब n और k दोनों को चर के रूप में माना जाता है, तो समस्या को NP-पूर्ण के रूप में जाना जाता है, और ऐसे समरूपों की संख्या की गणना करने की समस्या #P-पूर्ण है।<ref>{{citation|last1=Bose|first1=Prosenjit|author1-link=Jit Bose|last2=Buss|first2=Jonathan F.|last3=Lubiw|first3=Anna|author3-link=Anna Lubiw|title=Pattern matching for permutations|journal=[[Information Processing Letters]]|date=March 1998|volume=65|issue=5|pages=277–283|doi=10.1016/S0020-0190(97)00209-3}}</ref> हालाँकि, क्रमपरिवर्तन पैटर्न सुमेलन को [[रैखिक समय]] में संसोधित किया जा सकता है जब k स्थिर हो। वास्तव में, गुइलमोट और मार्क्स ने<ref>{{cite journal|last=Guillemot|first=Sylvain|author2=Marx, Daniel|title=रैखिक समय में क्रमपरिवर्तन में छोटे पैटर्न ढूँढना|journal=Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms|year=2014|page=20|doi=10.1137/1.9781611973402.7|arxiv=1307.3073|isbn=978-1-61197-338-9|s2cid=1846959}}</ref> दिखाया कि क्रमपरिवर्तन पैटर्न सुमेलन को <math>2^{O(k^2\log k)} \cdot n</math> समय पर हल किया जा सकता है। जिसका अर्थ है कि यह  <math>k</math> के संबंध में निश्चित-पैरामीटर सुविधाजनक है
 
क्रमपरिवर्तन पैटर्न सुमेलन समस्या पर कई प्रकार हैं, जैसा कि ब्रूनर और लैकनर द्वारा सर्वेक्षण किया गया है।<ref>{{citation|title=The computational landscape of permutation patterns|first1=Marie-Louise|last1=Bruner|first2=Martin|last2=Lackner|year=2013|journal=Pure Mathematics and Applications|volume=24|issue=2|pages=83–101|arxiv=1301.0340}}</ref> उदाहरण के लिए, यदि सुमेलन में सन्निहित प्रविष्टियों को सम्मिलित करना आवश्यक है तो समस्या को बहुपद समय में हल किया जा सकता है।<ref>{{citation|last1=Kubica|first1=M.|last2=Kulczyński|first2=T.|last3=Radoszewski|first3=J.|last4=Rytter|first4=W.|last5=Waleń|first5=T.|title=A linear time algorithm for consecutive permutation pattern matching|journal=[[Information Processing Letters]]|year=2013|volume=113|issue=12|pages=430–433|doi=10.1016/j.ipl.2013.03.015}}</ref>
 
अन्य संस्करण तब होता है जब पैटर्न और टेक्स्ट दोनों एक उपयुक्त क्रमचय वर्ग <math>\mathcal{C}</math> तक सीमित होते हैं, जिस स्थिति में समस्या को <math>\mathcal{C}</math>-क्रमपरिवर्तन पैटर्न सुमेलन कहा जाता है। उदाहरण के लिए, गुइलमोट और वायलेट<ref>{{citation|last1=Guillemot|first1=Sylvain|last2=Vialette|first2=Stéphane|contribution=Pattern matching for 321-avoiding permutations|title=Algorithms and Computation|year=2009|volume=5878|series=Lecture Notes in Computer Science|pages=1064–1073|doi=10.1007/978-3-642-10631-6_107|arxiv=1511.01770}}</ref> ने दिखाया कि <math>\mbox{Av}(321)</math>-क्रमपरिवर्तन पैटर्न सुमेलन को <math>O(k^2n^6)</math> समय में हल किया जा सकता है। अल्बर्ट, लैकनर, लैकनर, और वैटर<ref>{{citation|last1=Albert|first1=Michael | author1-link=Michael H. Albert |last2=Lackner|first2=Marie-Louise|last3=Lackner|first3=Martin|last4=Vatter|first4=Vincent|year=2016|volume=18|issue=2|journal=Discrete Mathematics & Theoretical Computer Science|title=The complexity of pattern matching for 321-avoiding and skew-merged permutations|doi=10.46298/dmtcs.1308 |arxiv=1510.06051|s2cid=5827603 }}</ref> ने बाद में इसे <math>O(kn)</math> तक कम किया और दिखाया कि तिर्यक-मिला दिए गए क्रमचय के वर्ग के लिए समान सीमा प्रयुक्त होती है। उन्होंने आगे पूछा कि क्या <math>\mathcal{C}</math>-क्रमपरिवर्तन पैटर्न सुमेलन समस्या को प्रत्येक निश्चित उपयुक्त क्रमचय वर्ग <math>\mathcal{C}</math> के लिए बहुपद समय में हल किया जा सकता है
 
== संकुलन घनत्व ==
क्रमचय π को β-इष्टतम कहा जाता है यदि π के समान लंबाई का कोई क्रमचय नहीं है जिसमें β की अधिक प्रतियां हैं। 1992 में असतत गणित पर औद्योगिक और व्यावहारिक गणित संस्था की बैठक में अपने संबोधन में, विल्फ ने लंबाई k के क्रमचय β के संकुलन घनत्व को परिभाषित किया


: <math>
: <math>
Line 96: Line 100:
\frac{\text{number of copies of }\beta\text{ in a }\beta\text{-optimal permutation of length }n}{\displaystyle{n\choose k}}.
\frac{\text{number of copies of }\beta\text{ in a }\beta\text{-optimal permutation of length }n}{\displaystyle{n\choose k}}.
</math>
</math>
[[फ्रेड गैल्विन]] के एक अप्रकाशित तर्क से पता चलता है कि अनुक्रम की इस सीमा के अंदर की मात्रा n ≥ k के लिए गैर-बढ़ती है, और इसलिए सीमा मौजूद है। जब β मोनोटोन होता है, तो इसका पैकिंग घनत्व स्पष्ट रूप से 1 होता है, और पैकिंग घनत्व व्युत्क्रम और रिवर्स द्वारा उत्पन्न समरूपता के समूह के अंतर्गत अपरिवर्तनीय होते हैं, इसलिए लंबाई तीन के क्रमचय के लिए, केवल एक गैर-तुच्छ पैकिंग घनत्व होता है। वाल्टर स्ट्रोमक्विस्ट (अप्रकाशित) ने यह दिखाकर इस मामले को सुलझाया कि 132 की पैकिंग घनत्व 2 है{{radic|3}} − 3, लगभग 0.46410।
[[फ्रेड गैल्विन]] के एक अप्रकाशित तर्क से पता चलता है कि अनुक्रम की इस सीमा के अंदर की मात्रा n ≥ k के लिए गैर-वर्धमान है, और इसलिए सीमा सम्मिलित है। जब β एकदिष्ट होता है, तो इसका संकुलन घनत्व स्पष्ट रूप से 1 होता है, और संकुलन घनत्व व्युत्क्रम और प्रतिलोम द्वारा उत्पन्न समरूपता के समूह के अंतर्गत अपरिवर्तनीय होते हैं, इसलिए लंबाई तीन के क्रमचय के लिए, केवल एक गैर-सामान्य संकुलन घनत्व होता है। वाल्टर स्ट्रोमक्विस्ट (अप्रकाशित) ने यह दिखाकर इस स्थिति को सुलझाया कि 132 की संकुलन घनत्व 2{{radic|3}} − 3, लगभग 0.46410 है।


लंबाई चार के क्रमचय β के लिए, (समरूपता के कारण) विचार करने के लिए सात मामले हैं:
लंबाई चार के क्रमचय β के लिए, (समरूपता के कारण) विचार करने के लिए सात मामले हैं:
Line 102: Line 106:
{| class="wikitable" style="text-align:center;" border="1"
{| class="wikitable" style="text-align:center;" border="1"
|-
|-
! β !! packing density !! reference
! β !! संकुलन घनत्व !! सन्दर्भ
|-
|-
| &nbsp;1234&nbsp; || 1 || trivial
| &nbsp;1234&nbsp; || 1 || सामान्य
|-
|-
| &nbsp;1432&nbsp; || root of ''x''<sup>3</sup> &minus; 12''x''<sup>2</sup> + 156''x'' &minus; 64 &cong; 0.42357 || {{harvtxt|Price|1997}}<ref name="price97">{{citation | last=Price | first=Alkes | title=Packing densities of layered patterns | publisher=University of Pennsylvania | series = Ph.D. thesis | year=1997}}.</ref>
| &nbsp;1432&nbsp; || root of ''x''<sup>3</sup> &minus; 12''x''<sup>2</sup> + 156''x'' &minus; 64 &cong; 0.42357 || {{harvtxt|प्राइज अलकेज|1997}}<ref name="price97">{{citation | last=Price | first=Alkes | title=Packing densities of layered patterns | publisher=University of Pennsylvania | series = Ph.D. thesis | year=1997}}.</ref>
|-
|-
| &nbsp;2143&nbsp; || ⅜ = 0.375 || {{harvtxt|Price|1997}}<ref name="price97"/>
| &nbsp;2143&nbsp; || ⅜ = 0.375 || {{harvtxt|प्राइज एलकेस|1997}}<ref name="price97"/>
|-
|-
| &nbsp;1243&nbsp; || ⅜ = 0.375 || {{harvtxt|Albert|Atkinson|Handley|Holton|2002}}<ref>{{Citation
| &nbsp;1243&nbsp; || ⅜ = 0.375 || अल्बर्ट एट अल (2002)<ref>{{Citation
| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert  
| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert  
| last2=Atkinson | first2=M. D.
| last2=Atkinson | first2=M. D.
Line 124: Line 128:
| url=http://www.combinatorics.org/Volume_9/Abstracts/v9i1r5.html| doi-access=free}}.</ref>
| url=http://www.combinatorics.org/Volume_9/Abstracts/v9i1r5.html| doi-access=free}}.</ref>
|-
|-
| &nbsp;1324&nbsp; || conjectured to be &cong; 0.244 ||  
| &nbsp;1324&nbsp; || अनुमानित &cong; 0.244 ||
|-
|-
| &nbsp;1342&nbsp; || conjectured to be &cong; 0.19658 ||  
| &nbsp;1342&nbsp; || अनुमानित &cong; 0.19658 ||
|-
|-
| &nbsp;2413&nbsp; || conjectured to be &cong; 0.10474 ||  
| &nbsp;2413&nbsp; || अनुमानित &cong; 0.10474 ||
|}
|}
तीन अज्ञात क्रमचय के लिए सीमाएँ और अनुमान हैं। {{harvtxt|Price|1997}} ने एक सन्निकटन एल्गोरिथम का उपयोग किया जो बताता है कि 1324 का पैकिंग घनत्व लगभग 0.244 है।<ref name="price97"/> बिर्जन बटकेयेव (अप्रकाशित) ने क्रमचय के एक परिवार का निर्माण किया, जिसमें दिखाया गया है कि 1342 का पैकिंग घनत्व कम से कम 132 और 1432 के पैकिंग घनत्व का उत्पाद है, लगभग 0.19658। यह 1342 की सटीक पैकिंग घनत्व होने का अनुमान है। {{harvtxt|Presutti|Stromquist|2010}} ने 2413 के पैकिंग घनत्व पर एक निचली सीमा प्रदान की। यह निचली सीमा, जिसे एक अभिन्न के रूप में व्यक्त किया जा सकता है, लगभग 0.10474 है, और वास्तविक पैकिंग घनत्व होने का अनुमान लगाया गया है।<ref>{{ Citation
तीन अज्ञात क्रमचय के लिए सीमाएँ और अनुमान हैं। प्राइस (1997) ने एक सन्निकटन एल्गोरिथम का उपयोग किया जो बताता है कि 1324 का संकुलन घनत्व लगभग 0.244 है।<ref name="price97"/> बिर्जन बटकेयेव (अप्रकाशित) ने क्रमचय के एक वर्ग का निर्माण किया, जिसमें दिखाया गया है कि 1342 का संकुलन घनत्व कम से कम 132 और 1432 के संकुलन घनत्व का उत्पाद, लगभग 0.19658 है। यह 1342 की परिशुद्ध संकुलन घनत्व होने का अनुमान है। प्रेसुट्टी और स्ट्रोमक्विस्ट (2010) ने 2413 के संकुलन घनत्व पर एक निचली सीमा प्रदान की। यह निचली सीमा, जिसे एक अभिन्न के रूप में व्यक्त किया जा सकता है, लगभग 0.10474 है, और वास्तविक संकुलन घनत्व होने का अनुमान लगाया गया है।<ref>{{ Citation
  | last1=Presutti
  | last1=Presutti
  | first1=Cathleen Battiste
  | first1=Cathleen Battiste
Line 154: Line 158:


== सुपरपैटर्न ==
== सुपरपैटर्न ==
{{main article|Superpattern}}
{{main article|सुपरपैटर्न}}
एक k-'सुपरपैटर्न' एक क्रमचय है जिसमें लंबाई k के सभी क्रमचय सम्मिलित हैं। उदाहरण के लिए, 25314 एक 3-सुपरपैटर्न है क्योंकि इसमें लंबाई 3 के सभी 6 क्रमचय सम्मिलित हैं। यह ज्ञात है कि k-सुपरपैटर्न की लंबाई कम से कम k होनी चाहिए।<sup>2</sup>/ई<sup>2</sup>, जहां e ≈ 2.71828 e (गणितीय स्थिरांक) है|यूलर की संख्या,<ref>{{citation
 
k-'सुपरपैटर्न' एक क्रमचय है जिसमें लंबाई k के सभी क्रमचय सम्मिलित हैं। उदाहरण के लिए, 25314 एक 3-सुपरपैटर्न है क्योंकि इसमें लंबाई 3 के सभी 6 क्रमचय सम्मिलित हैं। यह ज्ञात है कि k-सुपरपैटर्न की लंबाई कम से कम k<sup>2</sup>/e<sup>2</sup>, जहां e ≈ 2.71828 e (गणितीय स्थिरांक) यूलर की संख्या है,<ref>{{citation
  | last = Arratia | first = Richard | authorlink = Richard Arratia
  | last = Arratia | first = Richard | authorlink = Richard Arratia
  | journal = [[Electronic Journal of Combinatorics]]
  | journal = [[Electronic Journal of Combinatorics]]
Line 164: Line 169:
  | volume = 6
  | volume = 6
  | year = 1999| doi = 10.37236/1477 | doi-access = free
  | year = 1999| doi = 10.37236/1477 | doi-access = free
  }}.</ref> और यह कि लंबाई ⌈(k.) के k-सुपरपैटर्न मौजूद हैं<sup>2</sup> + 1)/2⌉.<ref name="engenvatter">{{citation
  }}.</ref> और लंबाई के k-सुपरपैटर्न ⌈(''k''<sup>2</sup> + 1)/2⌉ सम्मिलित है। <ref name="engenvatter">{{citation
| last1 = Engen | first1 = Michael  
| last1 = Engen | first1 = Michael  
| last2 = Vatter | first2 = Vincent
| last2 = Vatter | first2 = Vincent
Line 175: Line 180:
| issue = 1
| issue = 1
| pages = 4–24
| pages = 4–24
}}</ref>
}}</ref> यह ऊपरी सीमा निम्न-क्रम की शर्तों तक सर्वोत्तम संभव होने का अनुमान लगाया गया है।<ref name="eelw">{{citation
यह ऊपरी सीमा निचले क्रम की शर्तों तक सर्वोत्तम संभव होने का अनुमान लगाया गया है।<ref name="eelw">{{citation
  | last1 = Eriksson | first1 = Henrik
  | last1 = Eriksson | first1 = Henrik
  | last2 = Eriksson | first2 = Kimmo
  | last2 = Eriksson | first2 = Kimmo
Line 193: Line 197:


== सामान्यीकरण ==
== सामान्यीकरण ==
ऐसे कई तरीके हैं जिनमें प्रतिमान की धारणा को सामान्यीकृत किया गया है। उदाहरण के लिए, एक विनकुलर प्रतिमान एक क्रमचय है जिसमें डैश होते हैं जो प्रविष्टियों को इंगित करते हैं जो लगातार होने की आवश्यकता नहीं होती है (सामान्य प्रतिमान परिभाषा में, कोई प्रविष्टि लगातार होने की आवश्यकता नहीं होती है)। उदाहरण के लिए, क्रमचय 314265 में धराशायी प्रतिमान 2-31-4 की दो प्रतियां हैं, जो 3426 और 3425 प्रविष्टियों द्वारा दी गई हैं। धराशायी प्रतिमान β और किसी भी क्रमचय π के लिए, हम β की प्रतियों की संख्या के लिए β(π) लिखते हैं। π में। इस प्रकार π में व्युत्क्रमों की संख्या 2-1(π) है, जबकि अवरोहण की संख्या 21(π) है। आगे जाकर, π में घाटियों की संख्या 213(π) + 312(π) है, जबकि चोटियों की संख्या 231(π) + 132(π) है। ये प्रतिमान द्वारा पेश किए गए थे {{harvtxt|Babson|Steingrímsson|2000}}, जिन्होंने दिखाया कि लगभग सभी ज्ञात Mahonian आँकड़े vincular permutations के संदर्भ में व्यक्त किए जा सकते हैं।<ref>{{citation
ऐसे कई तरीके हैं जिनमें पैटर्न की धारणा को सामान्यीकृत किया गया है। उदाहरण के लिए, एक विनकुलर पैटर्न एक क्रमचय है जिसमें डैश होते हैं जो प्रविष्टियों को इंगित करते हैं जो सतत होने की आवश्यकता नहीं होती है (सामान्य पैटर्न परिभाषा में, कोई प्रविष्टि सतत होने की आवश्यकता नहीं होती है)। उदाहरण के लिए, क्रमचय 314265 में सतत पैटर्न 2-31-4 की दो प्रतियां हैं, जो 3426 और 3425 प्रविष्टियों द्वारा दी गई हैं। सतत पैटर्न β और किसी भी क्रमचय π के लिए, हम π में β की प्रतियों की संख्या के लिए β(π) लिखते हैं। इस प्रकार π में व्युत्क्रमों की संख्या 2-1(π) है, जबकि अवरोहण की संख्या 21(π) है। आगे बढ़ते हुए, π में घाटियों की संख्या 213(π) + 312(π) है, जबकि शिखरों की संख्या 231(π) + 132(π) है। ये पैटर्न बाबसन एंड स्टिंग्रिम्सन (2000) द्वारा प्रस्तुत किए गए थे, जिन्होंने दिखाया था कि लगभग सभी ज्ञात महोनियन आँकड़ो को विनकुलर क्रमपरिवर्तन के रूप में व्यक्त किया जा सकता है।<ref>{{citation
| last1=Babson | first1=Erik
| last1=Babson | first1=Erik
| last2= Steingrímsson | first2=Einar
| last2= Steingrímsson | first2=Einar
Line 202: Line 206:
| pages=Research article B44b, 18 pp
| pages=Research article B44b, 18 pp
| mr = 1758852
| mr = 1758852
| url=http://www.emis.de/journals/SLC/wpapers/s44stein.html}}.</ref> उदाहरण के लिए, π का ​​[[प्रमुख सूचकांक]] 1-32(π) + 2-31(π) + 3-21(π) + 21(π) के बराबर है।
| url=http://www.emis.de/journals/SLC/wpapers/s44stein.html}}.</ref> उदाहरण के लिए, π का प्रमुख सूचकांक 1-32(π) + 2-31(π) + 3-21(π) + 21(π) के समान है।


एक अन्य सामान्यीकरण वर्जित प्रतिमान का है, जिसमें कुछ प्रविष्टियाँ वर्जित हैं। π के लिए वर्जित प्रतिमान से परिहरण करने के लिए β का अर्थ है कि π की प्रविष्टियों का प्रत्येक सेट जो β की गैर-वर्जित प्रविष्टियों की प्रतिलिपि बनाता है, को β की सभी प्रविष्टियों की प्रतिलिपि बनाने के लिए बढ़ाया जा सकता है। {{harvtxt|West|1993}} ने क्रमचय के अपने अध्ययन में इस प्रकार के प्रतिमान पेश किए जिन्हें एक ढेर के माध्यम से दो बार पास करके क्रमबद्ध किया जा सकता है।<ref>{{Citation | last1=West | first1=Julian | title=Sorting twice through a stack| mr = 1235186| year=1993 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]| volume=117 | issue=1–2 | pages=303–313| doi = 10.1016/0304-3975(93)90321-J| doi-access=free}}.</ref> (ध्यान दें कि स्टैक के माध्यम से दो बार सॉर्ट करने की पश्चिम की परिभाषा श्रृंखला में दो स्टैक्स के साथ सॉर्ट करने के समान नहीं है।) वर्जित प्रतिमान का एक और उदाहरण के काम में होता है {{harvtxt|Bousquet-Mélou|Butler|2007}}, जिन्होंने दिखाया कि π के अनुरूप शूबर्ट विविधता Schubert किस्म है#स्थानीय रूप से फैक्टोरियल यदि और केवल यदि π 1324 और 21 से बचता है<span style= text-decoration: overline; >3</span>54.<ref>{{Citation
अन्य सामान्यीकरण रेखित पैटर्न का है, जिसमें कुछ प्रविष्टियाँ रेखित हैं। और π के लिए रेखित पैटर्न से संरक्षित करने के लिए β का अर्थ है कि π की प्रविष्टियों का प्रत्येक समूह जो β की गैर-रेखित प्रविष्टियों की प्रतिलिपि बनाता है, जिसको β की सभी प्रविष्टियों की प्रतिलिपि बनाने के लिए बढ़ाया जा सकता है। वेस्ट (1993) ने क्रमचय के अपने अध्ययन में इस प्रकार के पैटर्न प्रस्तुत किए जिन्हें एक स्टैक के माध्यम से दो बार पास करके क्रमबद्ध किया जा सकता है।<ref>{{Citation | last1=West | first1=Julian | title=Sorting twice through a stack| mr = 1235186| year=1993 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]| volume=117 | issue=1–2 | pages=303–313| doi = 10.1016/0304-3975(93)90321-J| doi-access=free}}.</ref> (ध्यान दें कि स्टैक के माध्यम से दो बार श्रेणीबद्ध करने की वेस्ट की परिभाषा श्रृंखला में दो स्टैक्स के साथ श्रेणीबद्ध करने के समान नहीं है।) रेखित पैटर्न का एक अन्य उदाहरण बाउस्केट-मेलौ और बटलर (2007) के कार्य में होता है , जिन्होंने दिखाया कि π के अनुरूप शूबर्ट विविधता स्थानीय रूप से फैक्टोरियल ( क्रमगुणित) है, यदि और केवल यदि π 1324 और 21354 से संरक्षित रहता है।<ref>{{Citation
| last1=Bousquet-Mélou | first1=Mireille | author1-link = Mireille Bousquet-Mélou
| last1=Bousquet-Mélou | first1=Mireille | author1-link = Mireille Bousquet-Mélou
| last2=Butler | first2=Steve |authorlink2=Steve Butler (mathematician)
| last2=Butler | first2=Steve |authorlink2=Steve Butler (mathematician)
Line 261: Line 265:
* [http://math.depaul.edu/~bridget/patterns.html Database of Permutation Pattern Avoidance], maintained by Bridget Tenner.
* [http://math.depaul.edu/~bridget/patterns.html Database of Permutation Pattern Avoidance], maintained by Bridget Tenner.
* [https://permpal.com/ 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.
* [https://permpal.com/ 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.
[[Category: क्रमपरिवर्तन पैटर्न | क्रमपरिवर्तन पैटर्न ]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Commons category link is locally defined]]
[[Category:Created On 21/03/2023]]
[[Category:Created On 21/03/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:क्रमपरिवर्तन पैटर्न| क्रमपरिवर्तन पैटर्न ]]

Latest revision as of 10:12, 18 April 2023

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

उदाहरण के लिए, क्रमचय π में पैटर्न 213 होता है जब भी π में तीन अंक x, y, और z होते हैं जो क्रम xy...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 के समान नहीं है।

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

ऐसी स्थिति बनाई जा सकती है कि पर्सी मैकमोहन (1915) लैटिस क्रमचय के अपने अध्ययन के साथ क्षेत्र में परिणाम प्रमाणित करने वाले पहले व्यक्ति थे।[1] विशेष रूप से मैकमोहन दिखाता है कि जिन क्रमपरिवर्तनों को दो घटते क्रमपरिवर्तनों में विभाजित किया जा सकता है (अर्थात्, 123 से परिहरण करने वाले क्रमचय) को कैटलन संख्याओं द्वारा गणना किए जाते है।[2]

इस क्षेत्र में एक और प्रारंभिक ऐतिहासिक परिणाम एर्डोस-ज़ेकेरेस प्रमेय है; क्रमचय पैटर्न भाषा में, प्रमेय कहता है कि किसी भी धनात्मक पूर्णांक a और b के लिए लंबाई का प्रत्येक क्रमचय कम से कम या तो पैटर्न या पैटर्न होना चाहिए।

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

क्रमचय पैटर्न का अध्ययन 1968 में डोनाल्ड नुथ के स्टैक- वर्गीकरण पर विचार के साथ महत्वपूर्ण रूप से प्रारंभ हुआ।[3] नुथ ने दिखाया कि क्रमचय π को स्टैक (डेटा संरचना) द्वारा क्रमबद्ध किया जा सकता है यदि और केवल यदि π 231 से परिहरण करता है, और यह कि स्टैक-क्रमांकन योग्य क्रमचय कैटलन संख्याओं द्वारा गणना किए जाते हैं।[4] नुथ ने डेक के साथ संकलन के बारे में भी सवाल प्रस्तुत किए। विशेष रूप से, नूथ का यह प्रश्न कि डेक के उपयोग से n तत्वों के कितने क्रमचय प्राप्त किए जा सकते हैं, और संवृत रहता है।[5] उसके बाद शीघ्र ही, रॉबर्ट टारजन (1972) स्टैक के नेटवर्क द्वारा संकलन की जांच की गई,[6] जबकि वॉन प्रैट (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 को परिवर्तित करके प्राप्त किया जा सकता है।[7] क्योंकि क्रमचय का यह संग्रह अनंत है (वास्तव में, यह क्रमचय के अनंत प्रतिश्रृंखला का पहला प्रकाशित उदाहरण है), यह तुरंत स्पष्ट नहीं है कि यह निर्धारित करने में कितना समय लगता है कि एक क्रमचय को डेक द्वारा क्रमबद्ध किया जा सकता है या नहीं किया जा सकता है। रोसेनस्टीहल और टार्जन (1984) ने बाद में एक रेखीय (π की लंबाई में) समय एल्गोरिथ्म प्रस्तुत किया जो यह निर्धारित करता है कि क्या π को एक डेक द्वारा क्रमबद्ध किया जा सकता है[8]

अपने पत्र में, प्रैट ने टिप्पणी की कि यह क्रमचय पैटर्न क्रम "क्रमचय पर एकमात्र आंशिक क्रम प्रतीत होता है जो एक सरल और प्राकृतिक तरीके से उत्पन्न होता है" और यह देखते हुए निष्कर्ष निकाला कि "एक अमूर्त दृष्टिकोण से", क्रमचय पैटर्न क्रम "हम जिन नेटवर्कों की विशेषता बता रहे थे, उनसे कहीं अधिक रोचक है”।[7]


परिगणनात्‍मक उत्पत्ति

Main article: विशिष्ट क्रमचय वर्गों की गणना

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

सिमोन एंड श्मिट (1985) पहला पत्र था जिसमें केवल गणना पर ध्यान केंद्रित किया गया था। अन्य परिणामों में, सिमिओन और श्मिट ने लंबाई तीन के एक पैटर्न से परिहार करते हुए सम और विषम क्रमपरिवर्तनों की गणना की, लंबाई तीन के दो प्रतिरूपों से परिहरण क्रमपरिवर्तनों की गणना की, और पहला विशेषण प्रमाण दिया कि 123- और 231-परिहार क्रमचय समतुल्य हैं।[9] उनके पत्र के बाद से, कई अन्य आक्षेप दिए गए हैं, सर्वेक्षण के लिए क्लेसन एंड किताएव (2008) देखें।[10]

सामान्य रूप से, यदि |Avn(β)| = |Avn(σ)| सभी n के लिए, तब β और σ को विलफ-तुल्य कहा जाता है। कई विल्फ-तुल्यताएँ सामान्य तथ्य से उत्पन्न होती हैं कि |Avn(β)| = |Avn(β−1)| = |Avn(βrev)| सभी n के लिए, जहां β−1 β के व्युत्क्रम को दर्शाता है और βrev β के व्युत्क्रम को दर्शाता है। (ये दो संक्रिया क्रमचय आव्यूहों पर एक प्राकृतिक क्रिया के साथ द्वितल समूह D8 उत्पन्न करते हैं।) हालांकि, गैर-सामान्य विल्फ-समतुल्यता के कई उदाहरण भी हैं (जैसे कि 123 और 231 के बीच):

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

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

β Avn(β) की अनुक्रम गणना ओईआईएस संदर्भ परिशुद्ध गणना संदर्भ
 1342  1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ... A022558 बोना (1997)[14]
 1234  1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ... A005802 गेसल (1990)[15]
 1324  1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ... A061552 अगणित

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


संवृत्त वर्ग

Main article: क्रमचय वर्ग

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

मोबियस फलन

चूंकि नियंत्रण क्रम के अंतर्गत क्रमचय का समूह आंशिकतः क्रमित समूह बनाता है, इसके मोबियस फलन के बारे में पूछना स्वाभाविक है, एक लक्ष्य जिसे पहली बार विल्फ़ (2002) द्वारा स्पष्ट रूप से प्रस्तुत किया गया था।[17] इस तरह की जांच में लक्ष्य एक अंतराल [σ, π] के मोबियस फलन के लिए क्रमचय पैटर्न आंशिकतः क्रमित समूह में एक सूत्र खोजना है जो सरल पुनरावर्ती परिभाषा से अधिक उपयुक्त है। ऐसा पहला परिणाम सागन एंड वैटर (2006) द्वारा स्थापित किया गया था, जिन्होंने स्तरित क्रमपरिवर्तन के अंतराल के मोबियस फलन के लिए एक सूत्र दिया था।[18]बाद में, बर्स्टीन एट अल (2011) ने इस परिणाम को वियोज्य क्रमचय के अंतराल के लिए सामान्यीकृत किया।[19]

यह ज्ञात है कि, असम्बद्ध रूप से, n लंबाई के सभी क्रमचय π का ​​कम से कम 39.95% μ(1, π)=0 को संतुष्ट करता है (अर्थात, प्रमुख मोबियस फलन शून्य के समतुल्य है),[20] लेकिन प्रत्येक n के लिए क्रमचय π सम्मिलित है जैसे कि μ(1, π), n का एक चरघातांकी फलन है।[21]


कम्प्यूटेशनल (अभिकलनात्मक) जटिलता

लंबाई n के एक क्रमचय ( मूल कहा जाता है) और लंबाई k के एक अन्य क्रमपरिवर्तन (पैटर्न कहा जाता है) को देखते हुए, क्रमपरिवर्तन पैटर्न सुमेलन (पीपीएम) समस्या प्रश्न है कि क्या , में समाहित है। जब n और k दोनों को चर के रूप में माना जाता है, तो समस्या को NP-पूर्ण के रूप में जाना जाता है, और ऐसे समरूपों की संख्या की गणना करने की समस्या #P-पूर्ण है।[22] हालाँकि, क्रमपरिवर्तन पैटर्न सुमेलन को रैखिक समय में संसोधित किया जा सकता है जब k स्थिर हो। वास्तव में, गुइलमोट और मार्क्स ने[23] दिखाया कि क्रमपरिवर्तन पैटर्न सुमेलन को समय पर हल किया जा सकता है। जिसका अर्थ है कि यह के संबंध में निश्चित-पैरामीटर सुविधाजनक है

क्रमपरिवर्तन पैटर्न सुमेलन समस्या पर कई प्रकार हैं, जैसा कि ब्रूनर और लैकनर द्वारा सर्वेक्षण किया गया है।[24] उदाहरण के लिए, यदि सुमेलन में सन्निहित प्रविष्टियों को सम्मिलित करना आवश्यक है तो समस्या को बहुपद समय में हल किया जा सकता है।[25]

अन्य संस्करण तब होता है जब पैटर्न और टेक्स्ट दोनों एक उपयुक्त क्रमचय वर्ग तक सीमित होते हैं, जिस स्थिति में समस्या को -क्रमपरिवर्तन पैटर्न सुमेलन कहा जाता है। उदाहरण के लिए, गुइलमोट और वायलेट[26] ने दिखाया कि -क्रमपरिवर्तन पैटर्न सुमेलन को समय में हल किया जा सकता है। अल्बर्ट, लैकनर, लैकनर, और वैटर[27] ने बाद में इसे तक कम किया और दिखाया कि तिर्यक-मिला दिए गए क्रमचय के वर्ग के लिए समान सीमा प्रयुक्त होती है। उन्होंने आगे पूछा कि क्या -क्रमपरिवर्तन पैटर्न सुमेलन समस्या को प्रत्येक निश्चित उपयुक्त क्रमचय वर्ग के लिए बहुपद समय में हल किया जा सकता है

संकुलन घनत्व

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

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

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

β संकुलन घनत्व सन्दर्भ
 1234  1 सामान्य
 1432  root of x3 − 12x2 + 156x − 64 ≅ 0.42357 प्राइज अलकेज (1997)[28]
 2143  ⅜ = 0.375 प्राइज एलकेस (1997)[28]
 1243  ⅜ = 0.375 अल्बर्ट एट अल (2002)[29]
 1324  अनुमानित ≅ 0.244
 1342  अनुमानित ≅ 0.19658
 2413  अनुमानित ≅ 0.10474

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


सुपरपैटर्न

Main article: सुपरपैटर्न

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


सामान्यीकरण

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

अन्य सामान्यीकरण रेखित पैटर्न का है, जिसमें कुछ प्रविष्टियाँ रेखित हैं। और π के लिए रेखित पैटर्न से संरक्षित करने के लिए β का अर्थ है कि π की प्रविष्टियों का प्रत्येक समूह जो β की गैर-रेखित प्रविष्टियों की प्रतिलिपि बनाता है, जिसको β की सभी प्रविष्टियों की प्रतिलिपि बनाने के लिए बढ़ाया जा सकता है। वेस्ट (1993) ने क्रमचय के अपने अध्ययन में इस प्रकार के पैटर्न प्रस्तुत किए जिन्हें एक स्टैक के माध्यम से दो बार पास करके क्रमबद्ध किया जा सकता है।[35] (ध्यान दें कि स्टैक के माध्यम से दो बार श्रेणीबद्ध करने की वेस्ट की परिभाषा श्रृंखला में दो स्टैक्स के साथ श्रेणीबद्ध करने के समान नहीं है।) रेखित पैटर्न का एक अन्य उदाहरण बाउस्केट-मेलौ और बटलर (2007) के कार्य में होता है , जिन्होंने दिखाया कि π के अनुरूप शूबर्ट विविधता स्थानीय रूप से फैक्टोरियल ( क्रमगुणित) है, यदि और केवल यदि π 1324 और 21354 से संरक्षित रहता है।[36]


संदर्भ

  1. ↑ MacMahon, Percy A. (1915), Combinatory Analysis, London: Cambridge University Press, Volume I, Section III, Chapter V.
  2. ↑ MacMahon (1915), Items 97 and 98.
  3. ↑ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391..
  4. ↑ Knuth (1968), Section 2.2.1, Exercises 4 and 5.
  5. ↑ Knuth (1968), Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.
  6. ↑ Tarjan, Robert (1972), "Sorting using networks of queues and stacks", Journal of the ACM, 19 (2): 341–346, doi:10.1145/321694.321704, MR 0298803, S2CID 13608929.
  7. ↑ 7.0 7.1 Pratt, Vaughan R. (1973), "Computing permutations with double-ended queues. Parallel stacks and parallel queues", Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), pp. 268–277, doi:10.1145/800125.804058, MR 0489115, S2CID 15740957.
  8. ↑ Rosenstiehl, Pierre; Tarjan, Robert (1984), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations", Journal of Algorithms, 5 (3): 375–390, doi:10.1016/0196-6774(84)90018-X, MR 0756164.
  9. ↑ Simion, Rodica; Schmidt, Frank W. (1985), "Restricted permutations", European Journal of Combinatorics, 6 (4): 383–406, doi:10.1016/s0195-6698(85)80052-4, MR 0829358.
  10. ↑ Claesson, Anders; Kitaev, Sergey (2008), "Classification of bijections between 321- and 132-avoiding permutations" (PDF), Séminaire Lotharingien de Combinatoire, 60: B60d, arXiv:0805.1325, MR 2465405.
  11. ↑ Stankova, Zvezdelina (1994), "Forbidden subsequences", Discrete Mathematics, 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR 1297387.
  12. ↑ Stankova, Zvezdelina; West, Julian (2002), "A New class of Wilf-Equivalent Permutations", Journal of Algebraic Combinatorics, 15 (3): 271–290, arXiv:math/0103152, doi:10.1023/A:1015016625432, MR 1900628, S2CID 13921676.
  13. ↑ Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Wilf-equivalence for singleton classes", Advances in Applied Mathematics, 38 (2): 133–149, doi:10.1016/j.aam.2004.11.006, MR 2290807.
  14. ↑ Bóna, Miklós (1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", Journal of Combinatorial Theory, Series A, 80 (2): 257–272, arXiv:math/9702223, doi:10.1006/jcta.1997.2800, MR 1485138, S2CID 18352890.
  15. ↑ Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", Journal of Combinatorial Theory, Series A, 53 (2): 257–285, doi:10.1016/0097-3165(90)90060-A, MR 1041448.
  16. ↑ Marcus, Adam; Tardos, Gábor (2004), "Excluded permutation matrices and the Stanley-Wilf conjecture", Journal of Combinatorial Theory, Series A, 107 (1): 153–160, doi:10.1016/j.jcta.2004.04.002, MR 2063960.
  17. ↑ Wilf, Herbert (2002), "Patterns of permutations", Discrete Mathematics, 257 (2): 575–583, doi:10.1016/S0012-365X(02)00515-0, MR 1935750.
  18. ↑ Sagan, Bruce; Vatter, Vince (2006), "The Möbius function of a composition poset", Journal of Algebraic Combinatorics, 24 (2): 117–136, arXiv:math/0507485, doi:10.1007/s10801-006-0017-4, MR 2259013, S2CID 11283347.
  19. ↑ Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (2011), "The Möbius function of separable and decomposable permutations", Journal of Combinatorial Theory, Series A, 118 (1): 2346–2364, doi:10.1016/j.jcta.2011.06.002, MR 2834180, S2CID 13978488.
  20. ↑ Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (2019), "Zeros of the Möbius function of permutations" (PDF), Mathematika, 65 (4): 1074–1092, arXiv:1810.05449, doi:10.1112/S0025579319000251, MR 3992365, S2CID 53366318
  21. ↑ Marchant, David (2020), "2413-balloon permutations and the growth of the Möbius function", Electronic Journal of Combinatorics, 27 (1): P1.7, doi:10.37236/8554
  22. ↑ Bose, Prosenjit; Buss, Jonathan F.; Lubiw, Anna (March 1998), "Pattern matching for permutations", Information Processing Letters, 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3
  23. ↑ Guillemot, Sylvain; Marx, Daniel (2014). "रैखिक समय में क्रमपरिवर्तन में छोटे पैटर्न ढूँढना". Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms: 20. arXiv:1307.3073. doi:10.1137/1.9781611973402.7. ISBN 978-1-61197-338-9. S2CID 1846959.
  24. ↑ Bruner, Marie-Louise; Lackner, Martin (2013), "The computational landscape of permutation patterns", Pure Mathematics and Applications, 24 (2): 83–101, arXiv:1301.0340
  25. ↑ Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (2013), "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters, 113 (12): 430–433, doi:10.1016/j.ipl.2013.03.015
  26. ↑ Guillemot, Sylvain; Vialette, Stéphane (2009), "Pattern matching for 321-avoiding permutations", Algorithms and Computation, Lecture Notes in Computer Science, vol. 5878, pp. 1064–1073, arXiv:1511.01770, doi:10.1007/978-3-642-10631-6_107
  27. ↑ Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Discrete Mathematics & Theoretical Computer Science, 18 (2), arXiv:1510.06051, doi:10.46298/dmtcs.1308, S2CID 5827603
  28. ↑ 28.0 28.1 28.2 Price, Alkes (1997), Packing densities of layered patterns, Ph.D. thesis, University of Pennsylvania.
  29. ↑ Albert, Michael H.; Atkinson, M. D.; Handley, C. C.; Holton, D. A.; Stromquist, W. (2002), "On packing densities of permutations", Electronic Journal of Combinatorics, 9: Research article 5, 20 pp, doi:10.37236/1622, MR 1887086.
  30. ↑ Presutti, Cathleen Battiste; Stromquist, Walter (2010), "Packing rates of measures and a conjecture for the packing density of 2413", in Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Permutation Patterns, London Math. Soc. Lecture Notes, vol. 376, Cambridge University Press, pp. 287–316, doi:10.1017/CBO9780511902499.015.
  31. ↑ Arratia, Richard (1999), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics, 6: N1, doi:10.37236/1477, MR 1710623.
  32. ↑ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, doi:10.1080/00029890.2021.1835384
  33. ↑ Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation", Annals of Combinatorics, 11 (3–4): 459–470, doi:10.1007/s00026-007-0329-7, MR 2376116, S2CID 2021533.
  34. ↑ Babson, Erik; Steingrímsson, Einar (2000), "Generalized permutation patterns and a classification of the Mahonian statistics", Séminaire Lotharingien de Combinatoire, 44: Research article B44b, 18 pp, MR 1758852.
  35. ↑ West, Julian (1993), "Sorting twice through a stack", Theoretical Computer Science, 117 (1–2): 303–313, doi:10.1016/0304-3975(93)90321-J, MR 1235186.
  36. ↑ Bousquet-Mélou, Mireille; Butler, Steve (2007), "Forest-like permutations", Annals of Combinatorics, 11 (3–4): 335–354, arXiv:math/0603617, doi:10.1007/s00026-007-0322-1, MR 2376109, S2CID 31236417.


बाहरी संबंध

Wikimedia Commons has media related to Permutation patterns.

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:

Other permutation patterns meetings:

Other links:

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=क्रमपरिवर्तन_पैटर्न&oldid=135021’