क्रमचय

गणित में, क्रमचय (परमुटेशन) की संकल्पना को सूक्ष्म रूप से विभिन्न अर्थों में प्रयोग किया जाता है, सभी अर्थ वस्तुओं या मूल्य के क्रमपरिवर्तन (क्रमबद्ध रूप से पुनर्व्यवस्थित करना) की कार्रवाई से संबंधित हैं। अनौपचारिक रूप से, कुछ मानों (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 -संयोजन के नंबर ${\tbinom {n}{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 के आसपास ही हिंदू संस्कृति में उपलब्ध था: भारतीय गणितज्ञ भास्कर द्वारा लीलावती में एक अनुच्छेद है जिसका अनुवाद है

इकाई से शुरू और वृद्धिमान और कई स्थानों के लिए जारी अंकगणितीय श्रृंखला के बहुगुणन का उत्पाद, विशिष्ट संख्या वाले अंकों का रूपांतर होगा.^[1]

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

सामान्य बात

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

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

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

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

कॉम्बीनेटॉरिक्स में, एक क्रमपरिवर्तन का अर्थ आम तौर पर एक परिमित सेट से एक बार और केवल एक बार प्रत्येक तत्व से युक्त अनुक्रम समझा जाता है। अनुक्रम की अवधारणा सेट से इस तरह अलग है कि उसमें अनुक्रम के तत्व एक क्रम में होते है: अनुक्रम का पहला तत्व (जब तक यह खाली न हो) होता है, दूसरा तत्व (यदि उसकी लंबाई 2 से कम नहीं है) और इसी प्रकार क्रमशः होते चले जाते हैं। इसके विपरीत, सेट में तत्वों का कोई क्रम नहीं होता, (1, 2, 3) और (3, 2, 1) एक ही सेट को निरूपित करने के अलग तरीके हैं। इस अर्थ में n तत्वों के परिमित S सेट का क्रमपरिवर्तन (1,2, ..., n) से S (जिसमें कोई i अनुक्रम के i -th तत्व से मानचित्रित है) में द्विभाजन, या S (जिसके लिए x <y यदि अनुक्रम में y से पहले x आए) के पूरे क्रम के लिए चयन के तुल्य है। इस अर्थ में n ! क्रमपरिवर्तन भी S का है।

"क्रमपरिवर्तन" शब्द का एक कमजोर अर्थ भी है जो कभी-कभार प्राथमिक कॉम्बीनेटॉरिक्स ग्रंथों में प्रयोग किया जाता है, उन क्रमों को नामोद्धिष्ट करते हुए जिनमें कोई तत्व एक से अधिक बार न आए, किन्तु निर्धारित सेट के सभी तत्वों के प्रयोग की आवश्यकता न पड़े. वास्तव में इसके उपयोग में अक्सर निर्धारित $n>k$ आकार के सेट में से लिए गए तत्वों की निर्धारित लंबाई k के क्रम पर विचार करना पड़ता है। इन वस्तुओं को बिना दोहराव के क्रम के रूप में भी जाना जाता है, ऐसा शब्द जिससे "क्रमपरिवर्तन" के दूसरे, आम अर्थों के भ्रम से बचा जाता है। n के आकार के एक सेट की तत्वों के बिना दोहराव के k क्रम की लंबाई की संख्या है

n^{\underline {k}}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1),

एक संख्या जिसे n की k -th ह्रासात्मक भाज्य शक्ति के रूप में जाना जाता है और जिसके कईं दूसरे नाम और अंकन प्रचलित हैं।

अगर M एक परिमित मल्टीसेट है, तो एक मल्टीसेट क्रमपरिवर्तन M तत्वों का क्रम है जिसमें प्रत्येक तत्व उतनी बार प्रकट होता है जितनी बार M में इसकी बहुलता है। यदि M के तत्वों की बहुलता (किसी क्रम में ली जाए) $m_{1}$ , $m_{2}$ , ..., $m_{l}$ है और उनका योग (अर्थात,M का आकार) n है, तो M के मल्टीसेट क्रमपरिवर्तन की संख्या बहुपदीय गुणांक द्वारा दी जाती है

{n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}.

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

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

अंकन पद्धति

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

\sigma ={\begin{pmatrix}1&amp;2&amp;3&amp;4&amp;5\\2&amp;5&amp;4&amp;3&amp;1\end{pmatrix}};

इसका मतलब है कि σ संतुष्ट करता है σ (1)=2,σ (2)=5, σ (3)=4,σ (4)=3 औरσ (5)=1.

वैकल्पिक रूप से, हम चक्र अंकन का उपयोग कर क्रमपरिवर्तन लिख सकते हैं, जो क्रमपरिवर्तन के सफल प्रयोग के प्रभाव पर केंद्रित करता है। यह क्रमपरिवर्तन को चक्र के उत्पाद के रूप में व्यक्त करती है जो क्रमपरिवर्तन की कक्षाओं (कम से कम दो तत्वों के साथ) के अनुरूप होता है; चूंकि पृथक कक्षाएं शिथिल होती हैं, इसे सामान्य रूप से क्रमपरिवर्तन का "शिथिल चक्रों में अपघटन" कहते हैं। यह इस प्रकार काम करता है: S के कुछ X तत्व से शुरू करकेσ(x) ≠ x, अनुक्रम लिखते हैं σ के तहत क्रमिक बिम्ब का (x σ ('x ) σ (σ ('x )) ...), जब तक बिम्ब X न हो जाए, जिस बिंदु पर कोष्ठक बंद कर दिए जाते हैं। लिखे गए मान का सेट x की कक्षा बनाता है (σ के अंतर्गत) और कोष्ठकबद्ध अभिव्यक्ति σ का समानुरूप चक्र देती है। तो S के x तत्व को चुनना जारी रहता है जो पहले से लिखी गई कक्षा में नहीं है और किσ(y) ≠ y और संगत चक्र को लिखते हैं और यह क्रम जारी रहता है जब तक S के सभी तत्व लिखे गए चक्र से संबद्ध नहीं होते हैं या σ के नियत बिंदु नहीं होते. चूंकि हर नए चक्र के लिए प्रारंभ बिंदु अलग अलग तरीकों से चुना जा सकता है, सामान्यतः एक ही क्रमपरिवर्तन के लिए कई अलग अलग चक्र अंकन हैं; उदाहरण के लिए ऊपर वाले में एक उदाहरण है

{\begin{pmatrix}1&amp;2&amp;3&amp;4&amp;5\\2&amp;5&amp;4&amp;3&amp;1\end{pmatrix}}={\begin{pmatrix}1&amp;2&amp;5\end{pmatrix}}{\begin{pmatrix}3&amp;4\end{pmatrix}}={\begin{pmatrix}3&amp;4\end{pmatrix}}{\begin{pmatrix}1&amp;2&amp;5\end{pmatrix}}={\begin{pmatrix}3&amp;4\end{pmatrix}}{\begin{pmatrix}5&amp;1&amp;2\end{pmatrix}}.

σ का हर चक्र (x ₁ x ₂ ... x _l) अपने आप में एक क्रमपरिवर्तन का प्रतीक है, अर्थात जो इस कक्षा में σ के सम मूल्य लेता है (तो यह चित्रित करता है x _'i को x _i+1 के लिए i < l और x _l को x ₁), S के सभी तत्वों को स्वंय में चित्रित करते हुए. कक्षा के l आकार को चक्र की लंबाई कहा जाता है। σ की पृथक कक्षाएं परिभाषा से शिथिल हैं, तो तदनुरूपी चक्र रूपांतरित हो जाते हैं और σ इसके चक्रों का उत्पाद है (किसी भी क्रम में). इसलिए चक्र अंकन में चक्र के संयोजन की क्रमपरिवर्तन की संरचना के अंकन के रूप में व्याख्या की जा सकती है, जिस कारण से क्रमपरिवर्तन का नाम "अपघटन". यह अपघटन अनिवार्य रूप से अद्वितीय है: उत्पाद में चक्रों के पुनर्क्रम के अलावा, σ को चक्रों के उत्पाद (शायद σ के चक्रों से असंबंधित) के रूप में लिखने का कोई तरीका नहीं है जिसकी कक्षाएं शिथिल हों. चक्र अंकन कम अद्वितीय है क्योंकि प्रत्येक चक्र अलग अलग तरीकों से लिखा जा सकता है, जैसा कि उपरोक्त उदाहरण में दिया गया है जहां (5 1 2) (1 2 5) जैसे चक्र को निरूपित करता है किन्तु (5 2 1) एक अलग क्रमपरिवर्तन को निरूपित करेगा).

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

लंबाई के दो चक्रों को प्रतिस्थापन कहा जाता है; ऐसे क्रमपरिवर्तन केवल दो तत्वों की जगह बदलते हैं।

उत्पाद और व्युत्क्रम

दो क्रमपरिवर्तन का उत्पाद कार्य के रूप में उनकी संरचना के रूप में परिभाषित है, दूसरे शब्दों में σ·π वह कार्य है जो सेट के किसी भी x तत्व का σ (π (x)) में चित्रण करता है। ध्यान दें कि कार्य का अनुप्रयोग लिखने के ढंग की वजह से सबसे दायां क्रमपरिवर्तन पहले तर्क पर लागू होता है। कुछ लेखक पहले सबसे बाएं कारक को लागू करना पसंद करते हैं, पर उसके लिए क्रमपरिवर्तन उनके तर्क की दायीं ओर लिखा जाना चाहिए, उदाहरणार्थ प्रतिपादक के रूप में, x पर लागू σ x ^σ लिखा जाता है; तो उत्पाद परिभाषित किया गया है x ^σ·π =(x ^σ)^π के द्वारा. हालांकि यह क्रमपरिवर्तन गुणा करने के लिए एक अलग नियम देता है; यह लेख वहां परिभाषा का उपयोग करता है जहां सबसे दाएं क्रमपरिवर्तन को पहले लागू किया जाता है।

चूंकि दो द्विभाजनों की संरचना हमेशा एक और द्विभाजन देती है, दो क्रमपरिवर्तन का उत्पाद फिर से एक क्रमपरिवर्तन है। कार्य संरचना सहयोगात्मक होती है, इसलिए क्रमपरिवर्तन पर उत्पाद संचालन है:(σ·π)·ρ =σ ·(π·ρ). इसलिए क्रमपरिवर्तन के उत्पाद आमतौर पर कोष्ठक के बिना लिखे जाते हैं और वे आमतौर पर एक डॉट या उत्पाद को चिह्नित करने वाले अन्य निशान के भी बिना लिखे जाते हैं

पहचान क्रमपरिवर्तन, जो सेट के प्रत्येक तत्व को स्वंय में ही चित्रित करता है, इस उत्पाद का तटस्थ तत्व है। दो पंक्तियों वाले अंकन में, पहचान है

{\begin{pmatrix}1&amp;2&amp;3&amp;\cdots &amp;n\\1&amp;2&amp;3&amp;\cdots &amp;n\end{pmatrix}}.

चूंकि द्विभाजन के व्युत्क्रम हैं, इसलिए क्रमपरिवर्तन के भी हैं और σ का व्युत्क्रम σ ⁻¹है जो फिर से एक क्रमपरिवर्तन है। स्पष्ट रूप से, जब भी σ(x) =y एक का σ ⁻¹(y)=x भी है। दो पंक्तियों वाले अंकन में व्युत्क्रम दो लाइनों (और कॉलम की छँटाई यदि कोई पहली पंक्ति को क्रम में देना चाहता हो) को परस्पर बदल कर प्राप्त किया जा सकता है उदाहरण के लिए

{\begin{pmatrix}1&amp;2&amp;3&amp;4&amp;5\\2&amp;5&amp;4&amp;3&amp;1\end{pmatrix}}^{-1}={\begin{pmatrix}2&amp;5&amp;4&amp;3&amp;1\\1&amp;2&amp;3&amp;4&amp;5\end{pmatrix}}={\begin{pmatrix}1&amp;2&amp;3&amp;4&amp;5\\5&amp;1&amp;4&amp;3&amp;2\end{pmatrix}}.

चक्र अंकन में प्रत्येक चक्र में तत्वों के क्रम को पलटने से इसके व्युत्क्रम के लिए चक्र अंकन प्राप्त कर सकते हैं।

एक सहयोगात्मक उत्पाद, एक तटस्थ तत्व और इसके सभी तत्वों के लिए व्युत्क्रम से S के सभी क्रमपरिवर्तन के सेट का समूह बनाता है जिसे S का सममितीय समूह कहा जाता है।

एक परिमित सेट के प्रत्येक क्रमपरिवर्तन को प्रतिस्थापन के उत्पाद के रूप में व्यक्त किया जा सकता है। इसके अलावा, हालांकि एक दिए गए क्रमपरिवर्तन के लिए कई तरह के भाव मौजूद हो सकते हैं, उनके बीच प्रतिस्थापन की सम संख्या और विषम संख्या दोनों भाव के साथ अभिव्यक्ति नहीं हो सकती. सभी क्रमपरिवर्तन सम या विषम रूप में वर्गीकृत हैं, किसी भी अभिव्यक्ति में उनके प्रतिस्थापन की समता के अनुसार.

चक्र अंकन में लिखे क्रमपरिवर्तन गुणा की विधि कठिन है और उत्पाद के चक्र संरचित किए जा रहे क्रमपरिवर्तन से पूरी तरह अलग हो सकते हैं। हालांकि चक्र संरचना संरक्षित है σ के क्रमपरिवर्तन के अन्य क्रमपरिवर्तन π के संयुग्म के विशेष मामले में, जिसका अर्थ है उत्पाद π·σ·π ⁻¹ का निर्माण. यहाँ परिणाम का चक्र अंकन प्राप्त किया जा सकता है σ का चक्र अंकन लेकर उसकी सभी प्रविष्टियों में π लागू कर^[2].

{1, 2, ...,{0}n} के क्रमपरिवर्तन का n ×n मैट्रिक्स के रूप में प्रतिनिधित्व किया जा सकता है। ऐसा करने के दो प्राकृतिक तरीके हैं, लेकिन केवल एक के लिए ही मैट्रिक्स का गुणा उसी क्रम में क्रमपरिवर्तन के गुणा के अनुरूप होता है: यही है जो σ मैट्रिक्स M का सहयोगी है जिसकी M _i, j प्रविष्टि 1 है यदि i=σ(j) है अन्यथा 0. परिणामस्वरूप मैट्रिक्स की ठीक 1 प्रविष्टि है प्रत्येक स्तंभ में और प्रत्येक पंक्ति में एक. इस तरह के मैट्रिक्स को क्रमपरिवर्तन मैट्रिक्स कहते हैं।

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

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

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

अन्य कॉम्बीनेटॉरिक्स के गुण सीधे S के क्रम से संबंधित है और जिस तरह से क्रमपरिवर्तन इससे संबंधित हो. इस तरह के कई गुण हैं।

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

n के σ के क्रमपरिवर्तन का आरोह i < n की स्थिति है जहां निम्नलिखित मूल्य वर्तमान की तुलना में बड़ा है।

अर्थात, यदि σ = σ ₁σ ₂...σ _n, तो i एक अवरोह है अगरσ _i < σ _{_i+1}.

उदाहरण के लिए, क्रमपरिवर्तन 3452167 का आरोह है (स्थिति पर) 1,2,5,6.

इसी तरह, अवरोह एक स्थिति है i < n के साथ σ _'i > σ _{_i}+1, इसलिए $1\leq i$ के साथ प्रत्येक _i या तो σ का आरोह है या अवरोह.

k आरोह के साथ n के क्रमपरिवर्तन की संख्या इल्यूरियन संख्या $\textstyle \left\langle {n \atop k}\right\rangle$ है, यह भी k आरोह के साथ n के क्रमपरिवर्तन की संख्या है^[3].

एक क्रमपरिवर्तन काआरोही रन उस क्रमपरिवर्तन का भरा हुआ वृद्धिमान समीपस्थ अनुक्रम है जिसे दोनों ओर से बढ़ाया जा सकता है, यह क्रमिक आरोही के अधिकतम अनुक्रम के अनुरूप है (बाद वाला खाली हो सकता है: दो क्रमिक अवरोही के बीच 1 लंबाई का आरोही रन अभी भी है).

{ विरोध में क्रमपरिवर्तन का वृद्धिमान परिणाम का समीपस्थ होना आवश्यक नहीं: यह कुछ बिंदुओं पर मूल्य को हटाकर क्रमपरिवर्तन से प्राप्त तत्वों का वृद्धिमान अनुक्रम है।

उदाहरण के लिए, क्रमपरिवर्तन 2453167 के आरोही रन 245, 3 और 167 है, जबकि इसका एक वृद्धिमान परिणाम 2367 है।

अगर एक क्रमपरिवर्तन के k − 1 अवरोही रन हैं, तो यह k आरोही रन का संघ होना चाहिए. इसलिए n का क्रमपरिवर्तन k आरोही रन के साथ वही है जो k − 1 आरोही के साथ क्रमपरिवर्तन की संख्या $\textstyle \left\langle {n \atop k-1}\right\rangle$ का है^[4].

व्युत्क्रम

क्रमपरिवर्तन σ का व्युत्क्रम स्थितियों की जोड़ी (i,j) है जिसमें क्रमपरिवर्तन की प्रविष्टियांउलट क्रम में हैं: $i$ और $\sigma _{i}>\sigma _{j}$ ^[5]. तो एक अवरोही सिर्फ दो आसन्न स्थितियों पर एक व्युत्क्रम मात्र है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 के तीन व्युत्क्रम हैं:(1,3), (2,3), (4,5), प्रविष्टियों के जोड़े (2,1), (3,1), (5, 4) के लिए.

कभी कभी एक व्युत्क्रम को ऐसे मूल्य के जोड़े (σ _i,σ _j) के रूप में परिभाषित किया जाता है जिसका क्रम उलट है, इससे व्युत्क्रम की संख्या के लिए कोई अंतर नहीं पड़ता और यह जोड़ा (उलट) भी उपर्युक्त अर्थ में σ ⁻¹ उलट क्रमपरिवर्तन का व्युत्क्रम है। व्युत्क्रम की संख्या डिग्री के लिए एक महत्वपूर्ण उपाय है जिसके लिए क्रमपरिवर्तन की प्रविष्टियां क्रम से बाहर हैं, σ और σ ⁻¹ के लिए वही है। k व्युत्क्रम वाले क्रमपरिवर्तन को व्वयवस्थित करने के लिए (अर्थात इसे पहचान क्रमपरिवर्तन में परिणत करना), आसन्न प्रतिस्थापन को क्रमिक रूप से लागू करके (दाएं-गुणा द्वारा), सदैव संभव है और ऐसे प्रचालनों के k अनुक्रम की आवश्यकता होती है। इसके अलावा आसन्न प्रतिस्थापन के कोई भी उचित चुनाव काम करेंगे: इसके लिए पर्याप्त होता है हर कदम पर i का प्रतिस्थापन चुनना और जहांi + 1 i अब तक परिशोधित क्रमपरिवर्तन का अवरोही है (ताकि प्रतिस्थापन इस विशेष अवरोही को हटायें यद्यपि यह अन्य अवरोही बना सकता है).

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

वास्तव में, आसन्न प्रतिस्थापन के सभी अनुक्रमों की गणना करके जोσ को पहचान के रूप में रूपांतरित कर दे, σ को आसन्न प्रतिस्थापन के उत्पाद के रूप में लिखने से न्यूनतम लंबाई लेखन की सभी अभिव्यक्तियों की पूरी सूची  प्राप्त होती है।

k व्युत्क्रम के साथ n के क्रमपरिवर्तन की संख्या महोनियन संख्या^[6] के द्वारा व्यक्त की जाती है, यह उत्पाद के विस्तार में X ^k का गुणांक है

\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1}),

जिसे q -भाज्य [n ]_q! (X के एवजी q) के रूप में भी जाना जाता है।

दोहराए बिना अनुक्रम की गिनती

इस खंड में, सेट S का k -क्रमपरिवर्तन S के k विशिष्ट तत्वों का व्यवस्थित अनुक्रम है। उदाहरण के लिए, दिए गए वर्णों का सेट {{1}C, E, G, I, N, R}, अनुक्रम ICE 3-क्रमपरिवर्तन है, RING और RICE 4-क्रमपरिवर्तन है, NICER और REIGN 5-क्रमपरिवर्तन हैं और CRINGE 6-क्रमपरिवर्तन है; चूंकि उत्तरार्द्ध सभी वर्णों का उपयोग करता है, यह साधारण कॉम्बीनेटोरियल अर्थ में दिए गए सेट का क्रमपरिवर्तन है।

दूसरी ओर ENGINE क्रमपरिवर्तन नहीं है, पुनरावृत्ति के कारण: यह E और N तत्वों का दो बार उपयोग करता है।

n को S का आकार होने दें, चयन के लिए उपलब्ध तत्वों की संख्या.

k -क्रमपरिवर्तन के निर्माण में अनुक्रम के पहले तत्व के लिए n संभाव्य विकल्प हैं, तत्पश्चात यह 1-क्रमपरिवर्तन की संख्या है।

एक बार जब इसे चुना लिया गया हो, S के n − 1तत्वों में से चुना जा सकता है, दूसरे तत्व का चयनn − 1 इस तरह से किया जा सकता है जिससे संभाव्य 2-क्रमपरिवर्तन से कुल n × (n − 1)

प्राप्त हो.

अनुक्रम के प्रत्येक उत्तरोतर तत्व के लिए, संभावनाओं की संख्या कम हो जाती है जिससे प्राप्त संख्या है

n × (n − 1) × (n − 2) ... × (n − k + 1) संभाव्य K -क्रमपरिवर्तन.

इससे विशेष रूप से n -क्रमपरिवर्तन की संख्या प्राप्त होती है (जिसमें एक बार S के सभी तत्व शामिल होते हैं, इसलिए वे केवल S के क्रमपरिवर्तन हैं:

n × (n − 1) × (n − 2) × ...

× 2 × 1,

एक संख्या जो गणित में इतनी बार घटित होती है कि इसे कॉम्पैक्ट अंकन "n !" दिया गया है और इसे "n भाज्य" कहा जाता है।

ये n -क्रमपरिवर्तन S के तत्वों को दोहराए बिना सबसे लंबे अनुक्रम हैं जो इस तथ्य से परिलक्षित हैं कि k -क्रमपरिवर्तन की संख्या का उपरोक्त सूत्र शून्य देता है जब भी k > n होता है।

n तत्वों के एक सेट के k -क्रमपरिवर्तन की संख्या कभी कभी P (n, k) या इसी तरह के अंकन (आमतौर पर n तत्वों के सेट के k -संयोजन की संख्या के लिए एक अंकन के साथ होती है जिसमें "P " का प्रतिस्थापन "C " से हुआ हो) से द्योतक होती है।

वह अंकन k -क्रमपरिवर्तन की गिनती के अतिरिक्त अन्य सन्दर्भों में शायद ही कभी इस्तेमाल किया जाता है लेकिन संख्या के लिए अभिव्यक्ति कई अन्य स्थितियों में पैदा होती है।

n से शुरू होने वाले और यूनिट चरण द्वारा घटने वाले k कारकों का उत्पाद होने के नाते इसे n की k -th ह्रासमान भाज्य शक्ति कहा जाता है:

n^{\underline {k}}=n\times (n-1)\times (n-2)\times \cdots \times (n-k+1),

हालांकि कई अन्य नाम और अंकन उपयोग में हैं, जैसे कि पोछाम्मेर प्रतीक में विस्तृत हैं। जब k ≤ n भाज्य शक्ति अतिरिक्त कारकों द्वारा पूरी की जा सकती है: n ^k × (n − k)!

 = n !, जो लेखन की अनुमति देता है

n^{\underline {k}}={\frac {n!}{(n-k)!}}.

दाहिने हाथ की ओर अक्सर k -क्रमपरिवर्तन की संख्या के लिए अभिव्यक्ति के रूप में दी जाती है लेकिन इसका मुख्य गुण कॉम्पैक्ट भाज्य अंकन का उपयोग करना है।

k कारकों के उत्पाद को संभावित रूप में बहुत बड़े उत्पादों के भागफल के रूप में व्यक्त करना, जहां हर में सभी कारक भी न्यूमरेटर में स्पष्ट रूप से उपस्थित हैं, विशेष रूप से योग्य नहीं है; गणना की एक विधि के रूप में अतिप्रवाह या पूर्णन त्रुटियों का अतिरिक्त खतरा है।

यह भी नोट किया जाना चाहिए कि k > n होने पर अभिव्यक्ति अपरिभाषित है, जबकि

उन मामलों में k -क्रमपरिवर्तन की संख्या n ^k बस 0 है।

कंप्यूटिंग में क्रमपरिवर्तन

क्रमपरिवर्तन का क्रमांकन

n के क्रमपरिवर्तन का प्रतिनिधित्व 0 ≤ N < n ! के साथ N पूर्णांक द्वारा किया जा सकता है, बशर्ते कि अनुक्रम के रूप में संख्या और क्रमपरिवर्तन के सामान्य प्रतिनिधित्व के बीच रूपान्तरण के लिए सुविधाजनक विधियां प्रदान की जा रही हों.

यह यादृच्छिक क्रमपरिवर्तन का सबसे सुसम्बद्ध प्रतिनिधित्व करता है और कंप्यूटिंग में

तब विशेष रूप से आकर्षक है जब n इतना छोटा हो कि N को मशीन शब्द में पकड़ा जा सके; 32-bit शब्दों के लिए इसका अर्थ है n ≤ 12 और 64-bit शब्दों के लिए इसका अर्थ है n ≤ 20.

 d n , d _{n −1}, ..., d ₂, d ₁ संख्याओं के अनुक्रम के मध्यवर्ती रूप के माध्यम से रूपान्तरण किया जा सकता है, जहां i  से कम d _'i एक गैर नकारात्मक पूर्णांक हो (d ₁ को हटाया जा सकता है, क्योंकि यह हमेशा 0 होता है लेकिन इसकी उपस्थिति से एक क्रमपरिवर्तन के बाद के रूपांतरण का वर्णन करना सरल होता है).

तब पहला कदम भाज्य संख्या प्रणाली में N की अभिव्यक्ति मात्र है जो बस मिश्रित मूलांक विशेष का प्रतिनिधित्व है, जहां n ! तक की संख्या के लिए

उत्तरोतर अंकों का आधार n n − 1, ..., 2, 1 हैं।

दूसरे कदम में इस क्रम की व्याख्या लेह्मर कोड के रूप में या (लगभग सम रूप से) व्युत्क्रम तालिका के रूप में की जाती है।

रॉथ आरेख
_i ＼ ^{σ _i}	1	2	3	4	5	6	7	8	9	लेह्मर कोड
$\sigma =(6,3,8,1,4,9,7,2,5)$
1	×	×	×	×	×	•				d ₉ = 5
2	×	×	•							d ₈ = 2
3	×	×		×	×		×	•		d ₇ = 5
4	•									d ₆ = 0
5		×		•						d ₅ = 1
6		×			×		×		•	d ₄ = 3
7		×			×		•			d ₃ = 2
8		•								d ₂ = 0
9					•					d ₁ = 0
व्युत्क्रम टेबल	3	6	1	2	4	0	2	0	0

लेह्मर कोड में क्रमपरिवर्तन σ के लिए, संख्या d n पहले पद σ ₁ के लिए किए गए चुनाव का प्रतिनिधित्व करती है, संख्या d _{_n}−₁ प्रतिनिधित्व करती है दूसरे पद σ ₁ के लिए सेट के शेषn − 1 तत्वों के बीच किए गए चुनाव का और इसी प्रकार आगे भी. और स्पष्ट शब्दों में, प्रत्येक d _n +1−i शेष तत्वों की संख्या देता है जो पद σ i से निश्चित रूप से कम होती है। चूंकि वे शेष तत्व किसी पश्च पद σ j के रूप में आने के लिए बाध्य हैं, अंक d _n+1−i व्युत्क्रमों (i, j) की गिनती i को छोटे सूचकांक के रूप में शामिल करके करता है (जिसके लिए मूल्य j की संख्या i < j और σ i > σ j है). σ के लिए व्युत्क्रम तालिका काफ़ी समान है, लेकिन यहाँ d _n+1−k व्युत्क्रम (i, j) की संख्या गिनती है जहां k = σ j घटित होता है विपरीत क्रम में प्रदर्शित दो मूल्यों में न्यूनतम के रूप में आता है^[7]. दोनो संकेतनों की n रॉथ आरेख^[8] में एक n द्वारा कल्पना की जा सकती है जिसमें (i, σ i ) पर बिंदु क्रमपरिवर्तन की प्रविष्टियों के प्रतीक है और (i, σ j ) पर क्रॉस व्युत्क्रम (i, j) के प्रतीक है; व्युत्क्रम की परिभाषा के द्वारा क्रॉस किसी भी ऐसे वर्ग में आता है जो अपने स्तंभ में (j, σ _j) बिंदु से पहले और अपनी पंक्ति में (i, σ _i) बिंदु दोनो तरह से आता है। लेह्मर कोड उत्तरोतर पंक्तियों में क्रॉसों की संख्या को सूचीबद्ध करता है, जबकि व्युत्क्रम तालिका उत्तरोतर स्तंभों में क्रॉसों की संख्या को सूचीबद्ध करती है; व्युत्क्रम क्रमपरिवर्तन के लिए लेह्मर कोड है और लेह्मर कोड के लिए व्युत्क्रम क्रमपरिवर्तन.

लेह्मर कोड d n , d _{n −1}, ..., d ₂, d ₁ को एक व्यवस्थित S सेट के क्रमपरिवर्तन में प्रभावी रूप से परिवर्तित करने के लिए, वर्द्धमान क्रम में S के तत्वों की सूची के साथ शुरू कर सकते हैं और i के लिए 1 से n सेट σ _i से सूचीबद्ध तत्वों से बढ़ाएँ जिसमें अन्य d _n +1−i पहले घटित हों और उस तत्व को सूची से निकाल दें. व्युत्क्रम तालिका d n , d _{_n}−1, ..., d ₂, d ₁ को समानुरूप क्रमपरिवर्तन में परिवर्तित करने के लिए, एक शुरू से खाली अनुक्रम में S के सबसे बड़े से सबसे छोटे तत्वों को डालते हुए d ₁ से d _n से संख्या को उलट सकते हैं; चरण में व्युत्क्रम तालिका से संख्या d का प्रयोग करते हुए, अनुक्रम में S के तत्व उस बिंदु पर डाले गए हों जहां पहले से ही मौजूद d तत्व इससे पहले आए हों. वैकल्पिक रूप से सम्मिलन तालिका और S के तत्व दोनो की संख्या पर विपरीत क्रम में कार्रवाई कर सकते हैं, शुरुआत n के खाली स्लॉटों की पंक्ति से की जा सकती है और हर चरण पर S के तत्व को खाली स्लॉट में डालें जिससे पहले d अन्य खाली स्लॉट हों.

उत्तरोतर प्राकृतिक संख्या के भाज्य संख्या प्रणाली में सफल परिवर्तन से ये अनुक्रम कोषगत क्रम में उत्पन्न होते हैं (जो किसी भी मिश्रित मूलांक प्रणाली के मामले में होता है) और इन्हें आगे क्रमपरिवर्तन में परिवर्तित करने से मूलांक क्रम संरक्षित रहता है बशर्ते कि लेह्मर कोड की व्याख्या का इस्तेमाल किया जाता है (व्युत्क्रम तालिकाओं का उपयोग करने से, भिन्न क्रम प्राप्त होता है, जहां क्रमपरिवर्तन की तुलना उनकी प्रथम प्रविष्टियों के मूल्य की अपेक्षा उनकी 1 प्रविष्टियों के स्थान द्वारा की जानी शुरू हो जाती है) प्रतिनिधित्व भाज्य संख्या प्रणाली में संख्या के योग से क्रमपरिवर्तन के व्युत्क्रम की संख्या प्राप्त होती है और उस योग की समता से क्रमपरिवर्तन के चिह्नक प्राप्त होते है। इसके अतिरिक्त व्युत्क्रम तालिका में शून्य की स्थिति क्रमपरिवर्तन की बाएं-से-दाएं महत्तम का मूल्य देती है (उदाहरण 6,8, 9 में) जबकि लेह्मर कोड में शून्य की स्थिति दाएं-से-बाएं लघुतम की स्थिति है (उदाहरण की स्थिति में 1, 2, 5 मूल्य की 4,8, 9 स्थिति); इससे सभी क्रमपरिवर्तनों में ऐसे अन्तिम के वितरण की कंप्यूटिंग होती है। लेह्मर कोड के साथ एक क्रमपरिवर्तन d n , d _n−1, ..., d ₂, d ₁ एक आरोहण हैn − i अगर और सिर्फ़ अगरd_i ≥ d_i+1.

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

कंप्यूटिंग में दिए गए मूल्यों के अनुक्रम का क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। यह करने की सबसे उपयोगी विधि इस बात पर निर्भर करती है कि कुछ, यादृच्छिक रूप से चुने गए, क्रमपरिवर्तन, या सभी क्रमपरिवर्तन अपेक्षित है और बाद के मामले में यदि एक विशिष्ट क्रम की आवश्यकता है। एक और प्रश्न है कि क्या दिए गए अनुक्रम में प्रविष्टियों के बीच संभाव्य समानता को ध्यान में रखा जाना है; अगर ऐसा है तो अनुक्रम के विशिष्ट मल्टीसेट क्रमपरिवर्तन ही उत्पन्न किए जाने चाहिए.

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

क्रमपरिवर्तन का यादृच्छिक उत्पादन

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

यादृच्छिक क्रमपरिवर्तन उत्पन्न करने का मूलभूत विचार यादृच्छिक रूप से एक n ! अनुक्रम जो पूर्णांक d ₁,d ₂,...,d _n का हो, का संतोषजनक0 ≤ d_i < i उत्पादन करना है (चूंकि d ₁ हमेशा शून्य होता है इसे छोड़ा जा सकता है) और द्विभाजित सादृश्यता के माध्यम से इसे एक क्रमपरिवर्तन में परिवर्तित करना है। परवर्ती सादृश्य के लिए (परवर्ती) अनुक्रम की लेह्मर कोड के रूप में व्याख्या की जा सकती है और इससे प्राप्त होती है उत्पादन की विधि जो रोनाल्ड ए. फ़िशर और फ़्रैंक येट्स द्वारा पहली बार 1938 में प्रकाशित हुई थी।^[9] उस समय कंप्यूटर कार्यान्वयन कोई मुद्दा नहीं था, इस विधि से लेह्मर कोड से क्रमपरिवर्तन में दक्षता से परिवर्तन करने में ऊपर रेखाचित्रित कठिनाई आती है। भिन्न द्विभाजित सादृश्यता का उपयोग करके इसका हल निकाला जा सकता है: क्रम के शेष i तत्वों में से d i के प्रयोग के बाद तत्व का चयन करके (i के ह्रासमान मूल्य के लिए), बजाए इसके कि तत्व को हटाया जाए और तत्वों को एक स्थान आगे करके अनुक्रम को सुसम्बद्ध बनाने से तत्व को अंतिम शेष तत्व प्रतिस्थापित कर देता है। इस प्रकार चयन के लिए शेष तत्व समय में प्रत्येक बिंदु पर एक क्रमागत रेंज बनाते हैं, भले ही वे उसी क्रम में नहीं होते जैसे कि वे मूल अनुक्रम में थे। पूर्णांक के अनुक्रम से क्रमपरिवर्तन का प्रतिचित्रण कुछ हद तक जटिल है, पर तत्काल प्रवेशण द्वारा इसे प्रत्येक क्रमपरिवर्तन ठीक एक तरह से उत्पन्न करते देखा जा सकता है। जब चयनित तत्व अंतिम शेष तत्व हो, प्रतिस्थापन संक्रिया को छोड़ा जा सकता है। यह इतने प्रायः नहीं होते कि अवस्था का परीक्षण न्यायसंगत हो, पर चयन के अभ्यर्थियों में अंतिम तत्व अवश्य शामिल किया जाना चाहिए ताकि इस बात की गारंटी हो कि सभी क्रमपरिवर्तन उत्पन्न किए जा सकते हैं।

a [0], a [1], ..., a [n − 1] के यादृच्छिक क्रमपरिवर्तन के उत्पादन के लिए परिणामी कलन गणित को निम्न छद्मसंकेत में वर्णित किया जा सकता है:

i के लिए n से नीचे तक 2
करें d_i ← random element of { 0, ..., i − 1 }
स्वैप a [d_i ] and a [i − 1]

सभी क्रमपरिवर्तनों का सुव्यवस्थित उत्पादन

दिए गए अनुक्रम के सभी क्रमपरिवर्तनों के सुव्यवस्थित उत्पादन के कई तरीके हैं; नुथ ने द आर्ट ऑफ़ कम्प्यूटर प्रोग्रामिंग के आगामी संस्करण में इस चर्चा के लिए पर्याप्त अनुभाग समर्पित किए हैं^[10]. एक शास्त्रीय कलन गणित, जो सरल और लचीला दोनों है, वह कोषगत क्रम में नए क्रमपरिवर्तन को ढूँढने पर आधारित है, अगर इसका अस्तित्व है। यह मूल्यों के दोहराव को संभाल सकता है, जिसके लिए यह हर बार पृथक मल्टीसेट क्रमपरिवर्तन उत्पन्न करता है। साधारण क्रमपरिवर्तन के लिए भी कोषगत क्रम में (संभवतः भाज्य संख्या प्रणाली का प्रयोग करते हुए) लेह्मर कोड में मूल्यों के उत्पादन की तुलना में यह अधिक सक्षम है। इसे उपयोग करने के लिए, वर्धमान (क्षीण) क्रम में अनुक्रम की छंटाई शुरू करते हैं (जिससे इसका कोषगत न्यूनतम क्रमपरिवर्तन प्राप्त होता है) और फिर अगले क्रमपरिवर्तन के मिलने तक दोहराते रहते हैं। यह विधि 14 वीं सदी के भारत में पंडित नारायण से शुरू हुई और तब से निरन्तर विकसित होती आ रही है^[10].

निम्नलिखित कलन गणित एक दिए गए क्रमपरिवर्तन के बाद कोषगत रूप से अगला क्रमपरिवर्तन उत्पन्न करता है। इससे दिए गए क्रमपरिवर्तन का स्थान बदल जाता है।

खोजें सबसे बड़ा सूचकांक k जैसे किa[k] < a[k + 1] . यदि ऐसा कोई सूचकांक उपलब्ध नहीं है, अंतिम क्रमपरिवर्तन ही क्रमपरिवर्तन है।
खोजें सबसे बड़ा सूचकांक l जैसे किa[k] < a[l]. चूंकि k + 1 ऐसा सूचकांक है, l अच्छी तरह से परिभाषित किया गया है और वांछनीय हैk < l.
a [k] को a [l ] से बदलें.
अनुक्रम को a [k + 1] से a [n ] के अंतिम तत्व सहित उल्टा कर दें.

चरण 1 के बाद, हमें पता है कि k स्थिति के बाद सभी तत्व सख्ती से क्षीण ह्रासमान अनुक्रम बनाते हैं, इसलिए इन तत्वों का कोई क्रमपरिवर्तन कोषगत क्रम में अग्रिम नही होगा; अग्रिम होने के लिए a [k ] में वृद्धि ज़रूरी है। चरण 2 छोटा मूल्य a [l ] ढूँढता है a [k ] को बदलने के लिए और चरण 3 में इन्हें बदलने से k के बाद अनुक्रम क्षीण ह्रासमान क्रम में प्राप्त होता है। इस अनुक्रम को चरण 4 में पलटने से इसका कोषगत न्यूनतम क्रमपरिवर्तन उत्पन्न होता है और पूरे अनुक्रम की प्रारंभिक अवस्था के लिए कोषगत उत्तराधिकारी.

सॉफ्टवेयर कार्यान्वयन

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

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

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

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

अनुप्रयोग

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

इन्हें भी देखें

गणित प्रवेशद्वार

नोट

↑ NL Biggs, द रूटस ऑफ़ कॉम्बीनेटॉरिक्स, Historia Math. 6 (1979) 109-136
↑ साँचा:Google books quote.
↑ कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 3
↑ कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 4f
↑ कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 43
↑ कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 43ff
↑ ^अ ^आ डी.ई. नुथ., द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग, खण्ड 3, सॉर्टिंग एंड सर्चिंग, एडिसन-वेसली (1973), p. 12. इस पुस्तक में लेह्मर कोड का उल्लेख (उस नाम का प्रयोग किए बगैर) अभ्यास 5.1.1−7 (p. 19) में व्युत्क्रम तालिकाओं के चर C ₁,...,C _n के रूप में, दो अन्य चरों के साथ किया गया है।
↑ H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263−305. Cited in^[7], p. 14.
↑ Fisher, R.A.; Yates, F. (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd संस्करण). London: Oliver & Boyd. पपृ॰ 26–27. OCLC 14222135.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
↑ ^अ ^आ Knuth, D. E. (2005). "Generating All Tuples and Permutations". The Art of Computer Programming. 4, Fascicle 2. Addison-Wesley. पपृ॰ 1–26. आई॰ऍस॰बी॰ऍन॰ 0-201-85393-0.
↑ Curmi, Jamie (2009-01-10). "Summary of Functions in Excel and Numbers" (PDF). मूल (PDF) से 24 दिसंबर 2010 को पुरालेखित. अभिगमन तिथि 2009-01-26.
↑ "3GPP TS 36.212". मूल से 1 दिसंबर 2008 को पुरालेखित. अभिगमन तिथि 30 जून 2010.

सन्दर्भ

मिकलॉस बोना. "कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स", चैपमैन हॉल सीआरसी-2004. ISBN 1-903679-03-6
डोनाल्ड नुथ. द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग, खण्ड 4: जेनरेटिंग ऑल ट्यूप्लस एंड परम्युटेशन्स, Fascicle 2, प्रथम मुद्रण. एडिसन-वेसली, 2005. ISBN 0-201-85393-0.
डोनाल्ड नुथ. द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग, खण्ड 3: सॉर्टिंग एंड सर्चिंग, द्वितीय संस्करण. एडिसन-वेसली, 1998. ISBN 0-201-89685-0 अनुभाग 5.1:कॉम्बीनेटोरियल प्रॉपर्टीज़ ऑफ़ परम्युटेशन्स, पीपी. 11-72.
Humphreys, J. F.. ए कोर्स इन ग्रुप थ्योरी . ऑक्सफ़ोर्ड यूनिवर्सिटी प्रेस, 1996. ISBN 978-0-19-853459-4

बाहरी कड़ियाँ

अंकपाश - P(n, r) (मानस गणित)
A HISTORY OF PIṄGALA’S COMBINATORICS (JAYANT SHAH, Northeastern University, Boston, Mass)

[1] NL Biggs, द रूटस ऑफ़ कॉम्बीनेटॉरिक्स, Historia Math. 6 (1979) 109-136

[2] साँचा:Google books quote.

[3] कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 3

[4] कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 4f

[5] कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 43

[6] कॉम्बीनेटॉरिक्स ऑफ़ परम्युटेशन्स, ISBN 1-58488-434-7, M. Bona, 2004, p. 43ff

[Knuth-7] अ ^आ डी.ई. नुथ., द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग, खण्ड 3, सॉर्टिंग एंड सर्चिंग, एडिसन-वेसली (1973), p. 12. इस पुस्तक में लेह्मर कोड का उल्लेख (उस नाम का प्रयोग किए बगैर) अभ्यास 5.1.1−7 (p. 19) में व्युत्क्रम तालिकाओं के चर C ₁,...,C _n के रूप में, दो अन्य चरों के साथ किया गया है।

[8] H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263−305. Cited in^[7], p. 14.

[9] Fisher, R.A.; Yates, F. (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd संस्करण). London: Oliver & Boyd. पपृ॰ 26–27. OCLC 14222135.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)

[Knuth_fasc2-10] अ ^आ Knuth, D. E. (2005). "Generating All Tuples and Permutations". The Art of Computer Programming. 4, Fascicle 2. Addison-Wesley. पपृ॰ 1–26. आई॰ऍस॰बी॰ऍन॰ 0-201-85393-0.

[11] Curmi, Jamie (2009-01-10). "Summary of Functions in Excel and Numbers" (PDF). मूल (PDF) से 24 दिसंबर 2010 को पुरालेखित. अभिगमन तिथि 2009-01-26.

[12] "3GPP TS 36.212". मूल से 1 दिसंबर 2008 को पुरालेखित. अभिगमन तिथि 30 जून 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]