क्रमचय: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 166: Line 166:


=== दोहराव के साथ क्रमपरिवर्तन ===
=== दोहराव के साथ क्रमपरिवर्तन ===
'''एक समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है,''' Tuple|k-tuples कहलाती है। उन्हें कभी-कभी 'पुनरावृत्ति के साथ क्रमपरिवर्तन' के रूप में संदर्भित किया जाता है, हालांकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। कुछ संदर्भों में उन्हें अक्षर S के ऊपर शब्द (गणित) भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S के ऊपर k-टुपल्स की संख्या है <math>n^k.</math>
समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स  कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, हालांकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स  की संख्या <math>n^k.</math> कोई तत्व k-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।
k-tuple में कोई तत्व कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार प्रकट हो सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।


=== मल्टीसेट्स के क्रमपरिवर्तन ===
=== मल्टीसेट्स के क्रमपरिवर्तन ===
[[File:Permutations with repetition.svg|thumb|मल्टीसेट के क्रमपरिवर्तन]]यदि M एक परिमित [[ मल्टीसेट ]] है, तो एक 'मल्टीसेट क्रमचय' M के तत्वों की एक क्रमबद्ध व्यवस्था है जिसमें प्रत्येक तत्व M में अपनी बहुलता के बराबर कई बार दिखाई देता है। कुछ दोहराए गए अक्षरों वाले शब्द का विपर्यय एक उदाहरण है एक मल्टीसेट क्रमचय का।{{efn|The natural order in this example is the order of the letters in the original word.}} यदि M के तत्वों का गुणन (किसी क्रम में लिया गया) हैं <math>m_1</math>, <math>m_2</math>, ..., <math>m_l</math> और उनका योग (अर्थात M का आकार) n है, तो M के बहुसेट क्रमपरिवर्तन की संख्या बहुपद गुणांक # बहुपद गुणांक द्वारा दी जाती है,<ref>{{harvnb|Brualdi|2010|loc=p. 46, Theorem 2.4.2}}</ref>
[[File:Permutations with repetition.svg|thumb|मल्टीसेट के क्रमपरिवर्तन]]यदि एम एक परिमित [[मल्टीसेट]] है, तो एक मल्टीसेट क्रमचय एम के तत्वों की एक क्रमबद्ध व्यवस्था है जिसमें प्रत्येक तत्व एम में इसकी बहुलता के बराबर बार-बार प्रकट होता है। कुछ दोहराए गए अक्षरों वाले शब्द का विपर्यय एक मल्टीसेट क्रमचय का एक उदाहरण है।{{efn|The natural order in this example is the order of the letters in the original word.}} यदि एम के तत्वों की बहुलता (किसी क्रम में ली गई) <math>m_1</math>, <math>m_2</math>, ..., <math>m_l</math> और उनका योग (अर्थात्, M का आकार) n है, तो M के बहु-सेट क्रमपरिवर्तनों की संख्या बहुपद गुणांक द्वारा दी जाती है,<ref>{{harvnb|Brualdi|2010|loc=p. 46, Theorem 2.4.2}}</ref>
:<math>
:<math>
   {n \choose m_1, m_2, \ldots, m_l} =
   {n \choose m_1, m_2, \ldots, m_l} =
Line 176: Line 175:
   \frac{\left(\sum_{i=1}^l{m_i}\right)!}{\prod_{i=1}^l{m_i!}}.
   \frac{\left(\sum_{i=1}^l{m_i}\right)!}{\prod_{i=1}^l{m_i!}}.
</math>
</math>
उदाहरण के लिए, MISSISSIPPI शब्द के अलग-अलग विपर्यय की संख्या है:<ref>{{harvnb|Brualdi|2010|p=47}}</ref>
उदाहरण के लिए, मिसीसिपी शब्द के अलग-अलग विपर्यय की संख्या है:<ref>{{harvnb|Brualdi|2010|p=47}}</ref>
:<math>\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650</math>.
:<math>\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650</math>.


