क्रमचय

गणित में, क्रमचय (परमुटेशन) की संकल्पना को सूक्ष्म रूप से विभिन्न अर्थों में प्रयोग किया जाता है, सभी अर्थ वस्तुओं या मूल्य के क्रमपरिवर्तन (क्रमबद्ध रूप से पुनर्व्यवस्थित करना) की कार्रवाई से संबंधित हैं। अनौपचारिक रूप से, कुछ मानों (values) के एक सेट को विशेष क्रम में व्यवस्थित करना क्रमचय है। इस प्रकार सेट (1, 2, 3,) के छह क्रमचय हैं अर्थात् [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] और [3,2,1].
बीजगणित में और विशेष रूप से समूह सिद्धांत में, सेट S का क्रमचय S से स्वंय में द्विभाजन के रूप में परिभाषित है (अर्थात, ऐसा नक्शाS → S जिसमें S का हर तत्व ठीक एक बार बिम्ब मूल्य के रूप में घटित होता है). ऐसे नक्शे के लिए f का संबंध S की उस पुनर्व्यवस्था से है जिसमें S तत्व अपने बिम्ब f (S) का स्थान ले लेता है। कॉम्बीनेटॉरिक्स में, परिमित सेट S का क्रमचय इसके तत्वों की सूचीबद्ध पुनर्व्यवस्था के रूप में परिभाषित है। इस अर्थ में, S का क्रमचय उसके तत्वों की पुनर्व्यवस्था से भिन्न है। प्रारंभिक क्रम वाले सेट S के लिए, जैसे S =(1,2,3,...,n), ये दोनो अर्थ लगभग पहचाने जा सकते हैं: इस प्रारंभिक आदेश पर पहले अर्थ में क्रमपरिवर्तन लागू करने से तत्वों का वैकल्पिक क्रम प्राप्त होता है, जो दूसरे अर्थ में क्रमपरिवर्तन है। 
किसी वस्तु के भागों की पुनर्व्यवस्था के कार्य को, या उससे प्राप्त परिणाम को नामित करने के लिए अनौपचारिक रूप से क्रमपरिवर्तन शब्द का प्रयोग किया जाता है। इस प्रकार किसी शब्द के वर्णविपर्यय को इसके वर्णो का क्रमपरिवर्तन के रूप में भी परिभाषित किया जा सकता है, या कह लें कि X ³Y +7+Y ²Z बहुपदीय X ³Y +Y ²Z +7 के पदों का क्रमपरिवर्तन (से प्राप्त) है। क्रमपरिवर्तन के कार्य को प्रतीकों का प्रतिस्थापन भी कहा जा सकता है, उदाहरण के लिए जब कहते हैं कि X, Y, Z की चर राशि के (चक्रीय) क्रमपरिवर्तन द्वारा X ³Y +Y ²Z +7 से Y ³Z +Z ²X +7 प्राप्त होता है। एक उपयुक्त सममितीय सामूहिक कार्रवाई को ध्यान में रखते हुए इन कथनों को सटीक अर्थ प्रदान किया जा सकता है 
कॉम्बीनेटॉरिक्स में "क्रमपरिवर्तन" के दूसरे अर्थ को कभी कभी विस्तृत किया जाता है। प्राथमिक कॉम्बीनेटॉरिक्स में, "क्रमपरिवर्तन और संयोजन" दो संबद्ध समस्याओं का हवाला देता है, दोनों ही n तत्व के सेट से विशिष्ट k तत्व के चयन की संभावनाओं पर निर्भर करती हैं, k क्रमपरिवर्तन के लिए चयन के क्रम को ध्यान में रखा जाता है, किन्तु k -संयोजन के लिए अनदेखा कर दिया जाता है। दरअसल k -क्रमपरिवर्तन की गणना का प्रयोग k -संयोजन के नंबर  की गणना की दिशा में एक कदम के रूप में किया जाता है और सेट के क्रमपरिवर्तन की संख्या n ! की गणना के रूप में भी (उपर्युक्त उल्लिखित दो के किसी भी अर्थ में) होता है। तथापि k -क्रमपरिवर्तन ऐसे क्रमपरिवर्तन के तब तक अनुरूप नहीं होते जब तक k = n, अर्थात, चयन में सभी उपलब्ध तत्व शामिल न हों. क्रमपरिवर्तन की धारणा को भिन्न तरीके से व्यापक बनाने के लिए, एक सेटS के स्थान पर, ऐसे परिमित मल्टीसेट M के साथ शुरुआत की जा सकती है, जिसमें कुछ मूल्य एक से अधिक बार घटित होते हों. M का (मल्टीसेट) क्रमपरिवर्तन M के तत्वों का अनुक्रम है जिनमें से प्रत्येक ठीक उतनी बार घटित होता है जितनी बार M में. इस प्रकार M = [1,1,1,2,3,3] के लिए, [3,1,2,1,1,3] का अनुक्रम M का मल्टीसेट क्रमपरिवर्तन है, किन्तु [3,1,2,1,2,3,1] नहीं है। 
लगभग गणित के प्रत्येक क्षेत्र में, क्रमपरिवर्तन कमोबेश प्रमुख रूप से होते हैं। किसी परिमित सेट पर भिन्न क्रम लागू किए जाने से वे उत्पन्न होते हैं, संभवतः क्योंकि ऐसे क्रम को अनदेखा करते हुए हम पता लगाना चाहते हैं कि इस प्रकार कितने विन्यासों की पहचान होती है। इसी तरह के कारणों से कंप्यूटर विज्ञान में कलन गणित की छँटाई के अध्ययन में क्रमपरिवर्तन घटित होता है। बीजगणित में, सममितीय समूह की संकल्पना के माध्यम से क्रमपरिवर्तन का विस्तृत अध्ययन करने के लिए एक संपूर्ण विषय समर्पित किया गया है। इसकी संरचना के लिए महत्वपूर्ण है क्रमपरिवर्तन की रचना की संभावना: अनुवर्ती क्रम में दो पुनर्व्यवस्थाओं को निष्पादित करते हुए, संयोजन तीसरी पुनर्व्यवस्था को परिभाषित करता है। 
n वस्तु के क्रमपरिवर्तन की संख्या निर्धारित करने का नियम 1150 के आसपास ही हिंदू संस्कृति में उपलब्ध था: भारतीय गणितज्ञ भास्कर द्वारा लीलावती में एक अनुच्छेद है जिसका अनुवाद है 
इकाई से शुरू और वृद्धिमान और कई स्थानों के लिए जारी अंकगणितीय श्रृंखला के बहुगुणन का उत्पाद, विशिष्ट संख्या वाले अंकों का रूपांतर होगा. 
क्रमपरिवर्तन की मदद से असंबंधित गणितीय प्रश्नों के पहले अध्ययन का पहला मामला 1770 में सामने आया, जब जोसफ़ लुइस लाग्रेंज ने, बहुपदीय समीकरणों का अध्ययन करते हुए पाया कि समीकरण के मूल के क्रमपरिवर्तन के गुण इसे हल करने की संभावनाओं से संबंधित हैं। इस कार्य से हुए विकास का परिणाम इवरिस गाल्वा, के काम के माध्यम से, गाल्वा सिद्धांत में प्रतिपादित हुआ, जो मूल द्वारा बहुपदीय समीकरणों (अज्ञात में) को हल करने में संभव और असंभव का पूरा विवरण देता है। आधुनिक गणित में इसी तरह की कई स्थितियां हैं, जहां समस्या को समझने के लिए संबंधित क्रमपरिवर्तन के अध्ययन की आवश्यकता होती है।

