क्रमचय की समानता

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

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

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

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

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

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

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

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

sgn(σ) = (−1)^m

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

उदाहरण

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

$\sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}={\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.$

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

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

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

गुण

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

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

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

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

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

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

sgn: S_n → {−1, 1} 

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

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

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

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

$(a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ or }}(a\ b)(b\ c)(c\ d)(d\ e).$

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

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

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

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

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

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

Expand

प्रमाण 1

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

σ = T₁ T₂ ... T_k

हम दिखाना चाहते हैं कि 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) आसन्न प्रतिस्थापन के रूप में।

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

σ = A₁ A₂ ... A_m

जहां सभी A₁...A_m दाये-बाये हैं। साथ ही, की समानता m के समान k है।

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

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

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

Expand

प्रमाण 2

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

$P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j}).$

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

$P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}).$

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

$\operatorname {sgn}(\sigma )={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}.$

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

${\begin{aligned}\operatorname {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}\\[4pt]&={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}\\[4pt]&=\operatorname {sgn}(\sigma )\cdot \operatorname {sgn}(\tau ).\end{aligned}}$

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

Expand

प्रमाण 3

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

• $\tau _{i}^{2}=1$  सभी के लिए i
• $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$   सभी के लिए i < n − 1
• $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$   if $|i-j|\geq 2.$

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

Expand

प्रमाण 4

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

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

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

Expand

प्रमाण 5

उन तत्वों पर विचार करें जो एक स्थानान्तरण के दो तत्वों द्वारा सैंडविच होते हैं। हर एक पूरी तरह से ऊपर, पूरी तरह से नीचे, या दो वाष्पोत्सर्जन तत्वों के बीच में स्थित है।

एक तत्व जो या तो पूरी तरह से ऊपर या पूरी तरह से नीचे है, ट्रांसपोजिशन लागू होने पर व्युत्क्रम गणना में कुछ भी योगदान नहीं देता है। बीच के तत्व योगदान करते हैं $2$.

जैसा कि ट्रांसपोजिशन ही आपूर्ति करता है $\pm 1$ व्युत्क्रम, और अन्य सभी 0 (mod 2) व्युत्क्रम प्रदान करते हैं, एक स्थानान्तरण व्युत्क्रमों की संख्या की समानता को बदल देता है।

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

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

माना σ = (i₁ i₂ ... मैं_r+1)(जे₁ j₂ ... जे_s+1)...(ℓ₁ ℓ₂ ... ℓ_u+1) अद्वितीय चक्र संकेतन हो | σ का असंयुक्त चक्रों में अपघटन, जिसे किसी भी क्रम में बनाया जा सकता है क्योंकि वे यात्रा करते हैं। एक चक्र (a b c ... x y z) शामिल है k + 1 अंक सदैव के ट्रांसपोजिशन (2-चक्र) बनाकर प्राप्त किए जा सकते हैं:

$(a\ b\ c\dots x\ y\ z)=(a\ b)(b\ c)\dots (x\ y)(y\ z),$

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

$n{\text{ minus the number of disjoint cycles in the decomposition of }}\sigma$

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

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

$(a\ b)(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})$,

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

$(a\ b)(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})$.

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

अगर σ = t₁t₂ ... t_r एक क्रमचय σ का मनमाना अपघटन है, r ट्रांसपोज़िशन को प्रयुक्त करके $t_{1}$ टी के बाद₂ के बाद ... टी के बाद_r सर्वसमिका (जिसका N शून्य है) के बाद निरीक्षण करें कि N(σ) और r में समानता है। σ की समता को N(σ) की समता के रूप में परिभाषित करके, एक क्रमचय जिसमें एक समान लंबाई का अपघटन होता है, एक सम क्रमचय होता है और एक क्रमचय जिसमें एक विषम लंबाई का अपघटन होता है, एक विषम क्रमचय होता है।

टिप्पणियां

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

सामान्यीकरण

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

यह भी देखें

• पंद्रह पहेली एक क्लासिक अनुप्रयोग है
• ज़ोलोटारेव की लेम्मा

संदर्भ

• 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.