क्रमचय: Difference between revisions

From Vigyanwiki
No edit summary
Line 227: Line 227:
M_{(2, 1, 3)} M_{(2, 3, 1)} = \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} = \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} = M_{(1, 3, 2)}.</math>
M_{(2, 1, 3)} M_{(2, 3, 1)} = \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix}\begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} = \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} = M_{(1, 3, 2)}.</math>


[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|क्रमचय आव्यूहों के गुणन के संगत क्रमचयों की संरचना।]]'''साहित्य में व्युत्क्रम परिपाटी का पता लगाना भी आम''' है, जहां एक क्रमचय σ मैट्रिक्स से जुड़ा होता है <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> जिसकी (i, j) प्रविष्टि 1 है यदि j = σ(i) और अन्यथा 0 है। इस परिपाटी में, क्रमचय आव्यूह क्रमचय से विपरीत क्रम में गुणा करते हैं, अर्थात्, <math>P_\sigma P_{\pi} = P_{\pi \circ \sigma}</math> सभी क्रमपरिवर्तन σ और π के लिए। इस पत्राचार में, क्रमचय मेट्रिसेस मानक के सूचकांकों की अनुमति देकर कार्य करते हैं <math>1 \times n</math> पंक्ति वैक्टर <math>({\bf e}_i)^T</math>: किसी के पास <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>.
[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|क्रमचय आव्यूहों के गुणन के संगत क्रमचयों की संरचना।]]साहित्य में उलटा सम्मेलन खोजना भी आम है, जहां एक क्रमचय σ मैट्रिक्स <math>P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}</math> जिसकी (i, j) प्रविष्टि 1 है यदि j = σ(i) और अन्यथा 0 है। इस परिपाटी में, क्रमचय आव्यूह, क्रमचय से विपरीत क्रम में गुणा करते हैं, अर्थात, <math>P_\sigma P_{\pi} = P_{\pi \circ \sigma}</math> सभी क्रमपरिवर्तन σ और π के लिए। इस पत्राचार में, क्रमचय आव्यूह मानक <math>1 \times n</math> पंक्ति सदिशों <math>({\bf e}_i)^T</math> एक में <math>({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T</math>


दाईं ओर [[ केली टेबल ]] 3 तत्वों के क्रमपरिवर्तन के लिए इन आव्यूहों को दिखाता है।
दाईं ओर [[ केली टेबल |केली टेबल]] 3 तत्वों के क्रमपरिवर्तन के लिए इन आव्यूहों को दिखाता है।


== पूरी तरह से ऑर्डर किए गए सेट के क्रमपरिवर्तन ==
== पूरी तरह से ऑर्डर किए गए सेट के क्रमपरिवर्तन ==
कुछ अनुप्रयोगों में, अनुमत सेट के तत्वों की एक दूसरे के साथ तुलना की जाएगी। इसके लिए आवश्यक है कि समुच्चय S का कुल क्रम हो जिससे किन्हीं भी दो तत्वों की तुलना की जा सके। सेट {1, 2, ..., n} पूरी तरह से सामान्य ≤ संबंध द्वारा क्रमबद्ध है और इसलिए यह इन अनुप्रयोगों में सबसे अधिक उपयोग किया जाने वाला सेट है, लेकिन सामान्य तौर पर, कोई भी पूरी तरह से ऑर्डर किया गया सेट करेगा। इन अनुप्रयोगों में, क्रमचय में पदों के बारे में बात करने के लिए क्रमपरिवर्तन के आदेशित व्यवस्था दृश्य की आवश्यकता होती है।
कुछ अनुप्रयोगों में, अनुमत सेट के तत्वों की एक दूसरे के साथ तुलना की जाएगी। इसके लिए आवश्यक है कि समुच्चय S का कुल क्रम हो जिससे किन्हीं भी दो तत्वों की तुलना की जा सके। सेट {1, 2, ..., n} सामान्य "≤" संबंध द्वारा पूरी तरह से आदेशित है और इसलिए यह इन अनुप्रयोगों में सबसे अधिक बार उपयोग किया जाने वाला सेट है, लेकिन सामान्य तौर पर, कोई भी पूरी तरह से ऑर्डर किया गया सेट करेगा। इन अनुप्रयोगों में, क्रमचय में पदों के बारे में बात करने के लिए क्रमपरिवर्तन के आदेशित व्यवस्था दृश्य की आवश्यकता होती है।


ऐसे कई गुण हैं जो सीधे S के कुल क्रम से संबंधित हैं।
ऐसे कई गुण हैं जो सीधे S के कुल क्रम से संबंधित हैं।


=== आरोहण, अवरोहण, दौड़ और अधिकता ===
=== आरोहण, अवरोहण, दौड़ और अधिकता ===
{{anchor|Descents}}
n के क्रमचय σ का आरोहण कोई भी स्थिति i < n है जहां निम्न मान वर्तमान मान से बड़ा है। अर्थात, यदि σ = σ1σ2...σn, तो i एक आरोहण है यदि σi < σi+1। उदाहरण के लिए, क्रमपरिवर्तन 3452167 में आरोही (स्थितियों पर) 1, 2, 5 और 6 हैं। इसी तरह, एक डिसेंट i < n के साथ σi > σi+1 की स्थिति है, इसलिए <math>1 \leq i<n</math> के साथ हर i या तो एक आरोही है या एक डिसेंट है σ। क्रमचय का एक आरोही क्रम क्रमचय का एक गैर-खाली बढ़ता हुआ सन्निकट क्रम है जिसे किसी भी छोर पर विस्तारित नहीं किया जा सकता है; यह लगातार चढ़ाई के अधिकतम अनुक्रम से मेल खाता है (उत्तरार्द्ध खाली हो सकता है: दो लगातार अवरोही के बीच अभी भी लंबाई 1 का आरोही रन है)। इसके विपरीत एक क्रमचय का एक बढ़ता क्रम आवश्यक रूप से सन्निहित नहीं है: यह कुछ स्थितियों पर मानों को छोड़ कर क्रमचय से प्राप्त तत्वों का बढ़ता क्रम है। उदाहरण के लिए, क्रमचय 2453167 में आरोही रन 245, 3, और 167 हैं, जबकि इसके बढ़ते क्रमांक 2367 हैं। यदि एक क्रमचय में k - 1 अवरोही है, तो यह k आरोही रन का संघ होना चाहिए।{{sfn|Bóna|2004|p=4f}}
n के क्रमचय σ का आरोहण किसी भी स्थिति i < n है जहां निम्न मान वर्तमान मान से बड़ा है। अर्थात्, यदि  = σ<sub>1</sub>σ<sub>2</sub>...पी<sub>''n''</sub>, तो मैं एक चढ़ाई है अगर σ<sub>''i''</sub>< पृ<sub>''i''+1</sub>.


उदाहरण के लिए, क्रमपरिवर्तन 3452167 में आरोही (स्थितियों पर) 1, 2, 5 और 6 हैं।
k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> सही\rangle; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। हालांकि कुछ लेखक ऑयलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो {{nowrap|''k'' − 1}} अवरोही के अनुरूप है।{{sfn|Bona|2012|pages=4–5}} क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि {{nowrap|''σ''<sub>''j''</sub> > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''<sub>''j''</sub> ≥ ''j''}}), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}