A ''k''-एक मल्टीसेट ''M'' का क्रमपरिवर्तन ''M'' के तत्वों की लंबाई ''k'' का एक क्रम है जिसमें प्रत्येक तत्व '' से कई बार कम या बराबर दिखाई देता है '' इसकी बहुलता ''एम'' (एक तत्व की ''पुनरावृत्ति संख्या'') में है।
मल्टीसेट M का k-क्रमपरिवर्तन, M के तत्वों की लंबाई k का अनुक्रम है जिसमें प्रत्येक तत्व एम में अपनी बहुलता से कई गुना कम या उसके बराबर दिखाई देता है (एक तत्व की पुनरावृत्ति संख्या)।


=== परिपत्र क्रमपरिवर्तन ===
=== परिपत्र क्रमपरिवर्तन ===
क्रमपरिवर्तन, जब व्यवस्था के रूप में माना जाता है, कभी-कभी रैखिक रूप से आदेशित व्यवस्था के रूप में संदर्भित किया जाता है। इन व्यवस्थाओं में एक पहला तत्व, दूसरा तत्व आदि होता है। यदि, हालांकि, वस्तुओं को एक गोलाकार तरीके से व्यवस्थित किया जाता है, तो यह विशिष्ट क्रम अब मौजूद नहीं है, अर्थात व्यवस्था में कोई पहला तत्व नहीं है, किसी भी तत्व को व्यवस्था की शुरुआत के रूप में माना जा सकता है। वृत्ताकार ढंग से वस्तुओं की व्यवस्था 'वृत्ताकार क्रमपरिवर्तन' कहलाती है।<ref>{{harvnb|Brualdi|2010|p=39}}</ref>{{efn|In older texts ''circular permutation'' was sometimes used as a synonym for [[cyclic permutation]], but this is no longer done. See {{harvtxt|Carmichael|1956|p=7}}}} इन्हें औपचारिक रूप से वस्तुओं के सामान्य क्रमपरिवर्तन के [[ तुल्यता वर्ग ]] के रूप में परिभाषित किया जा सकता है, रेखीय व्यवस्था के अंतिम तत्व को उसके सामने ले जाने से उत्पन्न [[ तुल्यता संबंध ]] के लिए।
क्रमपरिवर्तन, जब व्यवस्था के रूप में माना जाता है, कभी-कभी रैखिक रूप से आदेशित व्यवस्था के रूप में संदर्भित किया जाता है। इन व्यवस्थाओं में एक पहला तत्व है, एक दूसरा तत्व है, इत्यादि। यदि, तथापि, वस्तुओं को एक वृत्ताकार तरीके से व्यवस्थित किया जाता है, तो यह विशिष्ट क्रम अब मौजूद नहीं है, अर्थात, व्यवस्था में कोई "पहला तत्व" नहीं है, किसी भी तत्व को व्यवस्था की शुरुआत माना जा सकता है। वस्तुओं की एक वृत्ताकार तरीके से व्यवस्था को वृत्तीय क्रमचय कहा जाता है।<ref>{{harvnb|Brualdi|2010|p=39}}</ref>{{efn|In older texts ''circular permutation'' was sometimes used as a synonym for [[cyclic permutation]], but this is no longer done. See {{harvtxt|Carmichael|1956|p=7}}}} इन्हें औपचारिक रूप से वस्तुओं के सामान्य क्रमपरिवर्तन के [[ तुल्यता वर्ग |तुल्यता वर्ग]] के रूप में परिभाषित किया जा सकता है, रेखीय व्यवस्था के अंतिम तत्व को उसके सामने ले जाने से उत्पन्न [[ तुल्यता संबंध | तुल्यता संबंध]] के लिए।  


दो गोलाकार क्रमपरिवर्तन समतुल्य होते हैं यदि एक को दूसरे में घुमाया जा सकता है (अर्थात, तत्वों की सापेक्ष स्थिति को बदले बिना चक्रित किया जाता है)। चार अक्षरों पर निम्नलिखित चार वृत्तीय क्रमचय एक समान माने जाते हैं।
दो गोलाकार क्रमपरिवर्तन समतुल्य होते हैं यदि एक को दूसरे में घुमाया जा सकता है (अर्थात, तत्वों की सापेक्ष स्थिति को बदले बिना चक्रित किया जाता है)। चार अक्षरों पर निम्नलिखित चार वृत्तीय क्रमचय एक समान माने जाते हैं।
<पूर्व>
     1 4 2 3
     1 4 2 3
   4 3 2 1 3 4 1 2
   4 3 2 1 3 4 1 2
     2 3 1 4
     2 3 1 4
