क्रमचय: Difference between revisions

{{math|''n''}} विशिष्ट वस्तुओं के क्रमपरिवर्तन की संख्या {{math|''n''}} भाज्य है, जिसे आमतौर पर {{math|''n''!}} के रूप में लिखा जाता है। जिसका अर्थ है {{math|''n''}} से कम या उसके बराबर सभी धनात्मक पूर्णांकों का गुणनफल।

सेट के सभी क्रमपरिवर्तनों का संग्रह एक [[ समूह (गणित) |समूह (गणित)]] बनाता है जिसे सेट के [[ सममित समूह |सममित समूह]] कहा जाता है। समूह संचालन [[संरचना]] है (उत्तराधिकार में दो दी गई व्यवस्थाओं का प्रदर्शन), जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण सेट तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अक्सर सेट के क्रमपरिवर्तन होते हैं <math>\{1, 2, \ldots, n\}</math> जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है।

प्राथमिक कॉम्बिनेटरिक्स में, {{math|''k''}}-क्रमपरिवर्तन, या [[ आंशिक क्रमपरिवर्तन |आंशिक क्रमपरिवर्तन]], एक सेट से चुने गए {{math|''k''}} विशिष्ट तत्वों की क्रमबद्ध व्यवस्था है। जब k समुच्चय के आकार के बराबर होता है, तो ये समुच्चय के क्रमचय होते हैं।

अरब गणितज्ञ [[ अल-खलील इब्न अहमद अल-फ़राहिदी | अल-खलील इब्न अहमद अल-फ़राहिदी]] अल-खलील (717-786) और क्रिप्टोग्राफर ने क्रिप्टोग्राफ़िक संदेशों की पुस्तक लिखी। इसमें स्वरों के साथ और बिना सभी संभावित [[अरबी शब्दों]] को सूचीबद्ध करने के लिए क्रमचय और संयोजन का पहला उपयोग शामिल है।<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=अरब क्रिप्टोलॉजी में प्रारंभिक सांख्यिकीय अनुमान का लेखा|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

n वस्तुओं के क्रमचय की संख्या निर्धारित करने का नियम भारतीय संस्कृति में लगभग 1150 AD के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा [[ लीलावती |लीलावती]] में एक मार्ग शामिल है जो इसका अनुवाद करता है:<blockquote>अंकगणितीय श्रृंखला के गुणन का गुणनफल एकता से शुरू और बढ़ता है और स्थानों की संख्या तक जारी रहता है, विशिष्ट अंकों के साथ संख्या की भिन्नता होगी।<ref>{{cite journal |first=N. L. |last=Biggs |title=कॉम्बिनेटरिक्स की जड़ें|journal=Historia Math. |volume=6 |year=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access=free }}</ref></blockquote>1677 में, [[फैबियन स्टैडमैन]] ने [[चेंजिंग रिंगिंग]] में घंटियों के क्रमपरिवर्तन की संख्या की व्याख्या करते हुए फैक्टोरियल्स का वर्णन किया। दो घंटियों से शुरू करते हुए: "पहले, दो को दो तरीकों से भिन्न होने के लिए स्वीकार किया जाना चाहिए", जिसे वह 1 2 और 2 1 दिखा कर दिखाता है।{{sfn|Stedman|1677|p=4}} इसके बाद वह बताते हैं कि तीन घंटियों के साथ "तीन में से तीन गुणा दो आंकड़े उत्पन्न होते हैं" जो फिर से सचित्र है। उनकी व्याख्या में शामिल है "3 को हटा दें, और 1.2 रहेगा; 2 को हटा दें, और 1.3 रहेगा; 1 को हटा दें, और 2.3 रहेगा"।{{sfn|Stedman|1677|p=5}}  फिर वह चार घंटियों की ओर बढ़ता है और यह दर्शाता है कि तीन के चार अलग-अलग सेट होंगे। प्रभावी रूप से, यह एक पुनरावर्ती प्रक्रिया है। वह "कास्टिंग अवे" पद्धति का उपयोग करते हुए पांच घंटियों के साथ आगे बढ़ता है और परिणामी 120 संयोजनों को सारणीबद्ध करता है।{{sfn|Stedman|1677|pp=6—7}}  इस बिंदु पर वह हार मान लेता है और टिप्पणी करता है:<blockquote>अब इन विधियों की प्रकृति ऐसी है कि एक संख्या में परिवर्तन सभी छोटी संख्याओं में परिवर्तन को समझ लेता है, ... इतना अधिक है कि एक संख्या पर परिवर्तनों का एक पूर्ण समूह सभी कम संख्याओं के पूर्ण अंकों को एक पूरे निकाय में एकजुट करके बनने लगता है;{{sfn|Stedman|1677|p=8}}</blockquote>स्टैडमैन क्रमपरिवर्तन के विचार को विस्तृत करता है; वह 20 के एक स्थिर से वर्णमाला के अक्षरों और घोड़ों के क्रमपरिवर्तन की संख्या पर विचार करता है।{{sfn|Stedman|1677|pp=13—18}}