इसी तरह, एक अवरोही σ के साथ एक स्थिति i < n है<sub>''i''</sub>> पी<sub>''i''+1</sub>, तो हर मैं के साथ <math>1 \leq i<n</math> या तो चढ़ाई है या σ का अवतरण है।
=== फोटा का संक्रमण लेम्मा ===
 
एक-पंक्ति संकेतन और विहित चक्र संकेतन के बीच एक संबंध है। विहित चक्र अंकन में क्रमचय <math>(\,2\,)(\,3\,1\,)</math> पर विचार करें; यदि हम केवल कोष्ठकों को हटा दें, तो हम एक-पंक्ति संकेतन में क्रमचय <math>231</math> प्राप्त करते हैं। [[ डोमिनिक फोटा |डोमिनिक फोटा]] की संक्रमण लेम्मा इस पत्राचार की प्रकृति को n-क्रमपरिवर्तन (स्वयं के लिए) के सेट पर एक आक्षेप के रूप में स्थापित करती है।{{sfn|Bona|2012|pp=109–110}} रिचर्ड पी. स्टेनली इस पत्राचार को मौलिक आपत्ति कहते हैं।<ref name="Stanley2012" />
क्रमचय का आरोही क्रम क्रमचय का एक गैर-रिक्त बढ़ता हुआ सन्निहित क्रम है जिसे किसी भी छोर पर नहीं बढ़ाया जा सकता है; यह क्रमिक आरोहण के अधिकतम अनुक्रम से मेल खाता है (बाद वाला खाली हो सकता है: दो क्रमिक अवरोही के बीच अभी भी लंबाई का एक आरोही भाग है)। इसके विपरीत क्रमपरिवर्तन का बढ़ता क्रम अनिवार्य रूप से सन्निहित नहीं है: यह कुछ पदों पर मानों को छोड़ कर क्रमपरिवर्तन से प्राप्त तत्वों का बढ़ता क्रम है।
उदाहरण के लिए, क्रमचय 2453167 में आरोही रन 245, 3, और 167 हैं, जबकि इसके बाद 2367 बढ़ते हुए क्रम हैं।
 