</पूर्व>
परिपत्र व्यवस्था को वामावर्त पढ़ा जाना है, इसलिए निम्नलिखित दो समतुल्य नहीं हैं क्योंकि कोई भी घूर्णन एक को दूसरे पर नहीं ला सकता है।
 
वृत्ताकार व्यवस्था को वामावर्त पढ़ा जाना है, इसलिए निम्नलिखित दो समतुल्य नहीं हैं क्योंकि कोई भी घुमाव एक को दूसरे पर नहीं ला सकता है।
<पूर्व>
     1 1
     1 1
   4 3 3 4
   4 3 3 4
Line 201: Line 195:


== गुण ==
== गुण ==
के क्रमपरिवर्तन की संख्या {{math|''n''}} भिन्न वस्तु है {{math|''n''}}!.
{{math|''n''}} विशिष्ट वस्तुओं के क्रमचय की संख्या {{math|''n''}}! है।


की संख्या {{math|''n''}}-के साथ क्रमपरिवर्तन {{math|''k''}} असंयुक्त चक्र पहली तरह की सांकेतिक स्टर्लिंग संख्या है, जिसे द्वारा निरूपित किया जाता है {{math|''c''(''n'', ''k'')}}.{{sfn|Bona|2012|pp=97–103}}
{{math|''k''}} असंयुक्त चक्रों के साथ {{math|''n''}}-क्रमपरिवर्तनों की संख्या पहले प्रकार की सांकेतिक स्टर्लिंग संख्या है, जिसे {{math|''c''(''n'', ''k'')}} द्वारा निरूपित किया जाता है।{{sfn|Bona|2012|pp=97–103}}


=== साइकिल का प्रकार ===
क्रमपरिवर्तन <math>\sigma</math> के {{mvar|n}} तत्वों के विभाजन वाले सेट के चक्र (निश्चित बिंदुओं सहित); इसलिए इन चक्रों की लंबाई {{mvar|n}} का पूर्णांक [[ विभाजन (संख्या सिद्धांत) |विभाजन (संख्या सिद्धांत)]] बनाती है, जिसे <math>\sigma</math> का चक्र प्रकार (या कभी-कभी चक्र संरचना या चक्र आकार) कहा जाता है। <math>\sigma</math> के प्रत्येक निश्चित बिंदु के लिए चक्र प्रकार में एक "1" है, प्रत्येक स्थानान्तरण के लिए एक "2", इत्यादि। चक्र का प्रकार <math>\beta = (1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)</math><math>(3, 2, 2, 1).</math> है, इसे अधिक संक्षिप्त रूप में {{math|[1<sup>1</sup>2<sup>2</sup>3<sup>1</sup>]}} के रूप में भी लिखा जा सकता है।


=== साइकिल का प्रकार ===
अधिक सटीक रूप से, सामान्य रूप है <math>[1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}]</math>, जहां <math>\alpha_1,\ldots,\alpha_n</math> संबंधित लंबाई के चक्रों की संख्या हैं। किसी दिए गए चक्र प्रकार के क्रमचय की संख्या है<ref>{{citation|last = Sagan|first = Bruce|title = The Symmetric Group|publisher = Springer | date = 2001 | edition = 2 | page = 3}}</ref>
<!-- linked from redirects [[Cycle type]], [[Cycle structure]], and [[Cycle shape]] -->
क्रमचय के चक्र (निश्चित बिंदुओं सहित)। <math>\sigma</math> के साथ एक सेट के {{mvar|n}} तत्वों का विभाजन जो सेट करता है; इसलिए इन चक्रों की लंबाई का एक [[ विभाजन (संख्या सिद्धांत) ]] बनाते हैं {{mvar|n}}, जिसे चक्र प्रकार (या कभी-कभी चक्र संरचना या चक्र आकार) कहा जाता है <math>\sigma</math>. के प्रत्येक निश्चित बिंदु के लिए चक्र प्रकार में 1 है <math>\sigma</math>, प्रत्येक स्थानान्तरण के लिए 2, इत्यादि। चक्र प्रकार <math>\beta = (1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)</math> है <math>(3, 2, 2, 1).</math> इसे अधिक संक्षिप्त रूप में भी लिखा जा सकता है: {{math|[1<sup>1</sup>2<sup>2</sup>3<sup>1</sup>]}}.
अधिक सटीक, सामान्य रूप है <math>[1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}]</math>, कहाँ पे <math>\alpha_1,\ldots,\alpha_n</math> संबंधित लंबाई के चक्रों की संख्या है। किसी दिए गए चक्र प्रकार के क्रमचय की संख्या है<ref>{{citation|last = Sagan|first = Bruce|title = The Symmetric Group|publisher = Springer | date = 2001 | edition = 2 | page = 3}}</ref>
: <math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}\alpha_1!\alpha_2!\dotsm \alpha_n!}</math>.
: <math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}\alpha_1!\alpha_2!\dotsm \alpha_n!}</math>.


