क्रमचय की समानता: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 109: Line 109:
}}
}}


{{hidden|header=Proof 4|content=
{{hidden|header=प्रमाण 4|content=
Recall that a pair ''x'', ''y'' such that {{nowrap|''x'' < ''y''}} and {{nowrap|''σ''(''x'') > ''σ''(''y'')}} is called an inversion. We want to show that the count of inversions has the same parity as the count of 2-element swaps. To do that, we can show that every swap changes the parity of the count of inversions, no matter which two elements are being swapped and what permutation has already been applied.
याद रखें कि एक जोड़ी ''x'', ''y'' जैसे कि {{nowrap|''x'' <''y''}} और {{nowrap|''σ''(''x'' ) > ''σ''(''y'')}} को उलटा कहा जाता है। हम यह दिखाना चाहते हैं कि व्युत्क्रमों की गिनती में 2-तत्व स्वैप की गिनती के समान समानता है। ऐसा करने के लिए, हम दिखा सकते हैं कि प्रत्येक अदला-बदली व्युत्क्रमों की गिनती की समानता को बदल देती है, इससे कोई फर्क नहीं पड़ता कि कौन से दो तत्वों की अदला-बदली की जा रही है और कौन सा क्रमचय पहले ही लागू किया जा चुका है।
Suppose we want to swap the ''i''th and the ''j''th element. Clearly, inversions formed by ''i'' or ''j'' with an element outside of {{nowrap|[''i'', ''j'']}} will not be affected.
मान लीजिए कि हम ''i''वें और ''j''वें तत्व की अदला-बदली करना चाहते हैं। स्पष्ट रूप से, {{nowrap|[''i'', ''j'']}} के बाहर किसी तत्व के साथ ''i'' या ''j'' द्वारा गठित व्युत्क्रम प्रभावित नहीं होंगे।
For the {{nowrap|1=''n'' = ''j'' &minus; ''i'' &minus; 1}} elements within the interval {{nowrap|(''i'', ''j'')}}, assume ''v''<sub>''i''</sub> of them form inversions with ''i'' and ''v''<sub>''j''</sub> of them form inversions with ''j''. If ''i'' and ''j'' are swapped, those ''v''<sub>''i''</sub> inversions with ''i'' are gone, but {{nowrap|''n'' &minus; ''v''<sub>''i''</sub>}} inversions are formed. The count of inversions ''i'' gained is thus {{nowrap|''n'' &minus; 2''v''<sub>''i''</sub>}}, which has the same parity as ''n''.
{{nowrap|1=''n'' = ''j'' &minus; ''मैं'' &ऋण; 1}} अंतराल के भीतर तत्व {{nowrap|(''i'', ''j'')}}, मान लें कि ''v''<sub>''i''</sub> उनमें से ''i'' के साथ व्युत्क्रम बनाते हैं और''v''<sub>''j''</sub> उनमें से 'जे' के साथ व्युत्क्रम बनाते हैं। यदि ''i'' और ''j'' की अदला-बदली की जाती है, तो वो ''v''<sub>''i''</sub> उनमें से 'जे' के साथ व्युत्क्रम बनाते हैं। यदि ''i'' और ''j'' की अदला-बदली की जाती है, तो वो ''v''<sub>''i''</sub><nowiki>}} inversions are formed. The count of inversions </nowiki>''i'' gained is thus {{nowrap|''n'' &minus; 2''v''<sub>''i''</sub>}}, जिसकी समानता ''n'' के समान है।
   
   
Similarly, the count of inversions ''j'' gained also has the same parity as ''n''. Therefore, the count of inversions gained by both combined has the same parity as 2''n'' or 0. Now if we count the inversions gained (or lost) by swapping the ''i''th and the ''j''th element, we can see that this swap changes the parity of the count of inversions, since we also add (or subtract) 1 to the number of inversions gained (or lost) for the pair ''(i,j)''.
इसी प्रकार, प्राप्त व्युत्क्रम ''j'' की गणना में भी ''n'' के समान समानता है। इसलिए, दोनों संयुक्त द्वारा प्राप्त व्युत्क्रमों की संख्या में 2''n'' या 0. के समान समानता है। 'वें तत्व, हम देख सकते हैं कि यह अदला-बदली व्युत्क्रमों की गिनती की समानता को बदल देती है, क्योंकि हम जोड़ी ''(i,j)'' के लिए प्राप्त व्युत्क्रमों की संख्या में 1 जोड़ते हैं (या घटाते हैं) .
Note that initially when no swap is applied, the count of inversions is 0. Now we obtain equivalence of the two definitions of parity of a permutation.
ध्यान दें कि शुरू में जब कोई स्वैप लागू नहीं होता है, तो व्युत्क्रमों की संख्या 0 होती है। अब हम क्रमचय की समता की दो परिभाषाओं की समानता प्राप्त करते हैं।
}}
}}