यदि क्रमचय में k − 1 अवरोही है, तो यह k आरोही रनों का संघ होना चाहिए।{{sfn|Bóna|2004|p=4f}}
k आरोहण वाले n के क्रमचयों की संख्या (परिभाषा के अनुसार) ऑयलेरियन संख्या है <math>\textstyle\left\langle{n\atop k}\right\rangle</math>; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। हालांकि कुछ लेखक यूलेरियन संख्या को परिभाषित करते हैं <math>\textstyle\left\langle{n\atop k}\right\rangle</math> k आरोही रन के साथ क्रमपरिवर्तन की संख्या के रूप में, जो से मेल खाती है {{nowrap|''k'' − 1}} अवरोह।{{sfn|Bona|2012|pages=4–5}}
एक क्रमचय की अधिकता<sub>1</sub>σ<sub>2</sub>...पी<sub>''n''</sub> एक सूचकांक जे ऐसा है कि {{nowrap|''σ''<sub>''j''</sub> > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''<sub>''j''</sub> ≥ ''j''}}), तो j को कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तनों की संख्या k अवरोही वाले n-क्रमपरिवर्तनों की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}


चलो <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}}


=== फोटा का संक्रमण लेम्मा ===
उदाहरण के लिए, क्रमचय में <math>q=312548976</math>, 5 पहला तत्व है जो प्रारंभिक तत्व 3 से बड़ा है, इसलिए <math>p</math> का पहला चक्र <math>(\,3\,1\,2\,)</math> होना चाहिए। फिर 8 अगला तत्व 5 से बड़ा है, तो दूसरा चक्र है <math>(\,5\,4\,)</math>। चूँकि 9, 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है {\displaystyle (\,9\,7\,6\,)}{\displaystyle (\,9\,7\,6\,)}। इन 4 चक्रों को जोड़ने पर <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र अंकन में।
एक-पंक्ति संकेतन और विहित चक्र संकेतन के बीच एक संबंध है। क्रमपरिवर्तन पर विचार करें <math>(\,2\,)(\,3\,1\,)</math> विहित चक्र अंकन में; यदि हम केवल कोष्ठकों को हटा दें, तो हमें क्रमचय प्राप्त होता है <math>231</math> एक-पंक्ति संकेतन में। [[ डोमिनिक फोटा ]] की संक्रमण लेम्मा इस पत्राचार की प्रकृति को एन-क्रमपरिवर्तन (स्वयं के लिए) के सेट पर एक आक्षेप के रूप में स्थापित करती है।{{sfn|Bona|2012|pp=109–110}} रिचर्ड पी। स्टेनली इस पत्राचार को मौलिक आपत्ति कहते हैं।<ref name="Stanley2012"/>
होने देना <math>f(p)=q</math> कोष्ठक-मिटाने वाला परिवर्तन जो वापस आता है <math>q</math> दिए जाने पर एक-पंक्ति संकेतन में <math>p</math> विहित चक्र संकेतन में। जैसा कि कहा गया, <math>f</math> सभी कोष्ठकों को हटाकर संचालित होता है। उलटा परिवर्तन का संचालन, <math>f^{-1}(q)=p</math>, जो लौटता है <math>p</math> दिए जाने पर विहित चक्र संकेतन में <math>q</math> एक-पंक्ति संकेतन में, थोड़ा कम सहज ज्ञान युक्त है। एक-पंक्ति संकेतन को देखते हुए <math>q = q_1q_2\cdots q_n</math>, का पहला चक्र <math>p</math> विहित चक्र में संकेतन के साथ शुरू होना चाहिए <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}}
उदाहरण के लिए, क्रमपरिवर्तन में <math>q=312548976</math>, 5 प्रारंभिक तत्व 3 से बड़ा पहला तत्व है, इसलिए का पहला चक्र <math>p</math> होना चाहिए <math>(\,3\,1\,2\,)</math>. फिर 8 अगला तत्व 5 से बड़ा है, इसलिए दूसरा चक्र है <math>(\,5\,4\,)</math>. चूंकि 9 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 इसके दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है <math>(\,9\,7\,6\,)</math>. इन 4 चक्रों को जोड़कर देता है <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र संकेतन में।


