क्रमचय

For other uses, see क्रमचय (disambiguation).

"एनपीआर" redirects here. For other uses, see एनपीआर (बहुविकल्पी).

छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है

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

क्रमपरिवर्तन संयोजनों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {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 से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है। अर्थात्, यह S से S तक का एक कार्य है जिसके लिए प्रत्येक तत्व के प्रतिबिंब के मान के लिए ठीक एक बार होता है। यह S के तत्वों की पुनर्व्यवस्था से संबंधित है जिसमें प्रत्येक तत्व S को संगत f(s) द्वारा प्रतिस्थापित किया जाता है। उदाहरण के लिए, ऊपर बताए गए क्रमचय (3, 1, 2) को फ़ंक्शन $\alpha$ के रूप में परिभाषित किया गया है

$\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2$.

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

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

File:Rubik's cube.svg

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

इतिहास

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

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

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

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

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

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

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

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

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

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

इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे $nPk$ (जो "n permute k" पढ़ता है) के रूप में लिखा जा सकता है, और संख्या $n(n-1)\cdots (n-k+1)$ के बराबर है। $n(n-1)\cdots (n-k+1)$ (जिसे $n!/(n-k)!$). के रूप में भी लिखा जाता है)

परिभाषा

गणित के ग्रंथों में यह लोअरकेस ग्रीक अक्षरों का उपयोग करके क्रमचय को निरूपित करने के लिए प्रथागत है। आमतौर पर, या तो $\alpha$ और $\beta$ , या $\sigma ,\tau$ और $\pi$ उपयोग किया गया हैं।

क्रमचय को समुच्चय S से स्वयं पर आक्षेप के रूप में परिभाषित किया जा सकता है। n तत्वों के साथ एक सेट के सभी क्रमपरिवर्तन एक सममित समूह बनाते हैं, जिसे S के रूप में दर्शाया जाता है, जहां समूह संचालन कार्य रचना है। इस प्रकार दो क्रमपरिवर्तन के लिए, $\pi$ और $\sigma$ तथा समूह में $S_{n}$ चार स्वयंसिद्ध समूह हैं:

1. क्लोजर (गणित) : यदि $\pi$ तथा $\sigma$ में हैं $S_{n}$ तो ऐसा है $\pi \sigma .$ सहबद्धता: किन्हीं तीन क्रमपरिवर्तनों के लिए $\pi ,\sigma ,\tau \in S_{n}$, $(\pi \sigma )\tau =\pi (\sigma \tau ).$
2. पहचान तत्व : एक पहचान क्रमचय है, निरूपित $\operatorname {id}$ और द्वारा परिभाषित $\operatorname {id} (x)=x$ सभी के लिए $x\in S$. किसी के लिए $\sigma \in S_{n}$, $\operatorname {id} \sigma =\sigma \operatorname {id} =\sigma .$
3. उलटा तत्व : प्रत्येक क्रमचय के लिए $\pi \in S_{n}$, एक व्युत्क्रम क्रमचय मौजूद है $$