Line 216: Line 209:


=== क्रमचय क्रम ===
=== क्रमचय क्रम ===
एक क्रमचय का क्रम <math>\sigma</math> सबसे छोटा धनात्मक पूर्णांक m है जिससे कि <math>\sigma^m = \mathrm{id}</math>. यह इसके चक्रों की लंबाई का कम से कम सामान्य गुणक है। उदाहरण के लिए, का क्रम <math>(\,1\,3\,2)(\,4\,5\,)</math> है <math>2\cdot3 = 6</math>.
एक क्रमचय का क्रम <math>\sigma</math> सबसे छोटा सकारात्मक पूर्णांक m है ताकि <math>\sigma^m = \mathrm{id}</math> { पहचान} }। यह इसके चक्रों की लंबाई का कम से कम सामान्य गुणक है। उदाहरण के लिए, <math>(\,1\,3\,2)(\,4\,5\,)</math> <math>2\cdot3 = 6</math> है।


=== क्रमपरिवर्तन की समता ===
=== क्रमपरिवर्तन की समता ===
{{main|Parity of a permutation}}
{{main|एक क्रमचय की समानता}}
परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है।<ref>{{harvnb|Hall|1959|p=60}}</ref>
हालांकि एक दिए गए क्रमचय के लिए ऐसे कई भाव मौजूद हो सकते हैं, या तो उन सभी में समान संख्या में ट्रांसपोज़िशन होते हैं या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमपरिवर्तनों को इस संख्या के आधार पर [[ सम और विषम क्रमपरिवर्तन ]]ों के रूप में वर्गीकृत किया जा सकता है।


इस परिणाम को बढ़ाया जा सकता है ताकि एक चिन्ह, लिखित रूप में निर्दिष्ट किया जा सके <math>\operatorname{sgn}\sigma</math>, प्रत्येक क्रमपरिवर्तन के लिए। <math>\operatorname{sgn}\sigma = +1</math> यदि <math>\sigma</math> सम है और <math>\operatorname{sgn}\sigma = -1</math> यदि <math>\sigma</math> अजीब है। फिर दो क्रमपरिवर्तन के लिए <math>\sigma</math> तथा <math>\pi</math>
परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है। [36] हालांकि एक दिए गए क्रमचय के लिए ऐसे कई व्यंजक मौजूद हो सकते हैं, या तो उन सभी में ट्रांसपोज़िशन की एक समान संख्या होती है या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमचयों को इस संख्या के आधार पर [[सम या विषम के रूप में वर्गीकृत]] किया जा सकता है।
 
