क्रमचय: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| (5 intermediate revisions by 4 users not shown) | |||
| Line 3: | Line 3: | ||
[[File:Permutations RGB.svg|thumb|120 px|छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है]]गणित में, एक सेट का [[क्रम]]चय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के [[रैखिक क्रम]] को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।<ref>{{harvtxt|Webster|1969}}</ref> | [[File:Permutations RGB.svg|thumb|120 px|छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है]]गणित में, एक सेट का [[क्रम]]चय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के [[रैखिक क्रम]] को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।<ref>{{harvtxt|Webster|1969}}</ref> | ||
क्रमपरिवर्तन [[संयोजनों]] से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {1, 2, 3}, अर्थात् (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), और (3, 2, 1)। ये तीन-तत्वों के इस सेट के सभी संभावित क्रम हैं। जिन शब्दों के वर्ण भिन्न हैं उनके एनाग्राम भी क्रमचय हैं: अक्षरों को पहले से ही मूल शब्द में क्रमबद्ध किया गया है, और [[विपर्यय]] अक्षरों का पुनर्क्रमण है। [[ साहचर्य ]] और [[ समूह सिद्धांत ]] के क्षेत्र में [[ परिमित सेट | परिमित सेट]] के क्रमपरिवर्तन का अध्ययन एक महत्वपूर्ण विषय है। | क्रमपरिवर्तन [[संयोजनों]] से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {1, 2, 3}, अर्थात् (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), और (3, 2, 1)। ये तीन-तत्वों के इस सेट के सभी संभावित क्रम हैं। जिन शब्दों के वर्ण भिन्न हैं उनके एनाग्राम भी क्रमचय हैं: अक्षरों को पहले से ही मूल शब्द में क्रमबद्ध किया गया है, और [[विपर्यय]] अक्षरों का पुनर्क्रमण है। [[ साहचर्य |साहचर्य]] और [[ समूह सिद्धांत |समूह सिद्धांत]] के क्षेत्र में [[ परिमित सेट |परिमित सेट]] के क्रमपरिवर्तन का अध्ययन एक महत्वपूर्ण विषय है। | ||
क्रमपरिवर्तन का उपयोग गणित की लगभग हर शाखा में और विज्ञान के कई अन्य क्षेत्रों में किया जाता है। [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, उनका उपयोग [[सॉर्टिंग एल्गोरिदम]] के विश्लेषण के लिए किया जाता है; [[क्वांटम भौतिकी]] में, कणों की अवस्थाओं का वर्णन करने के लिए; और जीव विज्ञान में, आरएनए अनुक्रमों का वर्णन करने के लिए। | क्रमपरिवर्तन का उपयोग गणित की लगभग हर शाखा में और विज्ञान के कई अन्य क्षेत्रों में किया जाता है। [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, उनका उपयोग [[सॉर्टिंग एल्गोरिदम]] के विश्लेषण के लिए किया जाता है; [[क्वांटम भौतिकी]] में, कणों की अवस्थाओं का वर्णन करने के लिए; और जीव विज्ञान में, आरएनए अनुक्रमों का वर्णन करने के लिए। | ||
{{math|''n''}} विशिष्ट वस्तुओं के क्रमपरिवर्तन की संख्या {{math|''n''}} भाज्य है, जिसे | {{math|''n''}} विशिष्ट वस्तुओं के क्रमपरिवर्तन की संख्या {{math|''n''}} भाज्य है, जिसे सामान्यतः {{math|''n''!}} के रूप में लिखा जाता है। जिसका अर्थ है {{math|''n''}} से कम या उसके बराबर सभी धनात्मक पूर्णांकों का गुणनफल है। | ||
तकनीकी रूप से, समुच्चय {{math|''S''}} के क्रमचय को {{math|''S''}} से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है।<ref>{{harvtxt|McCoy|1968|p=152}}</ref><ref>{{harvtxt|Nering|1970|p=86}}</ref> अर्थात्, यह {{math|''S''}} से {{math|''S''}} तक का एक कार्य है जिसके लिए प्रत्येक तत्व के [[प्रतिबिंब]] के मान के लिए ठीक एक बार होता है। | तकनीकी रूप से, समुच्चय {{math|''S''}} के क्रमचय को {{math|''S''}} से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है।<ref>{{harvtxt|McCoy|1968|p=152}}</ref><ref>{{harvtxt|Nering|1970|p=86}}</ref> अर्थात्, यह {{math|''S''}} से {{math|''S''}} तक का एक कार्य है जिसके लिए प्रत्येक तत्व के [[प्रतिबिंब]] के मान के लिए ठीक एक बार होता है। यह {{math|''S''}} के तत्वों की पुनर्व्यवस्था से संबंधित है जिसमें प्रत्येक तत्व {{math|''S''}} को संगत {{math|''f''(''s'')}} द्वारा प्रतिस्थापित किया जाता है। उदाहरण के लिए, ऊपर बताए गए क्रमचय (3, 1, 2) को फ़ंक्शन <math>\alpha</math> के रूप में परिभाषित किया गया है | ||
: <math>\alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2</math>. | : <math>\alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2</math>. | ||
सेट के सभी क्रमपरिवर्तनों का संग्रह एक [[ समूह (गणित) |समूह (गणित)]] बनाता है जिसे सेट के [[ सममित समूह |सममित समूह]] कहा जाता है। समूह संचालन [[संरचना]] है ( | सेट के सभी क्रमपरिवर्तनों का संग्रह एक [[ समूह (गणित) |समूह (गणित)]] बनाता है जिसे सेट के [[ सममित समूह |सममित समूह]] कहा जाता है। समूह संचालन [[संरचना]] है (उत्तरदायी में दो दी गई व्यवस्थाओं का प्रदर्शन), जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण सेट तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अधिकांशतः सेट के क्रमपरिवर्तन होते हैं <math>\{1, 2, \ldots, n\}</math> जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है। | ||
प्राथमिक | प्राथमिक साहचर्य में, {{math|''k''}}-क्रमपरिवर्तन, या [[ आंशिक क्रमपरिवर्तन |आंशिक क्रमपरिवर्तन]], एक सेट से चुने गए {{math|''k''}} विशिष्ट तत्वों की क्रमबद्ध व्यवस्था है। जब k समुच्चय के आकार के बराबर होता है, तो ये समुच्चय के क्रमचय होते हैं। | ||
[[Image:Rubik's cube.svg|thumb|1974 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।]] | [[Image:Rubik's cube.svg|thumb|1974 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।]] | ||
== इतिहास == | == इतिहास == | ||
चीन में | चीन में [[चिंग]]([[ पिनयिन |पिनयिन]]: यी जिंग) में 1000 ईसा पूर्व के रूप में हेक्साग्राम नामक क्रमपरिवर्तन का उपयोग किया गया था। | ||
अरब गणितज्ञ [[ अल-खलील इब्न अहमद अल-फ़राहिदी | अल-खलील इब्न अहमद अल-फ़राहिदी]] अल-खलील (717-786) और क्रिप्टोग्राफर ने क्रिप्टोग्राफ़िक संदेशों की पुस्तक लिखी। इसमें स्वरों के साथ और बिना सभी संभावित [[अरबी शब्दों]] को सूचीबद्ध करने के लिए क्रमचय और संयोजन का पहला उपयोग | अरब गणितज्ञ [[ अल-खलील इब्न अहमद अल-फ़राहिदी |अल-खलील इब्न अहमद अल-फ़राहिदी]] अल-खलील (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 के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा [[ लीलावती |लीलावती]] में एक मार्ग | 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}} | ||
पहला मामला जिसमें प्रतीत होता है कि असंबद्ध गणितीय प्रश्नों का क्रमपरिवर्तन की मदद से अध्ययन किया गया था, 1770 के आसपास हुआ था, जब [[ जोसेफ लुइस लाग्रेंज |जोसेफ लुइस लाग्रेंज]] ने बहुपद समीकरणों के अध्ययन में देखा किसी समीकरण के मूलों के क्रमचय के गुण इसे हल करने की संभावनाओं से संबंधित होते हैं। काम की इस पंक्ति का परिणाम अंततः एवरिस्ट गैलोइस के काम के माध्यम से हुआ, [[ गैलोइस सिद्धांत |गैलोइस सिद्धांत]] में, जो मूलांकों द्वारा बहुपद समीकरणों (एक अज्ञात में) को हल करने के संबंध में क्या संभव है और क्या असंभव है, इसका पूरा विवरण देता है। आधुनिक गणित में, ऐसी कई समान स्थितियाँ हैं जिनमें किसी समस्या को समझने के लिए उससे संबंधित कुछ क्रमपरिवर्तनों का अध्ययन करने की आवश्यकता होती है। | पहला मामला जिसमें प्रतीत होता है कि असंबद्ध गणितीय प्रश्नों का क्रमपरिवर्तन की मदद से अध्ययन किया गया था, 1770 के आसपास हुआ था, जब [[ जोसेफ लुइस लाग्रेंज |जोसेफ लुइस लाग्रेंज]] ने बहुपद समीकरणों के अध्ययन में देखा किसी समीकरण के मूलों के क्रमचय के गुण इसे हल करने की संभावनाओं से संबंधित होते हैं। काम की इस पंक्ति का परिणाम अंततः एवरिस्ट गैलोइस के काम के माध्यम से हुआ, [[ गैलोइस सिद्धांत |गैलोइस सिद्धांत]] में, जो मूलांकों द्वारा बहुपद समीकरणों (एक अज्ञात में) को हल करने के संबंध में क्या संभव है और क्या असंभव है, इसका पूरा विवरण देता है। आधुनिक गणित में, ऐसी कई समान स्थितियाँ हैं जिनमें किसी समस्या को समझने के लिए उससे संबंधित कुछ क्रमपरिवर्तनों का अध्ययन करने की आवश्यकता होती है। | ||
== दोहराव के बिना क्रमपरिवर्तन == | == दोहराव के बिना क्रमपरिवर्तन == | ||
क्रमचय का सबसे सरल उदाहरण पुनरावृत्ति के बिना क्रमचय है जहाँ हम {{mvar|n}} वस्तुओं को {{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 | इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे <math>nPk</math> (जो "n क्रमचय 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> | ||
क्रमचय को समुच्चय S से स्वयं पर आक्षेप के रूप में परिभाषित किया जा सकता है। n तत्वों के साथ एक सेट के सभी क्रमपरिवर्तन एक सममित समूह बनाते हैं, जिसे {{math|''S''}} के रूप में दर्शाया जाता है, जहां समूह [[संचालन कार्य रचना]] है। इस प्रकार दो क्रमपरिवर्तन के लिए, <math>\pi</math> और <math>\sigma</math> | क्रमचय को समुच्चय S से स्वयं पर आक्षेप के रूप में परिभाषित किया जा सकता है। n तत्वों के साथ एक सेट के सभी क्रमपरिवर्तन एक सममित समूह बनाते हैं, जिसे {{math|''S''}} के रूप में दर्शाया जाता है, जहां समूह [[संचालन कार्य रचना]] है। इस प्रकार दो क्रमपरिवर्तन के लिए, <math>\pi</math> और <math>\sigma</math> तथा समूह में <math>S_n</math> चार स्वयंसिद्ध समूह हैं: | ||
# [[ क्लोजर (गणित) | क्लोजर (गणित)]] : यदि <math>\pi</math> तथा <math>\sigma</math> में हैं <math>S_n</math> तो ऐसा है <math>\pi\sigma.</math> सहबद्धता: किन्हीं तीन क्रमपरिवर्तनों के लिए <math>\pi, \sigma, \tau \in S_n</math>, <math>(\pi\sigma)\tau = \pi(\sigma\tau).</math> | # [[ क्लोजर (गणित) | क्लोजर (गणित)]] : यदि <math>\pi</math> तथा <math>\sigma</math> में हैं <math>S_n</math> तो ऐसा है <math>\pi\sigma.</math> सहबद्धता: किन्हीं तीन क्रमपरिवर्तनों के लिए <math>\pi, \sigma, \tau \in S_n</math>, <math>(\pi\sigma)\tau = \pi(\sigma\tau).</math> | ||
# [[ पहचान तत्व | पहचान तत्व]] : एक पहचान क्रमचय है, निरूपित <math>\operatorname{id}</math> और द्वारा परिभाषित <math>\operatorname{id}(x) = x</math> सभी के लिए <math>x \in S</math>. किसी के लिए <math>\sigma \in S_n</math>, <math>\operatorname{id} \sigma = \sigma \operatorname{id} = \sigma.</math> | # [[ पहचान तत्व | पहचान तत्व]] : एक पहचान क्रमचय है, निरूपित <math>\operatorname{id}</math> और द्वारा परिभाषित <math>\operatorname{id}(x) = x</math> सभी के लिए <math>x \in S</math>. किसी के लिए <math>\sigma \in S_n</math>, <math>\operatorname{id} \sigma = \sigma \operatorname{id} = \sigma.</math> | ||
# [[ उलटा तत्व | | # [[ उलटा तत्व | व्युत्क्रमा तत्व]] : प्रत्येक क्रमचय के लिए <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> | |||
एक सेट से अपने आप में एक आक्षेप के रूप में, एक क्रमचय एक ऐसा कार्य है जो एक सेट की पुनर्व्यवस्था करता है, और स्वयं कोई व्यवस्था नहीं है। एक पुराना और अधिक प्राथमिक दृष्टिकोण यह है कि क्रमचय स्वयं व्यवस्थाएँ हैं। इन दोनों के बीच अंतर करने के लिए, सक्रिय और निष्क्रिय पहचानकर्ताओं को कभी-कभी क्रमचय शब्द से पहले जोड़ा जाता है, जबकि पुरानी शब्दावली में प्रतिस्थापन और क्रमपरिवर्तन का उपयोग किया जाता है।{{sfn|Cameron|1994|loc=p. 29, footnote 3}} | एक सेट से अपने आप में एक आक्षेप के रूप में, एक क्रमचय एक ऐसा कार्य है जो एक सेट की पुनर्व्यवस्था करता है, और स्वयं कोई व्यवस्था नहीं है। एक पुराना और अधिक प्राथमिक दृष्टिकोण यह है कि क्रमचय स्वयं व्यवस्थाएँ हैं। इन दोनों के बीच अंतर करने के लिए, सक्रिय और निष्क्रिय पहचानकर्ताओं को कभी-कभी क्रमचय शब्द से पहले जोड़ा जाता है, जबकि पुरानी शब्दावली में प्रतिस्थापन और क्रमपरिवर्तन का उपयोग किया जाता है।{{sfn|Cameron|1994|loc=p. 29, footnote 3}} | ||
एक क्रमचय को एक या एक से अधिक असंयुक्त चक्रों में विघटित किया जा सकता है, अर्थात्, [[ कक्षा (समूह सिद्धांत) |कक्षा (समूह सिद्धांत)]], जो कुछ तत्वों पर क्रमचय के अनुप्रयोग को बार-बार अनुरेखित करने पर मिलते हैं। उदाहरण के लिए, क्रमपरिवर्तन <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}} नीचे)। | एक क्रमचय को एक या एक से अधिक असंयुक्त चक्रों में विघटित किया जा सकता है, अर्थात्, [[ कक्षा (समूह सिद्धांत) |कक्षा (समूह सिद्धांत)]], जो कुछ तत्वों पर क्रमचय के अनुप्रयोग को बार-बार अनुरेखित करने पर मिलते हैं। उदाहरण के लिए, क्रमपरिवर्तन <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-चक्र कहलाता है। | ||
1-चक्र <math>(\,x\,)</math> में एक तत्व को क्रमचय का [[ निश्चित बिंदु (गणित) | निश्चित बिंदु (गणित)]] कहा जाता है। एक क्रमचय जिसमें कोई निश्चित बिंदु नहीं है, को विक्षिप्तता कहा जाता है। 2-चक्रों को स्थानान्तरण कहा जाता है; इस तरह के क्रमचय केवल दो तत्वों का आदान-प्रदान करते हैं, अन्य को स्थिर छोड़ देते हैं। | 1-चक्र <math>(\,x\,)</math> में एक तत्व को क्रमचय का [[ निश्चित बिंदु (गणित) |निश्चित बिंदु (गणित)]] कहा जाता है। एक क्रमचय जिसमें कोई निश्चित बिंदु नहीं है, को विक्षिप्तता कहा जाता है। 2-चक्रों को स्थानान्तरण कहा जाता है; इस तरह के क्रमचय केवल दो तत्वों का आदान-प्रदान करते हैं, अन्य को स्थिर छोड़ देते हैं। | ||
== अंकन == | == अंकन == | ||
चूँकि क्रमचय को तत्ववार लिखना, अर्थात्, टुकड़े के कार्यों के रूप में, बोझिल है, उन्हें अधिक | चूँकि क्रमचय को तत्ववार लिखना, अर्थात्, टुकड़े के कार्यों के रूप में, बोझिल है, उन्हें अधिक जटिल रूप से प्रस्तुत करने के लिए कई संकेतन का आविष्कार किया गया है। साइकिल अंकन कई गणितज्ञों के लिए इसकी जटिलनेस और इस तथ्य के कारण एक लोकप्रिय विकल्प है कि यह एक क्रमचय की संरचना को पारदर्शी बनाता है। जब तक अन्यथा निर्दिष्ट नहीं किया जाता है, तब तक यह इस लेख में प्रयुक्त संकेतन है, लेकिन अन्य संकेतन अभी भी व्यापक रूप से उपयोग किए जाते हैं, विशेष रूप से अनुप्रयोग क्षेत्रों में। | ||
=== दो-पंक्ति संकेतन === | === दो-पंक्ति संकेतन === | ||
| Line 71: | Line 71: | ||
\end{pmatrix}.</math> | \end{pmatrix}.</math> | ||
=== एक-पंक्ति संकेतन === | === एक-पंक्ति संकेतन === | ||
यदि 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>, तो कोई इसे दो-पंक्ति | यदि 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>, तो कोई इसे दो-पंक्ति संकेतन की पहली पंक्ति के लिए उपयोग करता है: | ||
: <math>\sigma = \begin{pmatrix} | : <math>\sigma = \begin{pmatrix} | ||
x_1 & x_2 & x_3 & \cdots & x_n \\ | x_1 & x_2 & x_3 & \cdots & x_n \\ | ||
| Line 78: | Line 78: | ||
इस धारणा के तहत, कोई पहली पंक्ति को छोड़ सकता है और क्रमचय को एक-पंक्ति संकेतन में लिख सकता है | इस धारणा के तहत, कोई पहली पंक्ति को छोड़ सकता है और क्रमचय को एक-पंक्ति संकेतन में लिख सकता है | ||
: <math>(\sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n)) </math>, | : <math>(\sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(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}} माना जाएगा। (इन प्रविष्टियों को केवल तभी अलग करने के लिए अल्पविराम का उपयोग करना विशिष्ट है, जब कुछ में दो या दो से अधिक अंक हों।) यह फॉर्म अधिक | अर्थात्, एस के तत्वों की एक व्यवस्थित व्यवस्था के रूप में।<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 के तत्वों या क्रमचय की तुलना बड़े या छोटे के रूप में की जानी है। | ||
=== साइकिल अंकन === | === साइकिल अंकन === | ||
| Line 86: | Line 86: | ||
# एक ओपनिंग ब्रैकेट लिखें, फिर <math>S</math> का एक मनमाना तत्व x चुनें और इसे लिखें: <math>(\,x</math> | # एक ओपनिंग ब्रैकेट लिखें, फिर <math>S</math> का एक मनमाना तत्व x चुनें और इसे लिखें: <math>(\,x</math> | ||
# फिर x की कक्षा का पता लगाएं; | # फिर x की कक्षा का पता लगाएं; अर्थात, <math>\sigma</math> : <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots</math> के क्रमिक अनुप्रयोगों के तहत इसके मूल्यों को लिखें। | ||
#तब तक दोहराएं जब तक कि मान x पर वापस न आ जाए और x के | #तब तक दोहराएं जब तक कि मान x पर वापस न आ जाए और x के अतिरिक्त समापन कोष्ठक लिखें: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)</math> | ||
# अब S के एक तत्व y के साथ जारी रखें, जिसे अभी तक लिखा नहीं गया है, और उसी तरह आगे बढ़ें: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)(\,y\,\ldots\,)</math> | # अब S के एक तत्व y के साथ जारी रखें, जिसे अभी तक लिखा नहीं गया है, और उसी तरह आगे बढ़ें: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)(\,y\,\ldots\,)</math> | ||
# S के सभी तत्वों को चक्रों में लिखे जाने तक दोहराएं। | # S के सभी तत्वों को चक्रों में लिखे जाने तक दोहराएं। | ||
| Line 93: | Line 93: | ||
तो क्रमचय {{nowrap|2 5 4 3 1}} (एक-पंक्ति संकेतन में) चक्र अंकन में {{nowrap|(125)(34)}} के रूप में लिखा जा सकता है। | तो क्रमचय {{nowrap|2 5 4 3 1}} (एक-पंक्ति संकेतन में) चक्र अंकन में {{nowrap|(125)(34)}} के रूप में लिखा जा सकता है। | ||
जबकि सामान्य रूप से क्रमपरिवर्तन नहीं करते हैं, अलग-अलग चक्र करते हैं; उदाहरण के लिए,<math display="block">(\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,3 \, 4\,) (\,1 \, 2 \, 5\,).</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>एक दिए गए क्रमपरिवर्तन के अलग-अलग चक्रों को कई अलग-अलग विधियों से लिखने के लिए कोई भी इन समानताओं को जोड़ सकता है। | ||
चक्र संकेतन की एक सुविधाजनक विशेषता यह है कि व्युत्क्रम क्रमचय का चक्र अंकन क्रमचय के चक्रों में तत्वों के क्रम को | 1-चक्रों को अधिकांशतः चक्र संकेतन से हटा दिया जाता है, बशर्ते संदर्भ स्पष्ट हो; एस में किसी भी तत्व एक्स के लिए किसी भी चक्र में दिखाई नहीं दे रहा है, कोई भी <math>\sigma(x) = x</math><ref>{{harvnb|Hall|1959|p=54}}</ref> मानता है। पहचान क्रमचय, जिसमें केवल 1-चक्र होते हैं, को एकल 1-चक्र (x), संख्या 1,{{efn|1 is frequently used to represent the [[identity element]] in a non-commutative group}} या आईडी द्वारा दर्शाया जा सकता है।<ref>{{harvnb|Rotman|2002|p=41}}</ref><ref>{{harvnb|Bogart|1990|p=487}}</ref> | ||
चक्र संकेतन की एक सुविधाजनक विशेषता यह है कि व्युत्क्रम क्रमचय का चक्र अंकन क्रमचय के चक्रों में तत्वों के क्रम को व्युत्क्रम कर दिया जाता है। उदाहरण के लिए,<math display="block">[(\,1\,2\,5\,)(\,3\,4\,)]^{-1} = (\,5\,2\,1\,)(\,4\,3\,).</math> | |||
=== विहित चक्र संकेतन === | === विहित चक्र संकेतन === | ||
| Line 107: | Line 108: | ||
उदाहरण के लिए, (312)(54)(8)(976) विहित चक्र संकेतन में एक क्रमचय है।<ref>{{harvnb|Bona|2012|loc=p.87}} [Note that the book has a typo/error here, as it gives (45) instead of (54).]</ref> विहित चक्र संकेतन एक-चक्र को नहीं छोड़ता है। | उदाहरण के लिए, (312)(54)(8)(976) विहित चक्र संकेतन में एक क्रमचय है।<ref>{{harvnb|Bona|2012|loc=p.87}} [Note that the book has a typo/error here, as it gives (45) instead of (54).]</ref> विहित चक्र संकेतन एक-चक्र को नहीं छोड़ता है। | ||
रिचर्ड पी. स्टेनली प्रतिनिधित्व के समान विकल्प को क्रमचय का "मानक प्रतिनिधित्व" कहते हैं,<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="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> | ||
=== क्रमपरिवर्तन की संरचना === | === क्रमपरिवर्तन की संरचना === | ||
| Line 121: | Line 122: | ||
</ref> | </ref> | ||
क्योंकि फ़ंक्शन एप्लिकेशन जिस तरह से लिखा गया है। चूँकि फ़ंक्शन रचना साहचर्य है, इसलिए क्रमपरिवर्तन पर रचना संचालन है: <math>(\sigma\pi)\tau = \sigma(\pi\tau)</math> इसलिए, दो से अधिक क्रमचयों के गुणनफल | क्योंकि फ़ंक्शन एप्लिकेशन जिस तरह से लिखा गया है। चूँकि फ़ंक्शन रचना साहचर्य है, इसलिए क्रमपरिवर्तन पर रचना संचालन है: <math>(\sigma\pi)\tau = \sigma(\pi\tau)</math> इसलिए, दो से अधिक क्रमचयों के गुणनफल सामान्यतः व्यक्त समूहन में कोष्ठक जोड़े बिना लिखे जाते हैं; वे सामान्यतः रचना को इंगित करने के लिए बि | ||