क्रमचय

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

"nPr" redirects here. For other uses, see NPR (disambiguation).

File:Permutations RGB.svg

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

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

क्रमपरिवर्तन संयोजन ों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {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 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।

इतिहास

[[ हेक्साग्राम (मैं चिंग ) ]] नामक क्रमपरिवर्तन चीन में आई चिंग (पिनयिन : यी जिंग) में 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 वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या n|k-क्रमपरिवर्तन का #k-क्रमपरिवर्तन कहा जाता है। इसे के रूप में लिखा जा सकता है $nPk$ (जो n क्रमपरिवर्तन k पढ़ता है), और संख्या के बराबर है $n(n-1)\cdots (n-k+1)$ (के रूप में भी लिखा है $n!/(n-k)!$).

परिभाषा

गणित के ग्रंथों में यह लोअरकेस ग्रीक अक्षरों का उपयोग करके क्रमचय को निरूपित करने के लिए प्रथागत है। आम तौर पर, या तो $\alpha$ तथा $\beta$, या $\sigma ,\tau$ तथा $\pi$ उपयोग किया जाता है। क्रमपरिवर्तन को एक सेट से आक्षेप के रूप में परिभाषित किया जा सकता है S खुद पर। n तत्वों के साथ एक सेट के सभी क्रमपरिवर्तन एक सममित समूह बनाते हैं, जिसे निरूपित किया जाता है $S_{n}$, जहां समूह संचालन कार्यों की संरचना है। इस प्रकार दो क्रमपरिवर्तन के लिए, $\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$. किसी के लिए $\mathrm{\sigma <!--\; \sigma \; -->}$