इस परिणाम को बढ़ाया जा सकता है ताकि प्रत्येक क्रमचय के लिए <math>\operatorname{sgn}\sigma</math> लिखा हुआ एक चिह्न निर्दिष्ट किया जा सके। <math>\operatorname{sgn}\sigma = +1</math> अगर <math>\sigma</math> सम है और <math>\operatorname{sgn}\sigma = -1</math> यदि <math>\sigma</math> विषम है। फिर दो क्रमपरिवर्तन के लिए <math>\sigma</math> तथा <math>\pi</math>
: <math>\operatorname{sgn}(\sigma\pi) = \operatorname{sgn}\sigma\cdot\operatorname{sgn}\pi.</math>
: <math>\operatorname{sgn}(\sigma\pi) = \operatorname{sgn}\sigma\cdot\operatorname{sgn}\pi.</math>
यह इस प्रकार है कि <math>\operatorname{sgn}\left(\sigma\sigma^{-1}\right) = +1.</math>
यह इस प्रकार है कि <math>\operatorname{sgn}\left(\sigma\sigma^{-1}\right) = +1.</math>
=== मैट्रिक्स प्रतिनिधित्व ===
=== मैट्रिक्स प्रतिनिधित्व ===
{{main|Permutation matrix}}
{{main|क्रमपरिवर्तन मैट्रिक्स}}
एक क्रमचय मैट्रिक्स एक वर्ग मैट्रिक्स | n × n मैट्रिक्स है जिसमें प्रत्येक स्तंभ और प्रत्येक पंक्ति में ठीक एक प्रविष्टि 1 है, और अन्य सभी प्रविष्टियाँ 0 हैं। कई अलग-अलग सम्मेलन हैं जिनका उपयोग क्रमचय मैट्रिक्स को एक क्रमपरिवर्तन के लिए निर्दिष्ट करने के लिए किया जा सकता है। {1, 2, ..., एन} का। एक प्राकृतिक दृष्टिकोण क्रमचय σ मैट्रिक्स से संबद्ध करना है <math>M_{\sigma}</math> जिसकी (i, j) प्रविष्टि 1 है यदि i = σ(j) और अन्यथा 0 है। इस परिपाटी के दो आकर्षक गुण हैं: पहला, आव्यूहों और क्रमपरिवर्तनों का गुणनफल एक ही क्रम में है, अर्थात्, <math>M_\sigma M_\pi = M_{\sigma\circ\pi}</math> सभी क्रमपरिवर्तन σ और π के लिए। दूसरा, अगर <math>{\bf e}_i</math> [[ मानक आधार ]] का प्रतिनिधित्व करता है <math>n \times 1</math> [[ स्तंभ वेक्टर ]] (1 के बराबर ith प्रविष्टि वाला वेक्टर और 0 के बराबर अन्य सभी प्रविष्टियाँ), फिर <math>M_\sigma {\bf e}_i = {\bf e}_{\sigma(i)}</math>.
एक क्रमचय मैट्रिक्स एक वर्ग मैट्रिक्स | n × n मैट्रिक्स है जिसमें प्रत्येक स्तंभ और प्रत्येक पंक्ति में ठीक एक प्रविष्टि 1 है, और अन्य सभी प्रविष्टियाँ 0 हैं। कई अलग-अलग सम्मेलन हैं जिनका उपयोग क्रमचय मैट्रिक्स को एक क्रमपरिवर्तन के लिए निर्दिष्ट करने के लिए किया जा सकता है। {1, 2, ..., एन} का। एक प्राकृतिक दृष्टिकोण क्रमचय σ मैट्रिक्स से संबद्ध करना है <math>M_{\sigma}</math> जिसकी (i, j) प्रविष्टि 1 है यदि i = σ(j) और अन्यथा 0 है। इस परिपाटी के दो आकर्षक गुण हैं: पहला, आव्यूहों और क्रमपरिवर्तनों का गुणनफल एक ही क्रम में है, अर्थात्, <math>M_\sigma M_\pi = M_{\sigma\circ\pi}</math> सभी क्रमपरिवर्तन σ और π के लिए। दूसरा, अगर <math>{\bf e}_i</math> [[ मानक आधार ]] का प्रतिनिधित्व करता है <math>n \times 1</math> [[ स्तंभ वेक्टर ]] (1 के बराबर ith प्रविष्टि वाला वेक्टर और 0 के बराबर अन्य सभी प्रविष्टियाँ), फिर <math>M_\sigma {\bf e}_i = {\bf e}_{\sigma(i)}</math>.


Line 236: Line 227:
M_{(2, 1, 3)} M_{(2, 3, 1)} = \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} = \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} = M_{(1, 3, 2)}.</math>
M_{(2, 1, 3)} M_{(2, 3, 1)} = \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} = \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} = M_{(1, 3, 2)}.</math>