Revision as of 23:11, 28 March 2023

4 तत्वों के क्रमचय

विषम क्रमपरिवर्तन की पृष्ठभूमि हरे या नारंगी रंग की होती है। दाहिने कॉलम में संख्याएँ व्युत्क्रम (असतत गणित) संख्याएँ हैं (sequence A034968 in the OEIS), जिसमें क्रमचय के समान समानता (गणित) है।

गणित में जब X कम से कम दो तत्वों के साथ एक परिमित समुच्चय होता है। तो X के क्रमचय (अर्थात X से X तक के विशेषण कार्य) समान आकार के दो वर्गों में आते हैं। 'सम क्रमपरिवर्तन' और 'विषम क्रमपरिवर्तन' यदि X का कोई कुल क्रम निश्चित है। तो क्रमपरिवर्तन की 'समता' ('विषमता' या 'समानता') X को σ के लिए व्युत्क्रमण (असतत गणित) की संख्या की समानता के रूप में परिभाषित किया जा सकता है। अर्थात X के तत्वों x,  y के जोड़े जैसे कि x < y और σ(x) > σ(y).

किसी क्रमचय σ के चिह्न हस्ताक्षर या चिह्न को sgn(σ) दर्शाया जाता है और यदि σ सम है। तो +1 के रूप में परिभाषित किया जाता है और -1 यदि σ विषम है। हस्ताक्षर सममित समूह Sn के वैकल्पिक चरित्र (गणित) को परिभाषित करता है। क्रमचय के चिह्न के लिए एक अन्य संकेत अधिक सामान्य लेवी-सिविता प्रतीक (εσ) जो X से X तक के सभी नक्शों के लिए परिभाषित है और बायजेक्शन के लिए मान शून्य है। गैर-विशेषण मानचित्र।

एक क्रमचय का संकेत स्पष्ट रूप से व्यक्त किया जा सकता है

sgn(σ) = (−1)N(σ)

जहां N(σ) σ में व्युत्क्रम (असतत गणित) की संख्या है।

वैकल्पिक रूप से क्रमचय के चिह्न σ को इसके अपघटन से स्थानान्तरण (गणित) के उत्पाद में परिभाषित किया जा सकता है।

sgn(σ) = (−1)m

जहाँ m अपघटन में स्थानान्तरण की संख्या है। चूंकि इस तरह का एक अपघटन अद्वितीय नहीं है। सभी अपघटन में परिवर्तनों की संख्या की समानता समान है। जिसका अर्थ है कि क्रमचय का संकेत अच्छी तरह से परिभाषित है।[1]


उदाहरण

सेट के क्रमचय σ पर विचार करें {1, 2, 3, 4, 5} द्वारा परिभाषित और एक-पंक्ति संकेतन में इस क्रमचय को 34521 दर्शाया गया है। इसे पहचान क्रमचय 12345 से तीन परिवर्तनों द्वारा प्राप्त किया जा सकता है। पहले संख्या 2 और 4 का आदान-प्रदान करें। फिर 3 और 5 का आदान-प्रदान करें और अंत में 1 और 3 का आदान-प्रदान करें। यह दर्शाता है कि दिया गया क्रमचय σ विषम है। क्रमपरिवर्तन # साइकिल नोटेशन लेख की विधि का अनुसरण करते हुए इसे बाएँ से दाएँ लिखते हुए लिखा जा सकता है। जैसा कि