क्रमचय का सबसे सरल उदाहरण पुनरावृत्ति के बिना क्रमचय है जहाँ हम {{mvar|n}} वस्तुओं को {{mvar|n}} स्थानों में व्यवस्थित करने के संभावित तरीकों की संख्या पर विचार करते हैं। एक सेट में क्रमपरिवर्तन की संख्या को परिभाषित करने के लिए फैक्टोरियल का विशेष अनुप्रयोग होता है जिसमें पुनरावृत्ति शामिल नहीं होती है। संख्या {{mvar|n}}!, "{{mvar|n}} फैक्टोरियल" पढ़ें, वास्तव में उन तरीकों की संख्या है जिनसे हम {{mvar|n}} चीजों को एक नए क्रम में पुनर्व्यवस्थित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास तीन फल हैं: एक संतरा, सेब और नाशपाती, तो हम उन्हें बताए गए क्रम में खा सकते हैं, या हम उन्हें बदल सकते हैं (उदाहरण के लिए, एक सेब, एक नाशपाती फिर एक संतरा)। तब क्रमचय की सही संख्या है <math>3! = 1 \cdot 2 \cdot 3 = 6</math> आइटमों की संख्या ({{mvar|n}}) बढ़ने पर यह संख्या बहुत बड़ी हो जाती है।

इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे <math>nPk</math> (जो "n permute k" पढ़ता है) के रूप में लिखा जा सकता है, और संख्या <math>n (n-1) \cdots (n - k + 1)</math> के बराबर है। <math>n (n-1) \cdots (n - k + 1)</math> (जिसे {{nowrap|<math>n! / (n-k)!</math>).}} के रूप में भी लिखा जाता है)<ref>{{Cite web| title=संयोजन और क्रमपरिवर्तन| url=https://www.mathsisfun.com/combinatorics/combinations-permutations.html| access-date=2020-09-10| website=www.mathsisfun.com}}</ref><ref>{{Cite web| last=Weisstein|first=Eric W.| title=परिवर्तन| url=https://mathworld.wolfram.com/परिवर्तन.html| access-date=2020-09-10| website=mathworld.wolfram.com| language=en}}</ref>

गणित के ग्रंथों में यह लोअरकेस ग्रीक अक्षरों का उपयोग करके क्रमचय को निरूपित करने के लिए प्रथागत है। आमतौर पर, या तो <math>\alpha</math> और <math>\beta</math> , या <math>\sigma, \tau</math> और <math>\pi</math>  उपयोग किया गया हैं।<ref name="Scheinerman">{{cite book |last1=Scheinerman |first1=Edward A. |date=March 5, 2012 |chapter=Chapter 5: Functions |title=गणित: एक असतत परिचय|chapter-url=https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |url-status=live |edition=3rd |publisher=Cengage Learning |page=188 |isbn=978-0840049421 |archive-url=https://web.archive.org/web/20200205212843/https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |archive-date=February 5, 2020 |access-date=February 5, 2020 |quote=क्रमपरिवर्तन के लिए लोअरकेस ग्रीक अक्षरों (विशेषकर π, σ, और τ) का उपयोग करने की प्रथा है।}}</ref>

# [[ उलटा तत्व | उलटा तत्व]] : प्रत्येक क्रमचय के लिए <math>\pi \in S_n</math>, एक व्युत्क्रम क्रमचय मौजूद है <math>\pi^{-1} \in S_n</math>, जिससे <math>\pi\pi^{-1} = \pi^{-1}\pi = \operatorname{id}.</math>

सामान्य तौर पर, दो क्रमपरिवर्तनों का संघटन क्रम [[ विनिमेय |विनिमेय]] नहीं होता है, अर्थात, <math>\pi\sigma \neq \sigma\pi.</math>

एक क्रमचय को एक या एक से अधिक असंयुक्त चक्रों में विघटित किया जा सकता है, अर्थात्, [[ कक्षा (समूह सिद्धांत) |कक्षा (समूह सिद्धांत)]], जो कुछ तत्वों पर क्रमचय के अनुप्रयोग को बार-बार अनुरेखित करने पर मिलते हैं। उदाहरण के लिए, क्रमपरिवर्तन <math>\sigma</math> द्वारा परिभाषित <math>\sigma(7) = 7</math> 1 चक्र है, <math>(\,7\,)</math> जबकि क्रमपरिवर्तन <math>\pi</math> द्वारा परिभाषित <math>\pi(2) = 3</math> तथा <math>\pi(3) = 2</math> एक 2-चक्र है <math>(\,2\,3\,)</math> (वाक्यविन्यास के विवरण के लिए, देखें {{Section link||Cycle notation}} नीचे)। सामान्य तौर पर, k लंबाई का एक चक्र, जो k तत्वों से बना होता है, k-चक्र कहलाता है।

चूँकि क्रमचय को तत्ववार लिखना, अर्थात्, टुकड़े के कार्यों के रूप में, बोझिल है, उन्हें अधिक कॉम्पैक्ट रूप से प्रस्तुत करने के लिए कई संकेतन का आविष्कार किया गया है। साइकिल अंकन कई गणितज्ञों के लिए इसकी कॉम्पैक्टनेस और इस तथ्य के कारण एक लोकप्रिय विकल्प है कि यह एक क्रमचय की संरचना को पारदर्शी बनाता है। जब तक अन्यथा निर्दिष्ट नहीं किया जाता है, तब तक यह इस लेख में प्रयुक्त संकेतन है, लेकिन अन्य संकेतन अभी भी व्यापक रूप से उपयोग किए जाते हैं, विशेष रूप से अनुप्रयोग क्षेत्रों में।

यदि S के तत्वों के लिए "प्राकृतिक" क्रम है,{{efn|The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.}} कहें <math>x_1, x_2, \ldots, x_n</math>, तो कोई इसे दो-पंक्ति नोटेशन की पहली पंक्ति के लिए उपयोग करता है:

अर्थात्, एस के तत्वों की एक व्यवस्थित व्यवस्था के रूप में।<ref>{{harvnb|Bogart|1990|p=17}}</ref><ref>{{harvnb|Gerstein|1987|p=217}}</ref> नीचे वर्णित चक्र संकेतन से एक-पंक्ति संकेतन को अलग करने के लिए सावधानी बरतनी चाहिए। गणित साहित्य में, चक्र संकेतन के लिए उनका उपयोग करते समय, एक-पंक्ति संकेतन के लिए कोष्ठकों को छोड़ना एक सामान्य उपयोग है। एक-पंक्ति संकेतन को क्रमपरिवर्तन का [[ शब्द (गणित) |शब्द (गणित)]] निरूपण भी कहा जाता है।<ref name="Aigner2007">{{cite book|first=Martin|last= Aigner|title=गणना में एक कोर्स|url=https://archive.org/details/courseenumeratio00aign_007|url-access=limited|year=2007|publisher=Springer GTM 238|isbn=978-3-540-39035-0|pages=[https://archive.org/details/courseenumeratio00aign_007/page/n32 24]–25}}</ref> उपरोक्त उदाहरण तब {{nowrap|2 5 4 3 1}} होगा क्योंकि पहली पंक्ति के लिए प्राकृतिक क्रम {{nowrap|1 2 3 4 5}} माना जाएगा। (इन प्रविष्टियों को केवल तभी अलग करने के लिए अल्पविराम का उपयोग करना विशिष्ट है, जब कुछ में दो या दो से अधिक अंक हों।) यह फॉर्म अधिक कॉम्पैक्ट है, और प्राथमिक कॉम्बिनेटरिक्स और कंप्यूटर साइंस में आम है। यह उन अनुप्रयोगों में विशेष रूप से उपयोगी है जहां S के तत्वों या क्रमचय की तुलना बड़े या छोटे के रूप में की जानी है।

# फिर x की कक्षा का पता लगाएं; यानी, <math>\sigma</math> : <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots</math> के क्रमिक अनुप्रयोगों के तहत इसके मूल्यों को लिखें।

#तब तक दोहराएं जब तक कि मान x पर वापस न आ जाए और x के बजाय समापन कोष्ठक लिखें: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)</math>

जबकि सामान्य रूप से क्रमपरिवर्तन नहीं करते हैं, अलग-अलग चक्र करते हैं; उदाहरण के लिए,<math display="block">(\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,3 \, 4\,) (\,1 \, 2 \, 5\,).</math>इसके अलावा, अलग-अलग शुरुआती बिंदुओं को चुनकर, प्रत्येक चक्र को अलग-अलग तरीकों से लिखा जा सकता है; उदाहरण के लिए,<math display="block">(\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,5 \, 1 \, 2\,)(\,3 \, 4\,) = (\,2 \, 5 \, 1\,)(\,4 \, 3\,).</math>एक दिए गए क्रमपरिवर्तन के अलग-अलग चक्रों को कई अलग-अलग तरीकों से लिखने के लिए कोई भी इन समानताओं को जोड़ सकता है।

चक्र संकेतन की एक सुविधाजनक विशेषता यह है कि व्युत्क्रम क्रमचय का चक्र अंकन क्रमचय के चक्रों में तत्वों के क्रम को उलट कर दिया जाता है। उदाहरण के लिए,<math display="block">[(\,1\,2\,5\,)(\,3\,4\,)]^{-1} = (\,5\,2\,1\,)(\,4\,3\,).</math>

रिचर्ड पी. स्टेनली प्रतिनिधित्व के समान विकल्प को क्रमचय का "मानक प्रतिनिधित्व" कहते हैं,<ref name="Stanley2012">{{cite book|first=Richard P.|last= Stanley|title=संख्यात्मक संयोजन: खंड I, दूसरा संस्करण|year=2012|publisher=Cambridge University Press|isbn=978-1-107-01542-5|page=23}}</ref>और मार्टिन एग्नर इसी धारणा के लिए "मानक रूप" शब्द का प्रयोग करते हैं।<ref name="Aigner2007" /> सर्गेई किताएव भी "मानक रूप" शब्दावली का उपयोग करते हैं, लेकिन दोनों विकल्पों को उलट देते हैं; अर्थात्, प्रत्येक चक्र अपने सबसे छोटे तत्व को पहले सूचीबद्ध करता है और चक्रों को उनके सबसे कम यानी पहले तत्वों के घटते क्रम में क्रमबद्ध किया जाता है।<ref name="Kitaev2011">{{cite book|first=Sergey |last=Kitaev|title=क्रमपरिवर्तन और शब्दों में पैटर्न|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-17333-2|page=119}}</ref>

क्योंकि फ़ंक्शन एप्लिकेशन जिस तरह से लिखा गया है। चूँकि फ़ंक्शन रचना साहचर्य है, इसलिए क्रमपरिवर्तन पर रचना संचालन है: <math>(\sigma\pi)\tau = \sigma(\pi\tau)</math> इसलिए, दो से अधिक क्रमचयों के गुणनफल आमतौर पर व्यक्त समूहन में कोष्ठक जोड़े बिना लिखे जाते हैं; वे आमतौर पर रचना को इंगित करने के लिए बिना किसी बिंदु या अन्य चिह्न के भी लिखे जाते हैं। कुछ लेखक सबसे बाएं कारक को पहले अभिनय करना पसंद करते हैं, ,<ref>

लेकिन इसके लिए क्रमचय को उनके तर्क के दाईं ओर लिखा जाना चाहिए, अक्सर एक प्रतिपादक के रूप में, जहाँ σ^x पर अभिनय करते हुए x^σ लिखा जाता है; तो उत्पाद को {{nowrap|''x''^''σ·π'' {{=}} (''x''^''σ'')^''π''}} द्वारा परिभाषित किया जाता है। हालाँकि यह क्रमपरिवर्तन को गुणा करने के लिए एक अलग नियम देता है; यह लेख उस परिभाषा का उपयोग करता है जहां सबसे सही क्रमचय पहले लागू किया जाता है।

शब्द क्रमचय का एक कमजोर अर्थ, कभी-कभी प्राथमिक कॉम्बिनेटरिक्स ग्रंथों में उपयोग किया जाता है, उन क्रमबद्ध व्यवस्थाओं को निर्दिष्ट करता है जिसमें कोई तत्व एक से अधिक बार नहीं होता है, लेकिन किसी दिए गए सेट से सभी तत्वों का उपयोग करने की आवश्यकता के बिना। विशेष मामलों को छोड़कर ये क्रमपरिवर्तन नहीं हैं, बल्कि आदेशित व्यवस्था अवधारणा के प्राकृतिक सामान्यीकरण हैं। वास्तव में, इस प्रयोग में अक्सर आकार n के दिए गए सेट से लिए गए तत्वों की एक निश्चित लंबाई k की व्यवस्था पर विचार करना शामिल होता है, दूसरे शब्दों में, n के ये k-क्रमपरिवर्तन एक n-सेट के k-तत्व उपसमुच्चय की अलग-अलग क्रमबद्ध व्यवस्थाएँ हैं (कभी-कभी इसे पुराने साहित्य में विविधता या व्यवस्था कहा जाता है{{efn|More precisely, ''variations without repetition''. The term is still common in other languages and appears in modern English most often in translation.}})। इन वस्तुओं को आंशिक क्रमपरिवर्तन या पुनरावृत्ति के बिना अनुक्रम के रूप में भी जाना जाता है, ऐसे शब्द जो "क्रमपरिवर्तन" के दूसरे, अधिक सामान्य अर्थ के साथ भ्रम से बचते हैं। <math>n</math> के ऐसे <math>k</math>-क्रमपरिवर्तनों की संख्या को  <math>P^n_k</math>,  <math>_nP_k</math>, <math>