निम्न तालिका दोनों को दिखाती है <math>q</math> तथा <math>p</math> के छह क्रमपरिवर्तन के लिए <math>123</math>. प्रत्येक समानता का बोल्ड पक्ष अपने निर्दिष्ट संकेतन (के लिए एक-पंक्ति संकेतन) का उपयोग करके क्रमपरिवर्तन को दर्शाता है <math>q</math> और विहित चक्र संकेतन के लिए <math>p</math>) जबकि गैर-बोल्ड पक्ष दूसरे अंकन में समान क्रमपरिवर्तन दिखाता है। तालिका के प्रत्येक कॉलम के बोल्ड साइड की तुलना से पता चलता है कि फोटा के बायजेक्शन के ऑपरेशन को हटाने/पुनर्स्थापित करने वाला कोष्ठक दिखाता है, जबकि प्रत्येक कॉलम के एक ही पक्ष की तुलना (उदाहरण के लिए, एक समीकरण के पक्ष) से ​​पता चलता है कि कौन से क्रमपरिवर्तन स्वयं को बायजेक्शन द्वारा मैप किए गए हैं ( पहली 3 पंक्तियाँ) और जो नहीं हैं (अंतिम 3 पंक्तियाँ)।
निम्न तालिका <math>q</math> और <math>p</math> दोनों को <math>123</math> के छह क्रमपरिवर्तनों के लिए दिखाती है। प्रत्येक समानता का बोल्ड पक्ष अपने नामित संकेतन <math>q</math> के लिए एक-पंक्ति संकेतन और <math>p</math> के लिए विहित चक्र संकेतन) का उपयोग करके क्रमपरिवर्तन दिखाता है, जबकि गैर-बोल्ड पक्ष दूसरे में समान क्रमचय दिखाता है अंकन। तालिका के प्रत्येक स्तंभ के बोल्ड पक्ष की तुलना करने से फोटा के आक्षेप के संचालन को हटाने/पुनर्स्थापना करने वाले कोष्ठक को दर्शाता है, प्रत्येक स्तंभ के एक ही पक्ष की तुलना करते समय (उदाहरण के लिए, बायाँ पक्ष) दिखाता है कौन से क्रमपरिवर्तन खुद को बायजेक्शन (पहली 3 पंक्तियों) द्वारा मैप किए जाते हैं और कौन से नहीं हैं (अंतिम 3 पंक्तियाँ)।