सामान्य बात

क्रमपरिवर्तन की संकल्पना का प्रयोग निम्नलिखित सन्दर्भों में किया जाता है।

समूह सिद्धांत में

समूह सिद्धांत (ग्रुप थिअरी) और संबंधित क्षेत्रों में, यादृच्छिक सेटों, अपरिमित का भी क्रमपरिवर्तन होता है। S का स्वंय में द्विभाजन सेट S का क्रमपरिवर्तन है। यह क्रमपरिवर्तन की अनुमति देता है, जो क्रमपरिवर्तन के समूहों को परिभाषित करता है। अगर n तत्वों का परिमित सेट S है, तो n ! S का क्रमपरिवर्तन है।

समूह सिद्धांत में क्रमपरिवर्तन

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

कॉम्बीनेटॉरिक्स में क्रमपरिवर्तन

कॉम्बीनेटॉरिक्स में n तत्वों के साथ सेट S का क्रमपरिवर्तन किसी क्रम में (हर तत्व एक बार घटता है) S के तत्वों की सूची है। इसे सेट (1, 2, ...,n) से S में औपचारिक द्विभाजन के रूप में परिभाषित किया जा सकता है। ध्यान दें कि यदि S (1, 2, ...,n) के बराबर है तो यह परिभाषा समूह सिद्धांत की परिभाषा से मेल खाती है। आमतौर पर (1, 2 ... n) के बजाए तत्वों के क्रम से सुसज्जित किसी भी सेट का इस्तेमाल कर सकते हैं। 
कॉम्बीनेटॉरिक का गुण जो क्रमपरिवर्तन की समूह सैद्धांतिक व्याख्या से संबंधित है और जिसे S के कुल क्रम का उपयोग किए बिना परिभाषित किया जा सकता है, वह क्रमपरिवर्तन σ की चक्र संरचना है। यह n के चक्रों की लंबाई का वर्णन करते हुए σ का विभाजन है। यहाँ σ के हर तय बिंदु के लिए विभाजन में भाग "1" है। एक क्रमपरिवर्तन जिसका कोई निश्चित बिंदु नहीं है उसे अव्यवस्था कहा जाता है। 
अन्य कॉम्बीनेटॉरिक्स के गुण सीधे S के क्रम से संबंधित है और जिस तरह से क्रमपरिवर्तन इससे संबंधित हो. इस तरह के कई गुण हैं।