[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|क्रमचय आव्यूहों के गुणन के संगत क्रमचयों की संरचना।]]साहित्य में व्युत्क्रम परिपाटी का पता लगाना भी आम है, जहां एक क्रमचय σ मैट्रिक्स से जुड़ा होता है <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> जिसकी (i, j) प्रविष्टि 1 है यदि j = σ(i) और अन्यथा 0 है। इस परिपाटी में, क्रमचय आव्यूह क्रमचय से विपरीत क्रम में गुणा करते हैं, अर्थात्, <math>P_\sigma P_{\pi} = P_{\pi \circ \sigma}</math> सभी क्रमपरिवर्तन σ और π के लिए। इस पत्राचार में, क्रमचय मेट्रिसेस मानक के सूचकांकों की अनुमति देकर कार्य करते हैं <math>1 \times n</math> पंक्ति वैक्टर <math>({\bf e}_i)^T</math>: किसी के पास <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>.
[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|क्रमचय आव्यूहों के गुणन के संगत क्रमचयों की संरचना।]]'''साहित्य में व्युत्क्रम परिपाटी का पता लगाना भी आम''' है, जहां एक क्रमचय σ मैट्रिक्स से जुड़ा होता है <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> जिसकी (i, j) प्रविष्टि 1 है यदि j = σ(i) और अन्यथा 0 है। इस परिपाटी में, क्रमचय आव्यूह क्रमचय से विपरीत क्रम में गुणा करते हैं, अर्थात्, <math>P_\sigma P_{\pi} = P_{\pi \circ \sigma}</math> सभी क्रमपरिवर्तन σ और π के लिए। इस पत्राचार में, क्रमचय मेट्रिसेस मानक के सूचकांकों की अनुमति देकर कार्य करते हैं <math>1 \times n</math> पंक्ति वैक्टर <math>({\bf e}_i)^T</math>: किसी के पास <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>.


दाईं ओर [[ केली टेबल ]] 3 तत्वों के क्रमपरिवर्तन के लिए इन आव्यूहों को दिखाता है।
दाईं ओर [[ केली टेबल ]] 3 तत्वों के क्रमपरिवर्तन के लिए इन आव्यूहों को दिखाता है।

Revision as of 15:32, 21 November 2022

For other uses, see क्रमचय (disambiguation).
"एनपीआर" redirects here. For other uses, see एनपीआर (बहुविकल्पी).
File:Permutations RGB.svg
छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है

गणित में, एक सेट का क्रमचय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के रैखिक क्रम को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।[1]

क्रमपरिवर्तन संयोजनों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {1, 2, 3}, अर्थात् (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), और (3, 2, 1)। ये तीन-तत्वों के इस सेट के सभी संभावित क्रम हैं। जिन शब्दों के वर्ण भिन्न हैं उनके एनाग्राम भी क्रमचय हैं: अक्षरों को पहले से ही मूल शब्द में क्रमबद्ध किया गया है, और विपर्यय अक्षरों का पुनर्क्रमण है। साहचर्य और समूह सिद्धांत के क्षेत्र में परिमित सेट के क्रमपरिवर्तन का अध्ययन एक महत्वपूर्ण विषय है।

क्रमपरिवर्तन का उपयोग गणित की लगभग हर शाखा में और विज्ञान के कई अन्य क्षेत्रों में किया जाता है। कंप्यूटर विज्ञान में, उनका उपयोग सॉर्टिंग एल्गोरिदम के विश्लेषण के लिए किया जाता है; क्वांटम भौतिकी में, कणों की अवस्थाओं का वर्णन करने के लिए; और जीव विज्ञान में, आरएनए अनुक्रमों का वर्णन करने के लिए।

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

तकनीकी रूप से, समुच्चय S के क्रमचय को S से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है।[2][3] अर्थात्, यह S से S तक का एक कार्य है जिसके लिए प्रत्येक तत्व के प्रतिबिंब के मान के लिए ठीक एक बार होता है। यह S के तत्वों की पुनर्व्यवस्था से संबंधित है जिसमें प्रत्येक तत्व S को संगत f(s) द्वारा प्रतिस्थापित किया जाता है। उदाहरण के लिए, ऊपर बताए गए क्रमचय (3, 1, 2) को फ़ंक्शन के रूप में परिभाषित किया गया है

.

सेट के सभी क्रमपरिवर्तनों का संग्रह एक समूह (गणित) बनाता है जिसे सेट के सममित समूह कहा जाता है। समूह संचालन संरचना है (उत्तराधिकार में दो दी गई व्यवस्थाओं का प्रदर्शन), जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण सेट तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अक्सर सेट के क्रमपरिवर्तन होते हैं जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है।

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

File:Rubik's cube.svg
1974 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।

इतिहास