उदाहरण के लिए ट्रांसपोज़िशन की कार्यात्मक संरचना के रूप में σ लिखने के कई अन्य तरीके हैं।

σ = (1 5)(3 4)(2 4)(1 2)(2 3),

लेकिन इसे सम संख्या के रूपांतरणों के उत्पाद के रूप में लिखना असंभव है।

गुण

पहचान क्रमचय एक समान क्रमचय है।[1] एक समान क्रमचय को एक सम और विषम संख्याओं की संरचना के रूप में प्राप्त किया जा सकता है और केवल दो तत्वों के आदान-प्रदान (जिन्हें ट्रांसपोजिशन (गणित) कहा जाता है) की समान संख्या है। जबकि एक विषम क्रमपरिवर्तन (केवल) विषम संख्या में ट्रांसपोज़िशन द्वारा प्राप्त किया जा सकता है।

निम्नलिखित नियम पूर्णांकों के योग के बारे में संबंधित नियमों से सीधे अनुसरण करते हैं।[1] दो सम क्रमचयों का संघटन सम होता है।

  • दो विषम क्रमचयों का संघटन सम होता है।
  • विषम और सम क्रमचय का संयोजन विषम होता है।

इनसे यह अनुसरण करता है।

  • प्रत्येक सम क्रमचय का व्युत्क्रम सम होता है।
  • प्रत्येक विषम क्रमचय का व्युत्क्रम विषम होता है।

सममित समूह एस को ध्यान में रखते हुएn सेट {1, ..., n} के सभी क्रमपरिवर्तनों में हम यह निष्कर्ष निकाल सकते हैं कि मानचित्र

sgn: Sn → {−1, 1} 

जो प्रत्येक क्रमचय को निर्दिष्ट करता है उसका हस्ताक्षर एक समूह समरूपता है।[2]

इसके अतिरिक्त हम देखते हैं कि सम क्रमपरिवर्तन Sn का एक उपसमूह बनाते हैं।[1] यह n अक्षरों पर वैकल्पिक समूह है। जिसे An द्वारा दर्शाया गया है।[3] यह होमोमोर्फिज्म एसजीएन का कर्नेल (बीजगणित) है। विषम क्रमचय एक उपसमूह नहीं बना सकते हैं। क्योंकि दो विषम क्रमपरिवर्तन का योग सम है। लेकिन वे An (Sn में) का सहसमुच्चय बनाते हैं[4]

अगर n > 1 तो Sn में उतने ही सम क्रमपरिवर्तन हैं। जैसा कि विषम हैं।[3] परिणामस्वरूप, An में n!/2 क्रमचय होते हैं। (कारण यह है कि यदि σ सम है। (1  2)σ विषम है और यदि σ विषम है। तो (1  2)σ सम है और ये दोनों मानचित्र एक दूसरे के व्युत्क्रम हैं।)[3]

एक चक्रीय क्रमचय सम है। यदि केवल इसकी लंबाई विषम है। यह जैसे सूत्रों से होता है।

व्यवहार में यह निर्धारित करने के लिए कि क्या दिया गया क्रमचय सम या विषम है। कोई क्रमचय को असंयुक्त चक्रों के उत्पाद के रूप में लिखता है। क्रमचय विषम है और केवल गुणनखंड में सम-लंबाई वाले चक्रों की संख्या विषम है।

एक दिया गया क्रमचय सम या विषम है। यह निर्धारित करने के लिए एक अन्य विधि संबंधित क्रमचय मैट्रिक्स का निर्माण करना और उसके निर्धारक की गणना करना है। निर्धारक का मान क्रमचय की समानता के समान है।

विषम क्रम (समूह सिद्धांत) का प्रत्येक क्रमचय सम होना चाहिए। क्रमपरिवर्तन (1 2)(3 4) में A4 दर्शाता है। कि इसका विलोम सामान्य रूप से सत्य नहीं है।

दो परिभाषाओं की समानता

यह खंड प्रमाण प्रस्तुत करता है कि क्रमचय σ की समानता को दो समान तरीकों से परिभाषित किया जा सकता है:

  • σ (किसी भी क्रम में) में व्युत्क्रमों की संख्या की समानता के रूप में।
  • ट्रांसपोज़िशन की संख्या की समानता के रूप में जिसे σ को विघटित किया जा सकता है (हालाँकि हम इसे विघटित करना चुनते हैं)।
प्रमाण 1

मान लें कि σ रैंक किए गए डोमेन S पर एक क्रमचय है। प्रत्येक क्रमचय ट्रांसपोजिशन (2-एलिमेंट एक्सचेंज) के अनुक्रम द्वारा निर्मित किया जा सकता है। निम्नलिखित को एक ऐसा अपघटन होने दें

σ = T1 T2 ... Tk

हम दिखाना चाहते हैं कि k की समता σ के व्युत्क्रमों की संख्या की समता के बराबर है।

प्रत्येक ट्रांसपोजिशन को आसन्न तत्वों के विषम संख्या के ट्रांसपोजिशन के उत्पाद के रूप में लिखा जा सकता है, उदा।:(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

आम तौर पर, हम सेट {1,...,i,...,i+d पर ट्रांसपोजिशन (i i+d) लिख सकते हैं ,...} d पर पुनरावर्तन द्वारा 2d−1 सन्निकट ट्रांसपोजिशन की संरचना के रूप में:

  • आधार मामला d=1 तुच्छ है।
  • पुनरावर्ती मामले में, पहले (i, i+d) को (i, i+1) (i+1, i) के रूप में फिर से लिखें +d) (i, i+1)। फिर पुनरावर्ती रूप से पुनर्लेखन (i+1, i+d) आसन्न प्रतिस्थापन के रूप में।

यदि हम इस तरह से प्रत्येक प्रतिस्थापन को विघटित करते हैंT1 ... Tk ऊपर, हमें नया अपघटन मिलता है:

σ = A1 A2 ... Am

जहां सभी A1...Am अगल-बगल हैं। साथ ही, की समानता m के समान k है।

यह एक तथ्य है: सभी क्रमचय τ और आसन्न स्थानान्तरण a, के लिए या तो τ की तुलना में एक कम या एक अधिक उलटा है। दूसरे शब्दों में, एक क्रमचय के व्युत्क्रमों की संख्या की समानता तब बदली जाती है जब एक निकटस्थ स्थानान्तरण के साथ रचना की जाती है।

इसलिए, σ के व्युत्क्रमों की संख्या की समानता m की समानता है, जो k की समानता भी है। यही हम साबित करने निकले हैं।

इस प्रकार हम σ की समता को परिभाषित कर सकते हैं जो किसी भी अपघटन में इसके घटक परिवर्तनों की संख्या है। और जैसा कि ऊपर देखा गया है, यह किसी भी आदेश के तहत व्युत्क्रमों की संख्या की समानता से सहमत होना चाहिए। इसलिए, परिभाषाएँ वास्तव में अच्छी तरह से परिभाषित और समकक्ष हैं।
प्रमाण 2

एक वैकल्पिक प्रमाण वैंडरमोंड बहुपद का उपयोग करता है

तो उदाहरण के लिए n = 3, हमारे पास है

अब संख्याओं {1, ..., n} के दिए गए क्रमचय σ के लिए, हम परिभाषित करते हैं

बहुपद के बाद से के समान कारक हैं उनके संकेतों को छोड़कर, यह इस प्रकार है कि sgn(σ) या तो +1 या माइनस 1 है। इसके अलावा, अगर σ और τ दो क्रमचय हैं, तो हम देखते हैं

चूंकि इस परिभाषा के साथ यह और भी स्पष्ट है कि दो तत्वों के किसी भी स्थानान्तरण में हस्ताक्षर −1 होता है, हम वास्तव में हस्ताक्षर को पुनः प्राप्त करते हैं जैसा कि पहले परिभाषित किया गया था।
प्रमाण 3

तीसरा दृष्टिकोण समूह के प्रस्तुति का उपयोग करता है Sn जनरेटर के मामले में τ1, ..., τn−1 और संबंध

  •   सभी के लिए i
  •   सभी के लिए i < n − 1
  •   if