{| class="wikitable"
{| class="wikitable"
Line 275: Line 266:
| <math>\mathbf{321}=(\,2\,)(\,3\,1\,)</math>  || <math>312=\mathbf{(\,3\,2\,1\,)}</math>  
| <math>\mathbf{321}=(\,2\,)(\,3\,1\,)</math>  || <math>312=\mathbf{(\,3\,2\,1\,)}</math>  
|}
|}
प्रथम उपप्रमेय के रूप में, बिल्कुल k बाएँ से दाएँ मैक्सिमा के साथ n-क्रमपरिवर्तनों की संख्या भी पहली तरह की सांकेतिक स्टर्लिंग संख्या के बराबर है, <math>c(n, k)</math>. इसके अलावा, Foata की मैपिंग k-कमजोर बहिर्वाह के साथ n-क्रमपरिवर्तन के साथ n-क्रमपरिवर्तन लेता है {{nowrap|''k'' − 1}} आरोही।{{sfn|Bona|2012|pp=109–110}} उदाहरण के लिए, (2)(31) = 321 में दो कमजोर एक्सीडेंस हैं (इंडेक्स 1 और 2 पर), जबकि {{nowrap|''f''(321) {{=}} 231}} एक चढ़ाई है (इंडेक्स 1 पर; यानी 2 से 3 तक)।
'''प्रथम उपप्रमेय के रूप में,''' बिल्कुल k बाएँ से दाएँ मैक्सिमा के साथ n-क्रमपरिवर्तनों की संख्या भी पहली तरह की सांकेतिक स्टर्लिंग संख्या के बराबर है, <math>c(n, k)</math>. इसके अलावा, Foata की मैपिंग k-कमजोर बहिर्वाह के साथ n-क्रमपरिवर्तन के साथ n-क्रमपरिवर्तन लेता है {{nowrap|''k'' − 1}} आरोही।{{sfn|Bona|2012|pp=109–110}} उदाहरण के लिए, (2)(31) = 321 में दो कमजोर एक्सीडेंस हैं (इंडेक्स 1 और 2 पर), जबकि {{nowrap|''f''(321) {{=}} 231}} एक चढ़ाई है (इंडेक्स 1 पर; यानी 2 से 3 तक)।


=== व्युत्क्रम ===
=== व्युत्क्रम ===

Revision as of 16:00, 21 November 2022

For other uses, see क्रमचय (disambiguation).
"एनपीआर" redirects here. For other uses, see एनपीआर (बहुविकल्पी).
छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है

गणित में, एक सेट का क्रमचय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के रैखिक क्रम को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।[1]

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

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

n विशिष्ट वस्तुओं के क्रमपरिवर्तन की संख्या n भाज्य है, जिसे आमतौर पर n! के रूप में लिखा जाता है। जिसका अर्थ है n से कम या उसके बराबर सभी धनात्मक पूर्णांकों का गुणनफल।

तकनीकी रूप से, समुच्चय S के क्रमचय को S से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है।[2][3] अर्थात्, यह S से S तक का एक कार्य है जिसके लिए प्रत्येक तत्व के प्रतिबिंब के मान के लिए ठीक एक बार होता है। यह S के तत्वों की पुनर्व्यवस्था से संबंधित है जिसमें प्रत्येक तत्व S को संगत f(s) द्वारा प्रतिस्थापित किया जाता है। उदाहरण के लिए, ऊपर बताए गए क्रमचय (3, 1, 2) को फ़ंक्शन के रूप में परिभाषित किया गया है

.

सेट के सभी क्रमपरिवर्तनों का संग्रह एक समूह (गणित) बनाता है जिसे सेट के सममित समूह कहा जाता है। समूह संचालन संरचना है (उत्तराधिकार में दो दी गई व्यवस्थाओं का प्रदर्शन), जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण सेट तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अक्सर सेट के क्रमपरिवर्तन होते हैं जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है।

प्राथमिक कॉम्बिनेटरिक्स में, k-क्रमपरिवर्तन, या आंशिक क्रमपरिवर्तन, एक सेट से चुने गए k विशिष्ट तत्वों की क्रमबद्ध व्यवस्था है। जब k समुच्चय के आकार के बराबर होता है, तो ये समुच्चय के क्रमचय होते हैं।

File:Rubik's cube.svg
1974 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।

इतिहास

चीन में I चिंग (पिनयिन: यी जिंग) में 1000 ईसा पूर्व के रूप में हेक्साग्राम नामक क्रमपरिवर्तन का उपयोग किया गया था।

