क्रमचय और संचय

क्रमचय वस्तुओं की क्रमबद्ध व्यवस्थाओं की गणना करते हैं और संचय अक्रमबद्ध चयनों की गणना करते हैं; साथ मिलकर वे गणना का प्रारंभिक मूल बनाते हैं।

Definition

किसी समुच्चय का क्रमचय उसके अवयवों की एक क्रमबद्ध व्यवस्था है (या समुच्चय का स्वयं पर एक विशेषण); एक संचय किसी समुच्चय से निश्चित संख्या में अवयवों का एक अक्रमबद्ध चयन है।

Scope

यह विषय व्यवस्थाओं (पुनरावृत्ति के साथ और बिना), चयनों और उनके परिष्करणों की गणना विकसित करता है, जिसमें अव्यवस्थाएँ (derangements), वृत्तीय क्रमचय (circular permutations), और प्रतिबंधित स्थितियों वाले क्रमचय शामिल हैं। यह क्रमचय सांख्यिकी जैसे अवरोहण (descents), व्युत्क्रमण (inversions), और चक्र संरचना (cycle structure) का परिचय देता है, जो प्रारंभिक गणना को सममित समूह (symmetric group) के समृद्ध आधुनिक सिद्धांत से जोड़ते हैं।

Core questions

• n भिन्न वस्तुओं को कितने तरीकों से व्यवस्थित किया जा सकता है, और उनमें से r को कितने तरीकों से व्यवस्थित किया जा सकता है?
• पुनरावृत्ति और अविभेद्यता व्यवस्थाओं की गणना को कैसे बदलती है?
• अव्यवस्थाएँ (derangements) क्या हैं, और एक यादृच्छिक क्रमचय कितनी बार किसी भी अवयव को ठीक नहीं करता है?
• क्रमचयों पर कौन से आँकड़े समवितरित (equidistributed) हैं?

Key concepts

• गुणनखंड (Factorial) और घटता गुणनखंड (falling factorial)
• पुनरावृत्ति के साथ और बिना व्यवस्थाएँ
• अव्यवस्थाएँ (Derangements)
• वृत्तीय क्रमचय (Circular permutations)
• व्युत्क्रमण (Inversions) और अवरोहण (descents)
• स्टरलिंग संख्याएँ (Stirling numbers)

Key theories

क्रमचयों का चक्र अपघटन (Cycle decomposition of permutations)

प्रत्येक क्रमचय अद्वितीय रूप से असंयुक्त चक्रों में गुणनखंडित होता है; उनके चक्र प्रकार द्वारा क्रमचयों की गणना प्रथम प्रकार की स्टर्लिंग संख्याओं द्वारा नियंत्रित होती है और सममित समूह की संरचना को रेखांकित करती है।

अव्यवस्था गणना (Derangement enumeration)

कोई निश्चित बिंदु (fixed point) न होने वाले क्रमचयों की संख्या, समावेशन-बहिष्करण (inclusion-exclusion) के माध्यम से प्राप्त की जाती है, जो n!/e के करीब पहुँचती है, जिससे यह शास्त्रीय परिणाम मिलता है कि लगभग 37% क्रमचय अव्यवस्थाएँ हैं।

Clinical relevance

क्रमचय और संचय की गणना प्रायिकता (समान रूप से संभावित परिणाम), छँटाई और फेरबदल एल्गोरिदम, प्रायोगिक डिजाइन, और क्रिप्टोग्राफिक कुंजी स्थानों में दिखाई देती है, जहाँ एक व्यवस्था स्थान का आकार कठिनाई और सुरक्षा निर्धारित करता है।

History

क्रमचयों के संयोजन विज्ञान को मैकमाहोन के 20वीं सदी के शुरुआती संयोजन विश्लेषण पर काम द्वारा व्यवस्थित किया गया था और बाद में क्रमचय सांख्यिकी के आधुनिक सिद्धांत के माध्यम से गहरा किया गया।

Key figures

• Percy MacMahon
• Richard P. Stanley

Seminal works

• stanley2011

Frequently asked questions

n अवयवों के एक समुच्चय में कितने क्रमचय होते हैं?

इसमें n! क्रमचय होते हैं, जो n तक के सभी धनात्मक पूर्णांकों का गुणनफल है, क्योंकि n स्थितियों में से प्रत्येक को एक भिन्न शेष अवयव द्वारा भरा जाता है।

अव्यवस्था (derangement) क्या है?

एक अव्यवस्था एक क्रमचय है जिसमें कोई भी अवयव अपनी मूल स्थिति में नहीं रहता है, जैसे कि एक पुनर्व्यवस्था जहाँ कोई भी पत्र अपने स्वयं के लिफाफे में वापस नहीं आता है।