[यहाँ जनरेटर (i, i + 1)}} का प्रतिनिधित्व करता है।] सभी संबंध एक शब्द की लंबाई को समान रखते हैं या इसे दो से बदलते हैं। एक सम-लंबाई वाले शब्द से शुरू करने से संबंधों का उपयोग करने के बाद हमेशा एक समान-लंबाई वाले शब्द का परिणाम होगा, और इसी तरह विषम-लंबाई वाले शब्दों के लिए भी। इसलिए इसके तत्वों को कॉल करना असंदिग्ध है Sn सम-लंबाई वाले शब्दों "सम" द्वारा प्रतिनिधित्व किया जाता है, और तत्वों को विषम-लंबाई वाले शब्दों "विषम" द्वारा दर्शाया जाता है।
प्रमाण 4

याद रखें कि एक जोड़ी x, y जैसे कि x <y और σ(x ) > σ(y) को उलटा कहा जाता है। हम यह दिखाना चाहते हैं कि व्युत्क्रमों की गिनती में 2-तत्व स्वैप की गिनती के समान समानता है। ऐसा करने के लिए, हम दिखा सकते हैं कि प्रत्येक अदला-बदली व्युत्क्रमों की गिनती की समानता को बदल देती है, इससे कोई फर्क नहीं पड़ता कि कौन से दो तत्वों की अदला-बदली की जा रही है और कौन सा क्रमचय पहले ही लागू किया जा चुका है। मान लीजिए कि हम iवें और jवें तत्व की अदला-बदली करना चाहते हैं। स्पष्ट रूप से, [i, j] के बाहर किसी तत्व के साथ i या j द्वारा गठित व्युत्क्रम प्रभावित नहीं होंगे। n = jमैं &ऋण; 1 अंतराल के भीतर तत्व (i, j), मान लें कि vi उनमें से i के साथ व्युत्क्रम बनाते हैं औरvj उनमें से 'जे' के साथ व्युत्क्रम बनाते हैं। यदि i और j की अदला-बदली की जाती है, तो वो vi उनमें से 'जे' के साथ व्युत्क्रम बनाते हैं। यदि i और j की अदला-बदली की जाती है, तो वो vi}} inversions are formed. The count of inversions i gained is thus n − 2vi, जिसकी समानता n के समान है।

इसी प्रकार, प्राप्त व्युत्क्रम j की गणना में भी n के समान समानता है। इसलिए, दोनों संयुक्त द्वारा प्राप्त व्युत्क्रमों की संख्या में 2n या 0. के समान समानता है। 'वें तत्व, हम देख सकते हैं कि यह अदला-बदली व्युत्क्रमों की गिनती की समानता को बदल देती है, क्योंकि हम जोड़ी (i,j) के लिए प्राप्त व्युत्क्रमों की संख्या में 1 जोड़ते हैं (या घटाते हैं) .

ध्यान दें कि शुरू में जब कोई स्वैप लागू नहीं होता है, तो व्युत्क्रमों की संख्या 0 होती है। अब हम क्रमचय की समता की दो परिभाषाओं की समानता प्राप्त करते हैं।
Proof 5

Consider the elements that are sandwiched by the two elements of a transposition. Each one lies completely above, completely below, or in between the two transposition elements.

An element that is either completely above or completely below contributes nothing to the inversion count when the transposition is applied. Elements in-between contribute .

As the transposition itself supplies inversion, and all others supply 0 (mod 2) inversions, a transposition changes the parity of the number of inversions.

अन्य परिभाषाएं और प्रमाण

के क्रमचय की समता इसके चक्रीय क्रमपरिवर्तन में अंक भी एन्कोड किए गए हैं।

माना σ = (i1 i2 ... मैंr+1)(जे1 j2 ... जेs+1)...(ℓ12 ... ℓu+1) अद्वितीय चक्र संकेतन हो | σ का असंयुक्त चक्रों में अपघटन, जिसे किसी भी क्रम में बनाया जा सकता है क्योंकि वे यात्रा करते हैं। एक चक्र (a b c ... x y z) शामिल है k + 1 अंक हमेशा के ट्रांसपोजिशन (2-चक्र) बनाकर प्राप्त किए जा सकते हैं:

इसलिए k को चक्र का आकार कहते हैं, और निरीक्षण करते हैं कि, इस परिभाषा के तहत, ट्रांसपोज़िशन आकार 1 के चक्र हैं। अपघटन से m विसंक्रमित चक्रों में हम σ का अपघटन प्राप्त कर सकते हैं k1 + k2 + ... + km स्थानान्तरण, जहाँ ki iवें चक्र का आकार है। जो नंबर N(σ) = k1 + k2 + ... + km को σ का विवेचक कहा जाता है, और इसकी गणना भी की जा सकती है

अगर हम σ के निश्चित बिंदुओं को 1-चक्र के रूप में शामिल करने का ख्याल रखते हैं।

मान लीजिए कि एक क्रमचय σ के बाद एक स्थानान्तरण (a b) लागू किया जाता है। जब a और b σ के विभिन्न चक्रों में होते हैं तब

,

और अगर ए और बी σ के एक ही चक्र में हैं तो

.

किसी भी मामले में, यह देखा जा सकता है N((a b)σ) = N(σ) ± 1, इसलिए N((a b)σ) की समता N(σ) की समता से भिन्न होगी।

अगर σ = t1t2 ... tr एक क्रमचय σ का मनमाना अपघटन है, r ट्रांसपोज़िशन को लागू करके टी के बाद2 के बाद ... टी के बादr सर्वसमिका (जिसका N शून्य है) के बाद निरीक्षण करें कि N(σ) और r में समानता है। σ की समता को N(σ) की समता के रूप में परिभाषित करके, एक क्रमचय जिसमें एक समान लंबाई का अपघटन होता है, एक सम क्रमचय होता है और एक क्रमचय जिसमें एक विषम लंबाई का अपघटन होता है, एक विषम क्रमचय होता है।

टिप्पणियां
  • उपर्युक्त तर्क की सावधानीपूर्वक जांच से पता चलता है rN(σ), और चक्रों में σ के किसी भी अपघटन के बाद से जिनके आकार r के बराबर होते हैं, उन्हें r पारदर्शिता की संरचना के रूप में व्यक्त किया जा सकता है, संख्या N(σ) σ के अपघटन में चक्रों के आकार का न्यूनतम संभव योग है, जिसमें शामिल है ऐसे मामले जिनमें सभी चक्र स्थानान्तरण हैं।
  • यह प्रमाण उन बिंदुओं के सेट में (संभवतः मनमाना) आदेश नहीं देता है जिन पर σ कार्य करता है।

सामान्यीकरण

समता को कॉक्सेटर समूहों के लिए सामान्यीकृत किया जा सकता है: एक लंबाई फ़ंक्शन ℓ(v) को परिभाषित करता है, जो जनरेटर की पसंद पर निर्भर करता है (सममित समूह के लिए, आसन्न पारदर्शिता), और फिर फ़ंक्शन v ↦ (−1)ℓ(v) एक सामान्यीकृत साइन मैप देता है।

यह भी देखें

टिप्पणियाँ

  1. 1.0 1.1 1.2 1.3 Jacobson (2009), p. 50.
  2. Rotman (1995), p. 9, Theorem 1.6.
  3. 3.0 3.1 3.2 जैकबसन (2009), पी। 51.
  4. Meijer & Bauer (2004), p. 72


संदर्भ

  • Weisstein, Eric W. "Even Permutation". MathWorld.
  • Jacobson, Nathan (2009). Basic algebra. Vol. 1 (2nd ed.). Dover. ISBN 978-0-486-47189-1.
  • Rotman, J.J. (1995). An introduction to the theory of groups. Graduate texts in mathematics. Springer-Verlag. ISBN 978-0-387-94285-8.
  • Goodman, Frederick M. Algebra: Abstract and Concrete. ISBN 978-0-9799142-0-1.
  • Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Group theory: the application to quantum mechanics. Dover classics of science and mathematics. Dover Publications. ISBN 978-0-486-43798-9.