चीन में I चिंग (पिनयिन: यी जिंग) में 1000 ईसा पूर्व के रूप में हेक्साग्राम नामक क्रमपरिवर्तन का उपयोग किया गया था।

अरब गणितज्ञ अल-खलील इब्न अहमद अल-फ़राहिदी अल-खलील (717-786) और क्रिप्टोग्राफर ने क्रिप्टोग्राफ़िक संदेशों की पुस्तक लिखी। इसमें स्वरों के साथ और बिना सभी संभावित अरबी शब्दों को सूचीबद्ध करने के लिए क्रमचय और संयोजन का पहला उपयोग शामिल है।[4]

n वस्तुओं के क्रमचय की संख्या निर्धारित करने का नियम भारतीय संस्कृति में लगभग 1150 AD के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा लीलावती में एक मार्ग शामिल है जो इसका अनुवाद करता है:

अंकगणितीय श्रृंखला के गुणन का गुणनफल एकता से शुरू और बढ़ता है और स्थानों की संख्या तक जारी रहता है, विशिष्ट अंकों के साथ संख्या की भिन्नता होगी।[5]

1677 में, फैबियन स्टैडमैन ने चेंजिंग रिंगिंग में घंटियों के क्रमपरिवर्तन की संख्या की व्याख्या करते हुए फैक्टोरियल्स का वर्णन किया। दो घंटियों से शुरू करते हुए: "पहले, दो को दो तरीकों से भिन्न होने के लिए स्वीकार किया जाना चाहिए", जिसे वह 1 2 और 2 1 दिखा कर दिखाता है।[6] इसके बाद वह बताते हैं कि तीन घंटियों के साथ "तीन में से तीन गुणा दो आंकड़े उत्पन्न होते हैं" जो फिर से सचित्र है। उनकी व्याख्या में शामिल है "3 को हटा दें, और 1.2 रहेगा; 2 को हटा दें, और 1.3 रहेगा; 1 को हटा दें, और 2.3 रहेगा"।[7] फिर वह चार घंटियों की ओर बढ़ता है और यह दर्शाता है कि तीन के चार अलग-अलग सेट होंगे। प्रभावी रूप से, यह एक पुनरावर्ती प्रक्रिया है। वह "कास्टिंग अवे" पद्धति का उपयोग करते हुए पांच घंटियों के साथ आगे बढ़ता है और परिणामी 120 संयोजनों को सारणीबद्ध करता है।[8] इस बिंदु पर वह हार मान लेता है और टिप्पणी करता है:

अब इन विधियों की प्रकृति ऐसी है कि एक संख्या में परिवर्तन सभी छोटी संख्याओं में परिवर्तन को समझ लेता है, ... इतना अधिक है कि एक संख्या पर परिवर्तनों का एक पूर्ण समूह सभी कम संख्याओं के पूर्ण अंकों को एक पूरे निकाय में एकजुट करके बनने लगता है;[9]

स्टैडमैन क्रमपरिवर्तन के विचार को विस्तृत करता है; वह 20 के एक स्थिर से वर्णमाला के अक्षरों और घोड़ों के क्रमपरिवर्तन की संख्या पर विचार करता है।[10]

पहला मामला जिसमें प्रतीत होता है कि असंबद्ध गणितीय प्रश्नों का क्रमपरिवर्तन की मदद से अध्ययन किया गया था, 1770 के आसपास हुआ था, जब जोसेफ लुइस लाग्रेंज ने बहुपद समीकरणों के अध्ययन में देखा किसी समीकरण के मूलों के क्रमचय के गुण इसे हल करने की संभावनाओं से संबंधित होते हैं। काम की इस पंक्ति का परिणाम अंततः एवरिस्ट गैलोइस के काम के माध्यम से हुआ, गैलोइस सिद्धांत में, जो मूलांकों द्वारा बहुपद समीकरणों (एक अज्ञात में) को हल करने के संबंध में क्या संभव है और क्या असंभव है, इसका पूरा विवरण देता है। आधुनिक गणित में, ऐसी कई समान स्थितियाँ हैं जिनमें किसी समस्या को समझने के लिए उससे संबंधित कुछ क्रमपरिवर्तनों का अध्ययन करने की आवश्यकता होती है।

दोहराव के बिना क्रमपरिवर्तन

क्रम