आरोह, अवरोह और रन

n के σ के क्रमपरिवर्तन का आरोह i < n की स्थिति है जहां निम्नलिखित मूल्य वर्तमान की तुलना में बड़ा है।
अर्थात, यदि σ = σ ₁σ ₂...σ ₙ , तो i एक अवरोह है अगरσ ᵢ  < σ ᵢ ₊₁.
उदाहरण के लिए, क्रमपरिवर्तन 3452167 का आरोह है (स्थिति पर) 1,2,5,6.
इसी तरह, अवरोह एक स्थिति है i < n के साथ σ 'ᵢ   > σ ᵢ +1, इसलिए  के साथ प्रत्येक ᵢ  या तो σ का आरोह है या अवरोह.
k आरोह के साथ n के क्रमपरिवर्तन की संख्या इल्यूरियन संख्या  है, यह भी k  आरोह के साथ n के क्रमपरिवर्तन की संख्या है.
एक क्रमपरिवर्तन काआरोही रन उस क्रमपरिवर्तन का भरा हुआ वृद्धिमान समीपस्थ अनुक्रम है जिसे दोनों ओर से बढ़ाया जा सकता है, यह क्रमिक आरोही के अधिकतम अनुक्रम के अनुरूप है (बाद वाला खाली हो सकता है: दो क्रमिक अवरोही के बीच 1 लंबाई का आरोही रन अभी भी है).
{ विरोध में क्रमपरिवर्तन का वृद्धिमान परिणाम का समीपस्थ होना आवश्यक नहीं: यह कुछ बिंदुओं पर मूल्य को हटाकर क्रमपरिवर्तन से प्राप्त तत्वों का वृद्धिमान अनुक्रम है।
 
उदाहरण के लिए, क्रमपरिवर्तन 2453167 के आरोही रन 245, 3 और 167 है, जबकि इसका एक वृद्धिमान परिणाम 2367 है।
अगर एक क्रमपरिवर्तन के k − 1 अवरोही रन हैं, तो यह k आरोही रन का संघ होना चाहिए. इसलिए n का क्रमपरिवर्तन k आरोही रन के साथ वही है जो k − 1 आरोही के साथ क्रमपरिवर्तन की संख्या  का है.

क्रमपरिवर्तन उत्पन्न करने के लिए कलन गणित

कंप्यूटिंग में दिए गए मूल्यों के अनुक्रम का क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। यह करने की सबसे उपयोगी विधि इस बात पर निर्भर करती है कि कुछ, यादृच्छिक रूप से चुने गए, क्रमपरिवर्तन, या सभी क्रमपरिवर्तन अपेक्षित है और बाद के मामले में यदि एक विशिष्ट क्रम की आवश्यकता है। एक और प्रश्न है कि क्या दिए गए अनुक्रम में प्रविष्टियों के बीच संभाव्य समानता को ध्यान में रखा जाना है; अगर ऐसा है तो अनुक्रम के विशिष्ट मल्टीसेट क्रमपरिवर्तन ही उत्पन्न किए जाने चाहिए.
n के क्रमपरिवर्तन को उत्पन्न करने का एक स्पष्ट तरीका है कि लेह्मर कोड के लिए मूल्य उत्पन्न किए जाएं (संभवतः n ! तक पूर्णांक भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करते हुए) और उन्हें समरूप क्रमपरिवर्तन में परिवर्तित किया जाए. हालांकि बाद का चरण भले ही स्पष्ट है पर कुशलता से लागू करना कठिन है क्योंकि इसके लिए एक यादृच्छिक स्थिति पर, एक सारणी या श्रंखलाबद्ध सूची के रूप में अनुक्रम के प्रत्यक्ष प्रतिनिधित्व के अनुक्रम में से प्रत्येक चयन की n संक्रिया और उससे विलोपन अपेक्षित है; परिवर्तन के लिए दोनों के लिए (भिन्न कारणों से) लगभग n ²/4 संक्रियाएं अपेक्षित हैं। n के विशेष रूप से छोटे होने की (खास तौर पर यदि सभी क्रमपरिवर्तन का उत्पादन आवश्यक हो) संभावना से अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित दोनों उत्पादन के लिए सरल विकल्प उपलब्ध हैं जो ज़्यादा कारगर होते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है हालांकि निश्चित रूप से संभव है, कि ऐसी विशेष डेटा संरचना को नियोजित किया जाए जिससे O (n logn) समय में लेह्मर कोड क्रमपरिवर्तन में रूपांतरण किया जा सके.

कैलकुलेटर के कार्य

कई वैज्ञानिक कैलकुलेटरों में n के k -क्रमपरिवर्तन की संख्या की गणना के लिए अंतर्निहित कार्य-प्रणाली होती है। क्रमपरिवर्तन का कार्य अक्सर मेनू के कई स्तरों के माध्यम से उपलब्ध होता है; कार्य का उपयोग कैसे किया जाए यह आमतौर पर कैलकुलेटरों के सहायक दस्तावेज़ों में दिया जाता है।

स्प्रेडशीट के कार्य

अधिकतर स्प्रेडशीट सॉफ्टवेयर में n के k -क्रमपरिवर्तन की गणना का कार्य अंतर्निहित रहता है। एप्पलज़ नंबर्ज़ '08 सॉफ्टवेयर में यह कार्य नहीं था किन्तु एप्पलज़ नंबर्ज़ '09 सॉफ्टवेयर पैकेज में इसे सुधारा गया।

अनुप्रयोग

क्रमपरिवर्तन का प्रयोग त्रुटि का पता लगाने और कलन गणित के सुधार में इंटरलीवर घटक में किया जाता है जैसे टर्बो कोड, 
उदाहरण के लिए 3GPP लांग टर्म इवॉल्यूशन मोबाइल दूरसंचार मानक इन विचारों का उपयोग करता है (3GPP तकनीकी विनिर्देशन देखें 36.212).
ऐसे अनुप्रयोग वांछनीय गुणों वाले क्रमपरिवर्तन के त्वरित उत्पादन का सवाल उठाते हैं। एक तरीका बहुपदीय क्रमपरिवर्तन पर आधारित है।