अरब गणितज्ञ अल-खलील इब्न अहमद अल-फ़राहिदी अल-खलील (717-786) और क्रिप्टोग्राफर ने क्रिप्टोग्राफ़िक संदेशों की पुस्तक लिखी। इसमें स्वरों के साथ और बिना सभी संभावित अरबी शब्दों को सूचीबद्ध करने के लिए क्रमचय और संयोजन का पहला उपयोग शामिल है।[4]

n वस्तुओं के क्रमचय की संख्या निर्धारित करने का नियम भारतीय संस्कृति में लगभग 1150 AD के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा लीलावती में एक मार्ग शामिल है जो इसका अनुवाद करता है:

अंकगणितीय श्रृंखला के गुणन का गुणनफल एकता से शुरू और बढ़ता है और स्थानों की संख्या तक जारी रहता है, विशिष्ट अंकों के साथ संख्या की भिन्नता होगी।[5]

1677 में, फैबियन स्टैडमैन ने चेंजिंग रिंगिंग में घंटियों के क्रमपरिवर्तन की संख्या की व्याख्या करते हुए फैक्टोरियल्स का वर्णन किया। दो घंटियों से शुरू करते हुए: "पहले, दो को दो तरीकों से भिन्न होने के लिए स्वीकार किया जाना चाहिए", जिसे वह 1 2 और 2 1 दिखा कर दिखाता है।[6] इसके बाद वह बताते हैं कि तीन घंटियों के साथ "तीन में से तीन गुणा दो आंकड़े उत्पन्न होते हैं" जो फिर से सचित्र है। उनकी व्याख्या में शामिल है "3 को हटा दें, और 1.2 रहेगा; 2 को हटा दें, और 1.3 रहेगा; 1 को हटा दें, और 2.3 रहेगा"।[7] फिर वह चार घंटियों की ओर बढ़ता है और यह दर्शाता है कि तीन के चार अलग-अलग सेट होंगे। प्रभावी रूप से, यह एक पुनरावर्ती प्रक्रिया है। वह "कास्टिंग अवे" पद्धति का उपयोग करते हुए पांच घंटियों के साथ आगे बढ़ता है और परिणामी 120 संयोजनों को सारणीबद्ध करता है।[8] इस बिंदु पर वह हार मान लेता है और टिप्पणी करता है:

अब इन विधियों की प्रकृति ऐसी है कि एक संख्या में परिवर्तन सभी छोटी संख्याओं में परिवर्तन को समझ लेता है, ... इतना अधिक है कि एक संख्या पर परिवर्तनों का एक पूर्ण समूह सभी कम संख्याओं के पूर्ण अंकों को एक पूरे निकाय में एकजुट करके बनने लगता है;[9]

स्टैडमैन क्रमपरिवर्तन के विचार को विस्तृत करता है; वह 20 के एक स्थिर से वर्णमाला के अक्षरों और घोड़ों के क्रमपरिवर्तन की संख्या पर विचार करता है।[10]

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

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

क्रमचय का सबसे सरल उदाहरण पुनरावृत्ति के बिना क्रमचय है जहाँ हम n वस्तुओं को n स्थानों में व्यवस्थित करने के संभावित तरीकों की संख्या पर विचार करते हैं। एक सेट में क्रमपरिवर्तन की संख्या को परिभाषित करने के लिए फैक्टोरियल का विशेष अनुप्रयोग होता है जिसमें पुनरावृत्ति शामिल नहीं होती है। संख्या n!, "n फैक्टोरियल" पढ़ें, वास्तव में उन तरीकों की संख्या है जिनसे हम n चीजों को एक नए क्रम में पुनर्व्यवस्थित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास तीन फल हैं: एक संतरा, सेब और नाशपाती, तो हम उन्हें बताए गए क्रम में खा सकते हैं, या हम उन्हें बदल सकते हैं (उदाहरण के लिए, एक सेब, एक नाशपाती फिर एक संतरा)। तब क्रमचय की सही संख्या है आइटमों की संख्या (n) बढ़ने पर यह संख्या बहुत बड़ी हो जाती है।

इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे