क्रमचय: Difference between revisions

{{redirect|nPr||NPR (disambiguation)}}

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

{{anchor|n-factorial}}के क्रमपरिवर्तन की संख्या {{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''}} संबंधित द्वारा प्रतिस्थापित किया जाता है {{math|''f''(''s'')}}. उदाहरण के लिए, ऊपर वर्णित क्रमपरिवर्तन (3, 1, 2) को फ़ंक्शन द्वारा वर्णित किया गया है <math>\alpha</math> के रूप में परिभाषित किया गया है

समुच्चय के सभी क्रमपरिवर्तनों के संग्रह से एक [[ समूह (गणित) ]] बनता है जिसे समुच्चय का [[ सममित समूह ]] कहा जाता है। ग्रुप ऑपरेशन [[ समारोह संरचना ]] (उत्तराधिकार में दो दिए गए पुनर्व्यवस्थाओं को निष्पादित करना) है, जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण समुच्चय तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अक्सर समुच्चय का क्रमपरिवर्तन होता है <math>\{1, 2, \ldots, n\}</math> जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है।

प्राथमिक कॉम्बिनेटरिक्स में, {{math|''k''}}-क्रमपरिवर्तन, या [[ आंशिक क्रमपरिवर्तन ]], की क्रमबद्ध व्यवस्थाएं हैं {{math|''k''}} एक सेट से चुने गए विशिष्ट तत्व। कब {{math|''k''}} सेट के आकार के बराबर है, ये सेट के क्रमपरिवर्तन हैं।

[[ हेक्साग्राम ([[ मैं चिंग ]]) ]] नामक क्रमपरिवर्तन चीन में आई चिंग ([[ पिनयिन ]]: यी जिंग) में 1000 ईसा पूर्व के रूप में इस्तेमाल किया गया था।

[[ अल-खलील इब्न अहमद अल-फ़राहिदी ]]|अल-खलील (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 के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा [[ लीलावती ]] में एक मार्ग शामिल है जो अनुवाद करता है:

अंकगणित श्रृंखला के गुणन का गुणनफल एकता से शुरू होता है और स्थानों की संख्या तक जारी रहता है, विशिष्ट अंकों के साथ संख्या की भिन्नता होगी।<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>

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}} इस बिंदु पर वह हार मान लेता है और टिप्पणी करता है:

अब इन विधियों की प्रकृति ऐसी है, कि एक संख्या पर परिवर्तन सभी छोटी संख्याओं पर परिवर्तन को समझ लेता है, ... इतना अधिक कि एक संख्या पर परिवर्तनों का एक पूर्ण समूह सभी छोटी संख्याओं पर पूर्ण अंक को एकजुट करके बनने लगता है। एक पूरे शरीर में;{{sfn|Stedman|1677|p=8}}

स्टैडमैन क्रमपरिवर्तन के विचार को विस्तृत करता है; वह 20 के एक स्थिर से वर्णमाला के अक्षरों और घोड़ों के क्रमपरिवर्तन की संख्या पर विचार करता है।{{sfn|Stedman|1677|pp=13—18}}

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

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

क्रमपरिवर्तन का सबसे सरल उदाहरण दोहराव के बिना क्रमपरिवर्तन है जहां हम व्यवस्था के संभावित तरीकों की संख्या पर विचार करते हैं {{mvar|n}} में आइटम {{mvar|n}} स्थान। एक सेट में क्रमपरिवर्तन की संख्या को परिभाषित करने के लिए फैक्टोरियल का विशेष अनुप्रयोग होता है जिसमें पुनरावृत्ति शामिल नहीं होती है। संख्या n!, n फैक्टोरियल पढ़ें, वास्तव में उन तरीकों की संख्या है जिनसे हम n चीजों को एक नए क्रम में पुनर्व्यवस्थित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास तीन फल हैं: एक संतरा, सेब और नाशपाती, तो हम उन्हें बताए गए क्रम में खा सकते हैं, या हम उन्हें बदल सकते हैं (उदाहरण के लिए, एक सेब, एक नाशपाती फिर एक संतरा)। तब क्रमपरिवर्तन की सही संख्या है <math>3! = 1 \cdot 2 \cdot 3 = 6</math>. जैसे-जैसे मदों की संख्या (n) बढ़ती है, संख्या बहुत बड़ी होती जाती है।

इसी तरह, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या n|k-क्रमपरिवर्तन का #k-क्रमपरिवर्तन कहा जाता है। इसे के रूप में लिखा जा सकता है <math>nPk</math> (जो n क्रमपरिवर्तन k पढ़ता है), और संख्या के बराबर है <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>

एक सेट से खुद के लिए एक आक्षेप के रूप में, एक क्रमचय एक ऐसा कार्य है जो एक सेट की पुनर्व्यवस्था करता है, और यह एक व्यवस्था नहीं है। एक पुराना और अधिक प्राथमिक दृष्टिकोण यह है कि क्रमपरिवर्तन स्वयं व्यवस्थाएँ हैं। इन दोनों के बीच अंतर करने के लिए, सक्रिय और निष्क्रिय पहचानकर्ताओं को कभी-कभी शब्द क्रमपरिवर्तन के लिए उपसर्ग किया जाता है, जबकि पुरानी शब्दावली में प्रतिस्थापन और क्रमपरिवर्तन का उपयोग किया जाता है।{{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}} नीचे)। सामान्य तौर पर, k लंबाई का एक चक्र, जो k तत्वों से बना होता है, k-चक्र कहलाता है।

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

{{anchor|Two-line notation}} चूँकि क्रमपरिवर्तनों को मौलिक रूप से लिखना, अर्थात्, टुकड़े-टुकड़े के कार्यों के रूप में, बोझिल है, उन्हें अधिक कॉम्पैक्ट रूप से प्रस्तुत करने के लिए कई संकेतन का आविष्कार किया गया है। साइकिल अंकन कई गणितज्ञों के लिए इसकी कॉम्पैक्टनेस और इस तथ्य के कारण एक लोकप्रिय विकल्प है कि यह क्रमपरिवर्तन की संरचना को पारदर्शी बनाता है। यह इस आलेख में उपयोग किया गया संकेतन है जब तक कि अन्यथा निर्दिष्ट न हो, लेकिन अन्य संकेतन अभी भी व्यापक रूप से उपयोग किए जाते हैं, खासकर आवेदन क्षेत्रों में।

[[ ऑगस्टिन-लुई कॉची ]] के दो-पंक्ति संकेतन में,<ref>{{citation|title=The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory|first=Hans|last=Wussing|publisher=Courier Dover Publications|year=2007|isbn=9780486458687|page=94|url=https://books.google.com/books?id=Xp3JymnfAq4C&pg=PA94|quote=Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.}}</ref> one पहली पंक्ति में S के तत्वों को सूचीबद्ध करता है, और दूसरी पंक्ति में प्रत्येक के नीचे उसकी छवि सूचीबद्ध करता है। उदाहरण के लिए, समुच्चय S = {1, 2, 3, 4, 5} का एक विशेष क्रमचय इस प्रकार लिखा जा सकता है

इसका मतलब है कि संतुष्ट {{math|''σ''(1) {{=}} 2}}, {{math|''σ''(2) {{=}} 5}}, {{math|''σ''(3) {{=}} 4}}, {{math|''σ''(4) {{=}} 3}}, तथा {{math|''σ''(5) {{=}} 1}}. एस के तत्व पहली पंक्ति में किसी भी क्रम में प्रकट हो सकते हैं। इस क्रमपरिवर्तन को इस प्रकार भी लिखा जा सकता है:

यदि 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>, तो कोई इसे दो-पंक्ति संकेतन की पहली पंक्ति के लिए उपयोग करत