क्रमचय: Difference between revisions

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

तकनीकी रूप से, समुच्चय {{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> के रूप में परिभाषित किया गया है

अरब गणितज्ञ [[ अल-खलील इब्न अहमद अल-फ़राहिदी | अल-खलील इब्न अहमद अल-फ़राहिदी]] अल-खलील (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}}

गणित के ग्रंथों में यह लोअरकेस ग्रीक अक्षरों का उपयोग करके क्रमचय को निरूपित करने के लिए प्रथागत है। सामान्यतः, या तो <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> तथा समूह में <math>S_n</math> चार स्वयंसिद्ध समूह हैं:

1-चक्र <math>(\,x\,)</math> में एक तत्व को क्रमचय का [[ निश्चित बिंदु (गणित) | निश्चित बिंदु (गणित)]] कहा जाता है। एक क्रमचय जिसमें कोई निश्चित बिंदु नहीं है, को विक्षिप्तता कहा जाता है। 2-चक्रों को स्थानान्तरण कहा जाता है; इस तरह के क्रमचय केवल दो तत्वों का आदान-प्रदान करते हैं, अन्य को स्थिर छोड़ देते हैं।

शब्द क्रमचय का एक कमजोर अर्थ, कभी-कभी प्राथमिक साहचर्य ग्रंथों में उपयोग किया जाता है, उन क्रमबद्ध व्यवस्थाओं को निर्दिष्ट करता है जिसमें कोई तत्व एक से अधिक बार नहीं होता है, लेकिन किसी दिए गए सेट से सभी तत्वों का उपयोग करने की आवश्यकता के बिना। विशेष मामलों को छोड़कर ये क्रमपरिवर्तन नहीं हैं, बल्कि आदेशित व्यवस्था अवधारणा के प्राकृतिक सामान्यीकरण हैं। वास्तव में, इस प्रयोग में अधिकांशतः आकार 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>^nP_k</math>, <math>P_{n,k}</math>, या <math>P(n,k)</math> और इसका मूल्य उत्पाद द्वारा दिया जाता है<ref>{{cite book|author=Charalambides, Ch A.|title=गणनात्मक कॉम्बिनेटरिक्स|publisher=CRC Press|year=2002|isbn=978-1-58488-290-9|page=42|url=https://books.google.com/books?id=PDMGA-v5G54C&pg=PA42}}</ref>

गुणनफल अच्छी तरह परिभाषित है, बिना इस धारणा के कि <math>n</math> एक गैर-ऋणात्मक पूर्णांक है, और साहचर्य के बाहर भी इसका महत्व है; इसे पॉचहैमर प्रतीक<math>(n)_k</math> या <math>k</math>-वीं गिरती फैक्टोरियल पावर <math>n^{\underline k}</math> के <math>n</math>रूप में जाना जाता है।

क्रमपरिवर्तन शब्द का यह प्रयोग शब्द संयोजन से निकटता से संबंधित है। n-सेट S का k-तत्व संयोजन, S का k-तत्व उपसमुच्चय है, जिनमें से तत्वों का आदेश नहीं दिया गया है। S के सभी k तत्व उपसमुच्चयों को लेकर और उनमें से प्रत्येक को हर संभव तरीके से व्यवस्थित करके, हम एस के सभी के-क्रमपरिवर्तन प्राप्त करते हैं। एक n-सेट, C(n,k) के k-संयोजनों की संख्या इसलिए है n के k-क्रमपरिवर्तन की संख्या से संबंधित:

इन संख्याओं को [[ द्विपद गुणांक ]] के रूप में भी जाना जाता है और इन्हें <math>\binom{n}{k}</math> द्वारा निरूपित किया जाता है .

समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, चूंकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स की संख्या <math>n^k.</math> कोई तत्व 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}}}} इन्हें औपचारिक रूप से वस्तुओं के सामान्य क्रमपरिवर्तन के [[ तुल्यता वर्ग |तुल्यता वर्ग]] के रूप में परिभाषित किया जा सकता है, रेखीय व्यवस्था के अंतिम तत्व को उसके सामने ले जाने से उत्पन्न [[ तुल्यता संबंध | तुल्यता संबंध]] के लिए।  

    1 4 2 3

  4 3 2 1 3 4 1 2

    2 3 1 4

    1 1

  4 3 3 4

    2 2</पूर्व>

सामान्यतः, चक्र संकेतन में लिखे गए रचना क्रमपरिवर्तन आसानी से वर्णित पैटर्न का अनुसरण नहीं करते हैं - रचना के चक्र रचना किए जाने वाले चक्रों से भिन्न हो सकते हैं। हालाँकि संयुग्मन वर्ग के क्रमपरिवर्तन के विशेष मामले में चक्र प्रकार संरक्षित है <math>\sigma</math> दूसरे क्रमपरिवर्तन द्वारा <math>\pi</math>, जिसका अर्थ है उत्पाद बनाना <math>\pi\sigma\pi^{-1}</math>. यहां, <math>\pi\sigma\pi^{-1}</math> का संयुग्म है <math>\sigma</math> द्वारा <math>\pi</math> और इसके चक्र अंकन के लिए चक्र अंकन लेकर प्राप्त किया जा सकता है <math>\sigma</math> और आवेदन <math>\pi</math> इसमें सभी प्रविष्टियों के लिए।{{sfn|Humphreys|1996|p=84}} यह इस प्रकार है कि दो क्रमपरिवर्तन ठीक उसी समय संयुग्मित होते हैं जब उनके पास एक ही चक्र प्रकार होता है।

एक क्रमचय मैट्रिक्स एक वर्ग मैट्रिक्स | 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>.

चलो <math>f(p)=q</math> कोष्ठक-मिटाने वाला परिवर्तन हो जो <math>q</math> को एक-पंक्ति नोटेशन में लौटाता है <math>p</math> विहित में चक्र अंकन। जैसा कि कहा गया है, <math>f</math> सभी कोष्ठकों को हटाकर संचालित होता है। व्युत्क्रम परिवर्तन का संचालन, {<math>f^{-1}(q)=p</math>, जो एक-पंक्ति संकेतन में <math>q</math> दिए जाने पर विहित चक्र संकेतन में <math>p</math> लौटाता है, यह थोड़ा कम सहज है। <math>q = q_1q_2\cdots q_n</math> का पहला चक्र p}p विहित चक्र संकेतन में <math>q_1</math> से शुरू होना चाहिए। जब तक बाद के तत्व <math>q_1</math> से छोटे हैं, हम <math>p</math> के समान चक्र में हैं। <math>p</math> का दूसरा चक्र सबसे छोटे इंडेक्स <math>j</math> से शुरू होता है, जैसे कि <math>q_j > q_1</math>। दूसरे शब्दों में, <math>q_j</math> अपने बायीं ओर की सभी चीज़ों से बड़ा है, इसलिए इसे बाएँ से दाएँ अधिकतम कहा जाता है। कैनोनिकल चक्र संकेतन में प्रत्येक चक्र बाएं से दाएं अधिकतम के साथ शुरू होता है।{{sfn|Bona|2012|pp=109–110}}

[[Image:15-Puzzle.jpg|thumb|[[ 15 पहेली ]] में वर्गों को आरोही क्रम में लाने का लक्ष्य है। प्रारंभिक स्थितियाँ जिनमें विषम संख्या में व्युत्क्रम हैं, को हल करना असंभव है।<ref name="Slocum">{{cite web

}}</ref>]]क्रमपरिवर्तन σ का व्युत्क्रम पदों की एक जोड़ी (i, j) है जहां क्रमचय की प्रविष्टियां विपरीत क्रम में होती हैं: <math>\sigma_i > \sigma_j</math>{{sfn|Bóna|2004|p=43}} तो <math>i < j</math> दो आसन्न स्थितियों पर एक व्युत्क्रम है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 में तीन व्युत्क्रम हैं: (1, 3), (2, 3), और (4, 5), प्रविष्टियों के जोड़े के लिए (2, 1), (3, 1), और ( 5, 4)।