बारह गुना शैली (ट्वेल्व फोल्ड वे): Difference between revisions
(Created page with "{{short description|Systematic classification of 12 related enumerative problems concerning two finite sets}} {{technical|date=March 2019}} साहचर्य में...") |
No edit summary |
||
Line 1: | Line 1: | ||
{{short description|Systematic classification of 12 related enumerative problems concerning two finite sets}} | {{short description|Systematic classification of 12 related enumerative problems concerning two finite sets}} | ||
{{technical|date= | {{technical|date=मार्च 2019}} | ||
[[साहचर्य]] में, बारह गुना तरीका दो परिमित | [[साहचर्य]] में, बारह गुना तरीका दो परिमित समुच्चयों से संबंधित 12 संबंधित गणनात्मक समस्याओं का एक व्यवस्थित वर्गीकरण है, जिसमें गणना [[क्रमपरिवर्तन]], संयोजन, [[ multiset ]] और विभाजन या तो एक समुच्चय या [[विभाजन (संख्या सिद्धांत)]] के विभाजन की शास्त्रीय समस्याएं सम्मिलित हैं। वर्गीकरण के विचार का श्रेय [[जियान-कार्लो रोटा]] को दिया जाता है, और नाम [[जोएल स्पेंसर]] द्वारा सुझाया गया था।<ref>[[Richard P. Stanley]] (1997). [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics, Volume I'']. Cambridge University Press. {{ISBN|0-521-66351-2}}. p.41</ref> | ||
== | == संक्षिप्त विवरण == | ||
मान लीजिए कि {{mvar|N}} और {{mvar|X}} परिमित समुच्चय हो। मान लीजिए कि <math>n=|N|</math> और <math>x=|X|</math> समुच्चय की [[प्रमुखता]] हो। इस प्रकार {{mvar|N}} एक {{mvar|n}}-समुच्चय, और {{mvar|X}} एक {{mvar|x}}-तय करना। | |||
हम जिस सामान्य समस्या पर विचार करते हैं, वह है फलन (गणित) के [[तुल्यता वर्ग]]ों की गणना। <math>f: N \to X</math>. | हम जिस सामान्य समस्या पर विचार करते हैं, वह है फलन (गणित) के [[तुल्यता वर्ग]]ों की गणना। <math>f: N \to X</math>. | ||
कार्य निम्नलिखित तीन प्रतिबंधों में से एक के अधीन हैं: | कार्य निम्नलिखित तीन प्रतिबंधों में से एक के अधीन हैं: | ||
# कोई | # कोई प्रतिबन्ध नहीं: प्रत्येक {{mvar|a}} में {{mvar|N}} द्वारा भेजा जा सकता है {{mvar|f}} किसी को {{mvar|b}} में {{mvar|X}}, और प्रत्येक {{mvar|b}} कई बार हो सकता है। | ||
# {{mvar|f}} [[इंजेक्शन समारोह]] है: प्रत्येक मान <math>f(a)</math> के लिए {{mvar|a}} में {{mvar|N}} एक दूसरे से अलग होना चाहिए, और इसलिए प्रत्येक {{mvar|b}} में {{mvar|X}} की [[छवि (गणित)]] में अधिकतम एक बार हो सकता है {{mvar|f}}. | # {{mvar|f}} [[इंजेक्शन समारोह|अंतःक्षेपक]] है: प्रत्येक मान <math>f(a)</math> के लिए {{mvar|a}} में {{mvar|N}} एक दूसरे से अलग होना चाहिए, और इसलिए प्रत्येक {{mvar|b}} में {{mvar|X}} की [[छवि (गणित)]] में अधिकतम एक बार हो सकता है {{mvar|f}}. | ||
# {{mvar|f}} विशेषण | # {{mvar|f}} विशेषण है: प्रत्येक के लिए {{mvar|b}} में {{mvar|X}} कम से कम एक होना चाहिए {{mvar|a}} में {{mvar|N}} ऐसा है कि <math>f(a) = b</math>, इस प्रकार प्रत्येक {{mvar|b}} की छवि में कम से कम एक बार होगा {{mvar|f}}. | ||
(स्थिति{{mvar|f}} is [[Bijection]] केवल एक विकल्प है जब <math>n=x</math>; | (स्थिति{{mvar|f}} is [[Bijection]] केवल एक विकल्प है जब <math>n=x</math>; परन्तु तब यह दोनों के समान है{{mvar|f}} अंतःक्षेपक है और{{mvar|f}} विशेषण है।) | ||
चार अलग-अलग [[तुल्यता संबंध]] हैं जिन्हें | चार अलग-अलग [[तुल्यता संबंध]] हैं जिन्हें फलनों के समुच्चय पर परिभाषित किया जा सकता है {{mvar|f}} से {{mvar|N}} को {{mvar|X}}: | ||
# समानता; | # समानता; | ||
# के क्रम[[परिवर्तन]] [[तक]] समानता {{mvar|N}}; | # के क्रम[[परिवर्तन]] [[तक]] समानता {{mvar|N}}; | ||
# के क्रमपरिवर्तन तक समानता {{mvar|X}}; | # के क्रमपरिवर्तन तक समानता {{mvar|X}}; | ||
# के क्रमपरिवर्तन तक समानता {{mvar|N}} और {{mvar|X}}. | # के क्रमपरिवर्तन तक समानता {{mvar|N}} और {{mvar|X}}. | ||
फलनों पर तीन प्रतिबन्धों और चार समकक्ष संबंधों को जोड़ा जा सकता है {{math|1=3 × 4 = 12}} तौर तरीकों। | |||
फलनों के समतुल्य वर्गों की गणना की बारह समस्याओं में समान कठिनाइयाँ सम्मिलित नहीं हैं, और उन्हें हल करने के लिए एक व्यवस्थित तरीका नहीं है। समस्याओं में से दो तुच्छ हैं (तुल्यता वर्गों की संख्या 0 या 1 है), पाँच समस्याओं का उत्तर n और x के गुणक सूत्र के संदर्भ में है, और शेष पाँच समस्याओं का उत्तर संयोजक फलनों (स्टर्लिंग संख्या) के संदर्भ में है और दिए गए भागों की संख्या के लिए विभाजन (संख्या सिद्धांत)। | |||
इस | इस समायोजन में शास्त्रीय गणना समस्याओं का समावेश इस प्रकार है। | ||
* एक्स के एन-क्रमपरिवर्तन ( | * एक्स के एन-क्रमपरिवर्तन (अर्थात, [[आंशिक क्रमपरिवर्तन]] या पुनरावृत्ति के बिना अनुक्रम) की गणना #केस i|अंतःक्षेपक फलनों की गणना के समान है {{math|''N'' → ''X''}}. | ||
* X के n-संयोजनों की गणना #case ininjective | * X के n-संयोजनों की गणना #case ininjective प्रफलनों की गणना करने के समान है {{math|''N'' → ''X''}} N के क्रमपरिवर्तन तक। | ||
* समुच्चय X के क्रमपरिवर्तनों की गणना करना अंतःक्षेपी | * समुच्चय X के क्रमपरिवर्तनों की गणना करना अंतःक्षेपी फलनों की गणना के समान है {{math|''N'' → ''X''}} जब n = x, और #case s|surjective फलनों की गणना करने के लिए भी {{math|''N'' → ''X''}} कब {{math|1=''n'' = ''x''}}. | ||
* X में तत्वों के आकार n (जिसे पुनरावृत्ति के साथ n-संयोजन के रूप में भी जाना जाता है) के | * X में तत्वों के आकार n (जिसे पुनरावृत्ति के साथ n-संयोजन के रूप में भी जाना जाता है) के बहु-समुच्चय की गणना करना सभी #case fn|फ़ंक्शंस की गणना करने के समान है {{math|''N'' → ''X''}} N के क्रमपरिवर्तन तक। | ||
* समुच्चय N के x उपसमुच्चय में विभाजनों की गणना करना सभी #केस sx | प्रक्षेप | * समुच्चय N के x उपसमुच्चय में विभाजनों की गणना करना सभी #केस sx | प्रक्षेप फलनों को गिनने के समान है {{math|''N'' → ''X''}} X के क्रमपरिवर्तन तक। | ||
* संख्या n की x भागों में [[रचना (संख्या सिद्धांत)]] की गणना सभी #केस एसएन | प्रक्षेप | * संख्या n की x भागों में [[रचना (संख्या सिद्धांत)]] की गणना सभी #केस एसएन | प्रक्षेप फलनों की गणना के समान है {{math|''N'' → ''X''}} N के क्रमपरिवर्तन तक। | ||
== दृष्टिकोण == | == दृष्टिकोण == | ||
Line 37: | Line 37: | ||
बारह प्रकार से विभिन्न समस्याओं पर विभिन्न दृष्टिकोणों से विचार किया जा सकता है। | बारह प्रकार से विभिन्न समस्याओं पर विभिन्न दृष्टिकोणों से विचार किया जा सकता है। | ||
=== | === गेंद और संदूक === | ||
पारम्परिक रूप से कई समस्याओं को | पारम्परिक रूप से कई समस्याओं को बारह गुना तरीके से फलनों को परिभाषित करने के बजाय गेंदों को संदूकों (या कुछ इसी तरह के दृश्य) में रखने के संदर्भ में तैयार किया गया है। समुच्चय एन को गेंदों के समुच्चय के साथ पहचाना जा सकता है, और एक्स को संदूक के समुच्चय के साथ पहचाना जा सकता है; समारोह ƒ : {{math|''N'' → ''X''}} फिर गेंदों को बक्से में वितरित करने के तरीके का वर्णन करता है, अर्थात् प्रत्येक गेंद को संदूक ƒ(a) में डालकर। एक फलन अपने कार्यक्षेत्र में प्रत्येक मान के लिए एक अद्वितीय छवि प्रदान करता है; यह संपत्ति इस संपत्ति से परिलक्षित होती है कि कोई भी गेंद केवल एक संदूक में जा सकती है (इस आवश्यकता के साथ कि कोई भी गेंद संदूक के बाहर नहीं रहनी चाहिए), जबकि कोई भी संदूक गेंदों की मनमानी संख्या को समायोजित कर सकता है। इसके अतिरिक्त ƒ को अंतःक्षेपी होने की आवश्यकता का अर्थ है किसी एक संदूक में एक से अधिक गेंद डालने से मना करना, जबकि ƒ को आच्छादक होने की आवश्यकता का अर्थ है कि प्रत्येक संदूक में कम से कम एक गेंद हो। | ||
N या X के तुल्यता संबंध क्रमपरिवर्तन की गणना गेंदों या | N या X के तुल्यता संबंध क्रमपरिवर्तन की गणना गेंदों या संदूकों को क्रमशः, अप्रभेद्य कह कर परिलक्षित होती है। यह एक सटीक सूत्रीकरण है, जिसका उद्देश्य यह इंगित करना है कि अलग-अलग विन्यासों को अलग-अलग नहीं गिना जाना चाहिए, यदि गेंदों या संदूकों के कुछ आदान-प्रदान से एक को दूसरे में परिवर्तित किया जा सकता है। परिवर्तन की इस संभावना को क्रमपरिवर्तन द्वारा क्रिया द्वारा औपचारिक रूप दिया जाता है। | ||
=== | === प्रतिदर्श === | ||
कुछ | कुछ स्थिति के विषय में सोचने का दूसरा तरीका आंकड़ों में [[नमूनाकरण (सांख्यिकी)|प्रतिदर्श (सांख्यिकी)]] के संदर्भ में है। एक्स वस्तु (या लोगों) की आबादी की कल्पना करें, जिनमें से हम एन चुनते हैं। दो अलग-अलग योजनाओं को सामान्य रूप से वर्णित किया जाता है, जिन्हें [[प्रतिस्थापन के साथ नमूनाकरण|प्रतिस्थापन के साथ प्रतिदर्श]] और [[प्रतिस्थापन के बिना नमूनाकरण|प्रतिस्थापन के बिना प्रतिदर्श]] के रूप में जाना जाता है। पूर्व स्थिति में (प्रतिस्थापन के साथ प्रतिदर्श), एक बार जब हम एक वस्तु चुन लेते हैं, तो हम इसे आबादी में वापस रख देते हैं, ताकि हम इसे फिर से चुन सकें। परिणाम यह है कि प्रत्येक विकल्प अन्य सभी विकल्पों की [[सांख्यिकीय स्वतंत्रता]] है, और प्रतिरूपो के समुच्चय को तकनीकी रूप से [[स्वतंत्र समान रूप से वितरित]] के रूप में संदर्भित किया जाता है। हालांकि, बाद वाले स्थिति में, एक बार जब हम एक वस्तु चुन लेते हैं, तो हम उसे एक तरफ रख देते हैं ताकि हम उसे फिर से न चुन सकें। इसका अर्थ है कि किसी वस्तु को चुनने की क्रिया का निम्नलिखित सभी विकल्पों पर प्रभाव पड़ता है (विशेष वस्तु को फिर से नहीं देखा जा सकता है), इसलिए हमारी पसंद एक दूसरे पर निर्भर हैं। | ||
प्रतिदर्श योजनाओं के मध्य एक दूसरा अंतर यह है कि क्या आदेश देना महत्व रखता है। उदाहरण के लिए, यदि हमारे पास दस वस्तु हैं, जिनमें से हम दो चुनते हैं, तो विकल्प (4,7) अलग है (7,4) यदि क्रमण देना महत्व रखता है; दूसरी ओर, यदि आदेश देने से कोई फर्क नहीं पड़ता है, तो विकल्प (4,7) और (7,4) समतुल्य हैं। (इसके विषय में सोचने का एक और तरीका यह है कि प्रत्येक विकल्प को वस्तु संख्या से क्रमबद्ध करें, और परिणाम के किसी भी डुप्लीकेट को फेंक दें।) | |||
नीचे दी गई तालिका की पहली दो पंक्तियाँ और स्तंभ क्रम पर विचार किए बिना और बिना प्रतिस्थापन के | नीचे दी गई तालिका की पहली दो पंक्तियाँ और स्तंभ क्रम पर विचार किए बिना और बिना प्रतिस्थापन के प्रतिरूप के अनुरूप हैं। प्रतिस्थापन के साथ प्रतिरूप के स्थिति किसी भी एफ लेबल वाले पंक्ति में पाए जाते हैं, जबकि बिना प्रतिस्थापन के प्रतिरूप के स्थिति अंतःक्षेपक एफ लेबल वाले पंक्ति में पाए जाते हैं। ऐसे स्थिति जहां क्रमण देने वाले स्थिति अलग लेबल वाली पंक्ति में पाए जाते हैं, और ऐसे स्थिति जहां क्रमण देने से कोई फर्क नहीं पड़ता, वे S लेबल वाली पंक्ति में पाए जाते हैं<sub>''n''</sub> कक्षाओं। प्रत्येक तालिका प्रविष्टि इंगित करती है कि किसी विशेष प्रतिदर्श योजना में विकल्पों के कितने अलग-अलग समुच्चय हैं। इन तालिका प्रविष्टियों में से तीन [[संभाव्यता वितरण]] के अनुरूप भी हैं। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमण महत्व रखता है, एन अलग-अलग यादृच्छिक चर के [[संयुक्त वितरण]] का वर्णन करने के लिए तुलनीय है, प्रत्येक एक्स-गुना [[श्रेणीबद्ध वितरण]] के साथ। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमण देना महत्व नहीं रखता है, हालांकि, एन के एकल बहुराष्ट्रीय वितरण का वर्णन करने के लिए एक एक्स-गुना श्रेणी से तुलना की जाती है, जहां प्रत्येक श्रेणी के केवल देखे गए संख्या महत्व रखते हैं। प्रतिस्थापन के बिना प्रतिदर्श जहां आदेश देना कोई महत्व नहीं रखता है, एक एकल [[बहुभिन्नरूपी हाइपरज्यामितीय वितरण]] के साथ तुलना करने योग्य है। प्रतिस्थापन के बिना प्रतिदर्श जहां आदेश महत्व रखता है वह संभाव्यता वितरण के अनुरूप नहीं लगता है।<ref>[[Robert V. Hogg and Elliot A. Tanis]] (2001). ''Probability and Statistical Inference''. Prentice-Hall, Inc. {{ISBN|0-13-027294-9}}. p.81</ref> ध्यान दें कि सभी अंतःक्षेपक स्थिति में (अर्थात प्रतिस्थापन के बिना प्रतिदर्श), विकल्पों के समुच्चय की संख्या शून्य है जब तक कि {{math|''N'' ≤ ''X''}}. (उपर्युक्त स्थिति में तुलनीय का अर्थ है कि संबंधित वितरण के प्रतिरूप स्थान का प्रत्येक तत्व विकल्पों के एक अलग समुच्चय से मेल खाता है, और इसलिए उपयुक्त संदूक में संख्या दिए गए वितरण के लिए प्रतिरूप स्थान के आकार को इंगित करती है।) | ||
प्रतिदर्श के परिप्रेक्ष्य से, विशेषण f लेबल वाला पंक्ति कुछ असामान्य है: अनिवार्य रूप से, हम तब तक प्रतिस्थापन के साथ प्रतिरूप लेते रहते हैं जब तक कि हम प्रत्येक वस्तु को कम से कम एक बार नहीं चुन लेते। फिर, हम गिनते हैं कि हमने कितने चुनाव किए हैं, और यदि यह N के समान नहीं है, तो सम्पूर्ण समुच्चय को बाहर फेंक दें और दोहराएं। यह कूपन कलेक्टर की समस्या के लिए अस्पष्ट रूप से तुलनीय है, जहां प्रक्रिया में प्रत्येक कूपन को कम से कम एक बार देखे जाने तक एक्स कूपन का एक समुच्चय (प्रतिस्थापन के साथ प्रतिदर्श द्वारा) एकत्र करना सम्मिलित है। ध्यान दें कि सभी विशेषण स्थिति में, पसंद के समुच्चय की संख्या शून्य है जब तक कि {{math|''N'' ≥ ''X''}}. | |||
=== | === लेबलन, चयन, समूहीकरण === | ||
एक समारोह ƒ : {{math|''N'' → ''X''}} को X या N के परिप्रेक्ष्य से माना जा सकता है। यह विभिन्न विचारों की ओर ले जाता है: | एक समारोह ƒ : {{math|''N'' → ''X''}} को X या N के परिप्रेक्ष्य से माना जा सकता है। यह विभिन्न विचारों की ओर ले जाता है: | ||
* | * फलन ƒ N के प्रत्येक तत्व को X के एक तत्व द्वारा लेबल करता है। | ||
* | * फलन ƒ एन के प्रत्येक तत्व के लिए समुच्चय एक्स के एक [[तत्व (गणित)]] का चयन करता है (चुनता है), कुल एन विकल्प। | ||
* | * फलन ƒ N के तत्वों को एक साथ समूहित करता है जिन्हें X के समान तत्व से मैप किया जाता है। | ||
ये दृष्टिकोण सभी | ये दृष्टिकोण सभी स्थिति के लिए समान रूप से अनुकूल नहीं हैं। लेबलन और चयन बिंदु एक्स के तत्वों के क्रमचय के साथ अच्छी तरह से संगत नहीं हैं, क्योंकि यह लेबल या चयन को बदलता है; दूसरी ओर समूहीकरण बिंदु विन्यास के विषय में सम्पूर्ण सूचना नहीं देता है जब तक कि एक्स के तत्वों को स्वतंत्र रूप से अनुमत नहीं किया जा सकता है। जब N को अनुमत नहीं किया जाता है, तो लेबलन और चयन बिंदु लगभग समतुल्य होते हैं, परन्तु जब यह होता है, तो चयन बिंदु अधिक अनुकूल होता है। तब चयन को एक अनियंत्रित चयन के रूप में देखा जा सकता है: X से n तत्वों के एक (बहु-) समुच्चय का एकल विकल्प बनाया जाता है। | ||
=== | === लेबलन और पुनरावृत्ति के साथ या बिना चयन === | ||
जब ƒ को N के तत्वों की | जब ƒ को N के तत्वों की लेबलन के रूप में देखा जाता है, तो बाद वाले को एक क्रम में व्यवस्थित माना जा सकता है, और X से लेबल को क्रमिक रूप से उन्हें सौंपा जा सकता है। एक आवश्यकता जो ƒ अंतःक्षेपी होने का अर्थ है कि किसी भी लेबल का दूसरी बार उपयोग नहीं किया जा सकता है; नतीजा दोहराव के बिना लेबल का अनुक्रम है। ऐसी आवश्यकता के अभाव में, पुनरावृत्ति के साथ शब्दावली अनुक्रम का उपयोग किया जाता है, जिसका अर्थ है कि लेबल का एक से अधिक बार उपयोग किया जा सकता है (हालांकि पुनरावृत्ति के बिना होने वाले अनुक्रमों की भी अनुमति है)। | ||
ƒ को X के तत्वों के एक अनियंत्रित चयन के रूप में देखते समय, उसी प्रकार का भेद | ƒ को X के तत्वों के एक अनियंत्रित चयन के रूप में देखते समय, उसी प्रकार का भेद अनुप्रयुक्त होता है। यदि ƒ अंतःक्षेपी होना चाहिए, तो चयन में X के विशिष्ट तत्व सम्मिलित होने चाहिए, इसलिए यह आकार n का X का एक उपसमुच्चय है, जिसे n-[[संयोजन]] भी कहा जाता है। आवश्यकता के बिना, एक्स का एक और एक ही तत्व चयन में कई बार हो सकता है, और परिणाम एक्स से तत्वों के आकार एन का एक बहु-समुच्चय होता है, जिसे एन-[[ बहुसंयोजन ]] या पुनरावृत्ति के साथ एन-संयोजन भी कहा जाता है। | ||
एन के | एन के लेबलन तत्वों के दृष्टिकोण से ƒ विशेषण होने की आवश्यकता का अर्थ है कि प्रत्येक लेबल का कम से कम एक बार उपयोग किया जाना है; एक्स से चयन के दृष्टिकोण से, इसका अर्थ है कि एक्स के प्रत्येक तत्व को चयन में कम से कम एक बार सम्मिलित किया जाना चाहिए। प्रक्षेपण के साथ लेबलन एन के तत्वों के समूह के समान है जिसके बाद प्रत्येक समूह को एक्स के तत्व द्वारा लेबल किया जाता है, और तदनुसार गणितीय रूप से वर्णन करने के लिए कुछ अधिक जटिल है। | ||
=== | === समुच्चय और संख्या का विभाजन === | ||
ƒ को N के तत्वों के समूह के रूप में देखते समय (जो मानता है कि X के क्रमपरिवर्तन के | ƒ को N के तत्वों के समूह के रूप में देखते समय (जो मानता है कि X के क्रमपरिवर्तन के अंतर्गत पहचान की जाती है), ƒ को विशेषण के रूप में देखने का अर्थ है कि समूहों की संख्या निश्चित रूप से x होनी चाहिए। इस आवश्यकता के बिना समूहों की संख्या अधिकतम x हो सकती है। अंतःक्षेपी ƒ की आवश्यकता का अर्थ है कि N का प्रत्येक तत्व अपने आप में एक समूह होना चाहिए, जो अधिक से अधिक एक मान्य समूह छोड़ता है और इसलिए एक अरोचक गणना समस्या देता है। | ||
इसके | इसके अतिरिक्त जब कोई N के क्रमचय के अंतर्गत पहचान करता है, तो इसका अर्थ समूहों को भूल जाना है परन्तु केवल उनके आकार को बनाए रखना है। इसके अतिरिक्त ये आकार किसी निश्चित क्रम में नहीं आते हैं, जबकि एक ही आकार एक से अधिक बार हो सकता है; कोई उन्हें संख्याओं की दुर्बलता से घटती सूची में व्यवस्थित करना चुन सकता है, जिसका योग संख्या n है। यह संख्या n के एक विभाजन (संख्या सिद्धांत) की संयोजी धारणा देता है, पूर्णतया x (आच्छादक ƒ के लिए) या अधिकतम x (यादृच्छिक ƒ के लिए) भागों में। | ||
== सूत्र == | == सूत्र == | ||
बारह गुना तरीके के विभिन्न | बारह गुना तरीके के विभिन्न स्थिति के सूत्र निम्नलिखित तालिका में संक्षेपित हैं; प्रत्येक तालिका प्रविष्टि सूत्र की व्याख्या करते हुए नीचे एक उपखंड से जुड़ती है। | ||
{| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center; border:none;" | {| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center; border:none;" | ||
|+ The twelve combinatorial objects and their enumeration formulas | |+ The twelve combinatorial objects and their enumeration formulas | ||
Line 93: | Line 93: | ||
| {{mvar|f}} | | {{mvar|f}} | ||
|- --> | |- --> | ||
| | | विशिष्ट<br>{{mvar|f}} | ||
| [[#case f|''n''-sequence in ''X'' <br><math>x^n</math>]] | | [[#case f|''n''-sequence in ''X'' <br><math>x^n</math>]] | ||
| [[#case i|''n''-permutation of ''X'' <br><math>x^{\underline n}</math>]] | | [[#case i|''n''-permutation of ''X'' <br><math>x^{\underline n}</math>]] | ||
| [[#case s|composition of ''N'' with ''x'' | | [[#case s|composition of ''N'' with ''x'' उपसमुच्चय <br><math>x!\left\{{n \atop x}\right\}</math>]] | ||
|- | |- | ||
| '''S'''<sub>''n''</sub> orbits <br>{{math|1=''f'' ∘ S<sub>''n''</sub>}} | | '''S'''<sub>''n''</sub> orbits <br>{{math|1=''f'' ∘ S<sub>''n''</sub>}} | ||
| [[#case fn|'' | | [[#case fn|''X का'' ''n''-बहुउपसमुच्चय <br><math>\binom{x + n - 1}{n}</math>]] | ||
| [[#case in|''n''- | | [[#case in|''n''-उपसमुच्चय of ''X''<br><math>\binom{x}{n}</math>]] | ||
| [[#case sn|composition of ''n'' with ''x'' terms <br><math>\binom{n - 1}{n - x}</math>]] | | [[#case sn|composition of ''n'' with ''x'' terms <br><math>\binom{n - 1}{n - x}</math>]] | ||
| | |||
|- | |- | ||
| '''S'''<sub>''x''</sub> orbits <br>{{math|1=S<sub>''x''</sub> ∘ ''f''}} | | '''S'''<sub>''x''</sub> orbits <br>{{math|1=S<sub>''x''</sub> ∘ ''f''}} | ||
| [[#case fx|partition of ''N'' into ≤ ''x'' | | [[#case fx|partition of ''N'' into ≤ ''x'' उपसमुच्चयs <br><math>\sum_{k=0}^x\left\{{n \atop k}\right\}</math>]] | ||
| [[#case ix|partition of ''N'' into ≤ ''x'' elements <br><math>[n \leq x]</math>]] | | [[#case ix|partition of ''N'' into ≤ ''x'' elements <br><math>[n \leq x]</math>]] | ||
| [[#case sx|partition of ''N'' into ''x'' | | [[#case sx|partition of ''N'' into ''x'' उपसमुच्चय <br><math>\left\{{n \atop x}\right\}</math>]] | ||
| | |||
|- | |- | ||
| '''S'''<sub>''n''</sub>×'''S'''<sub>''x''</sub> orbits <br>{{math|1=S<sub>''x''</sub> ∘ ''f'' ∘ S<sub>''n''</sub>}} | | '''S'''<sub>''n''</sub>×'''S'''<sub>''x''</sub> orbits <br>{{math|1=S<sub>''x''</sub> ∘ ''f'' ∘ S<sub>''n''</sub>}} | ||
Line 113: | Line 115: | ||
| [[#case snx|partition of ''n'' into ''x'' parts <br><math>p_x(n)</math>]] | | [[#case snx|partition of ''n'' into ''x'' parts <br><math>p_x(n)</math>]] | ||
|} | |} | ||
उपयोग की जाने वाली विशेष | उपयोग की जाने वाली विशेष संकेत पद्धति हैं: | ||
* गिरती तथ्यात्मक शक्ति <math display="inline">x^{\underline n} = \frac{x!}{(x - n)!} = x(x - 1)(x - 2) \cdots (x - n + 1)</math>, | * गिरती तथ्यात्मक शक्ति <math display="inline">x^{\underline n} = \frac{x!}{(x - n)!} = x(x - 1)(x - 2) \cdots (x - n + 1)</math>, | ||
* पोचममेर प्रतीक # वैकल्पिक अंकन <math display="inline">x^{\overline n} = \frac{(x + n - 1)!}{(x - 1)!} = x(x + 1)(x + 2) \cdots (x + n - 1)</math>, | * पोचममेर प्रतीक # वैकल्पिक अंकन <math display="inline">x^{\overline n} = \frac{(x + n - 1)!}{(x - 1)!} = x(x + 1)(x + 2) \cdots (x + n - 1)</math>, | ||
* तथ्यात्मक <math display="inline">n! = n^{\underline n} = n(n-1)(n-2)\cdots1</math> | * तथ्यात्मक <math display="inline">n! = n^{\underline n} = n(n-1)(n-2)\cdots1</math> | ||
* [[दूसरी तरह की स्टर्लिंग संख्या]] <math display="inline">\left\{{n \atop k}\right\}</math>, n तत्वों के एक | * [[दूसरी तरह की स्टर्लिंग संख्या]] <math display="inline">\left\{{n \atop k}\right\}</math>, n तत्वों के एक समुच्चय को k उपसमुच्चय में विभाजित करने के तरीकों की संख्या को दर्शाता है | ||
* [[द्विपद गुणांक]] <math display="inline">\binom{n}{k} = \frac{n^{\underline k}}{k!}</math> | * [[द्विपद गुणांक]] <math display="inline">\binom{n}{k} = \frac{n^{\underline k}}{k!}</math> | ||
* [[आइवरसन ब्रैकेट]] [] एक सत्य मान को 0 या 1 के रूप में | * [[आइवरसन ब्रैकेट]] [] एक सत्य मान को 0 या 1 के रूप में विकोडन करता है | ||
* जो | * जो संख्या <math display="inline">p_k(n)</math> n के k भागों में विभाजन (संख्या सिद्धांत) का | ||
=== पंक्तियों और स्तंभों का सहज अर्थ === | === पंक्तियों और स्तंभों का सहज अर्थ === | ||
यह त्वरित सारांश है कि विभिन्न | यह त्वरित सारांश है कि विभिन्न स्थिति का क्या अर्थ है। स्थिति का विवरण नीचे दिया गया है। | ||
X क्रमांकित वस्तुओं (1 से x तक क्रमांकित) के एक | X क्रमांकित वस्तुओं (1 से x तक क्रमांकित) के एक समुच्चय के विषय में सोचें, जिसमें से हम n चुनते हैं, वस्तुओं की एक आदेशित सूची प्रदान करते हैं: उदा। अगर वहाँ <math>x = 10</math> जिन वस्तुओं को हम चुनते हैं <math>n = 3</math>परिणाम सूची (5, 2, 10) हो सकता है। फिर हम गिनते हैं कि ऐसी कितनी अलग-अलग सूचियाँ उपस्थित हैं, कभी-कभी पहले सूचियों को उन तरीकों से रूपांतरित करते हैं जो अलग-अलग संभावनाओं की संख्या को कम करते हैं। | ||
तब स्तंभों का अर्थ है: | तब स्तंभों का अर्थ है: | ||
; कोई भी f: किसी | ; कोई भी f: किसी वस्तु को चयन करने के पश्चात, हम उसे वापस रख देते हैं, ताकि हम उसे फिर से चुन सकें। | ||
; | ; अंतःक्षेपक एफ: एक वस्तु चयन करने के पश्चात, हम इसे अलग रख देते हैं, इसलिए हम इसे फिर से नहीं चुन सकते; इसलिए हम n विशिष्ट वस्तुओं के साथ समाप्त करेंगे। अनिवार्य रूप से, जब तक <math>n \leq x</math>, कोई भी सूची पूर्णतया नहीं चुनी जा सकती। | ||
; प्रक्षेप्य एफ: एक | ; प्रक्षेप्य एफ: एक वस्तु चयन करने के पश्चात, हम इसे वापस रख देते हैं, इसलिए हम इसे फिर से चुन सकते हैं - परन्तु अंत में, हमें प्रत्येक वस्तु को कम से कम एक बार चुनना होगा। अनिवार्य रूप से, जब तक <math>n \geq x</math>, कोई भी सूची पूर्णतया नहीं चुनी जा सकती। | ||
और पंक्तियों का अर्थ है: | और पंक्तियों का अर्थ है: | ||
; विशिष्ट: सूचियों को अकेला छोड़ दें; उन्हें सीधे गिनें। | ; विशिष्ट: सूचियों को अकेला छोड़ दें; उन्हें सीधे गिनें। | ||
; एस<sub>''n''</sub> कक्षाएँ: गिनने से पहले, चुने गए | ; एस<sub>''n''</sub> कक्षाएँ: गिनने से पहले, चुने गए वस्तुों की वस्तु संख्या द्वारा सूचियों को क्रमबद्ध करें, ताकि क्रम कोई महत्व न रखे, जैसे, (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10)। | ||
; एस<sub>''x''</sub> कक्षाएँ: गिनने से पहले, देखी गई वस्तुओं को फिर से क्रमांकित करें ताकि पहली देखी गई वस्तु की संख्या 1, दूसरी 2, आदि हो। यदि किसी वस्तु को एक से अधिक बार देखा गया था, तो संख्याएँ दोहराई जा सकती हैं, जैसे, (3, 5, 3), (5, 2, 5), (4, 9, 4) → (1, 2, 1) जबकि (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2). | ; एस<sub>''x''</sub> कक्षाएँ: गिनने से पहले, देखी गई वस्तुओं को फिर से क्रमांकित करें ताकि पहली देखी गई वस्तु की संख्या 1, दूसरी 2, आदि हो। यदि किसी वस्तु को एक से अधिक बार देखा गया था, तो संख्याएँ दोहराई जा सकती हैं, जैसे, (3, 5, 3), (5, 2, 5), (4, 9, 4) → (1, 2, 1) जबकि (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2). | ||
; एस<sub>''n''</sub> × एस<sub>''x''</sub> कक्षाएँ: दो सूचियाँ समान मानी जाती हैं यदि यह दोनों को पुन: व्यवस्थित करना और उन्हें ऊपर के रूप में पुन: लेबल करना और समान परिणाम उत्पन्न करना संभव है। उदाहरण के लिए, (3, 5, 3) और (2, 9, 9) को समान माना जाता है क्योंकि उन्हें (3, 3, 5) और (9, 9, 2) के रूप में फिर से क्रमित किया जा सकता है और फिर दोनों को फिर से लेबल करने से समान उत्पादन होता है सूची (1, 1, 2)। | ; एस<sub>''n''</sub> × एस<sub>''x''</sub> कक्षाएँ: दो सूचियाँ समान मानी जाती हैं यदि यह दोनों को पुन: व्यवस्थित करना और उन्हें ऊपर के रूप में पुन: लेबल करना और समान परिणाम उत्पन्न करना संभव है। उदाहरण के लिए, (3, 5, 3) और (2, 9, 9) को समान माना जाता है क्योंकि उन्हें (3, 3, 5) और (9, 9, 2) के रूप में फिर से क्रमित किया जा सकता है और फिर दोनों को फिर से लेबल करने से समान उत्पादन होता है सूची (1, 1, 2)। | ||
== बॉल और संदूक परिदृश्य का उपयोग करके तालिका का सहज अर्थ == | |||
नीचे दिया गया तालिका उपरोक्त तालिका के समान है, परन्तु यह सूत्रों को दिखाने के बजाय परिचित गेंदों और बक्से के उदाहरण का उपयोग करके उनके अर्थ की सहज समझ देता है। पंक्तियाँ गेंदों और संदूकों की विशिष्टता का प्रतिनिधित्व करती हैं। यदि मल्टी-पैक (एक संदूक में एक से अधिक गेंद), या खाली संदूक की अनुमति है तो पंक्ति दर्शाते हैं। तालिका के कक्ष उस प्रश्न को दिखाते हैं जिसका उत्तर ऊपर दिए गए सूत्र तालिका में दिए गए सूत्र को हल करके दिया जाता है। | |||
नीचे दिया गया | |||
{| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center; border:none;" border="1" | {| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center; border:none;" border="1" | ||
Line 163: | Line 164: | ||
n marked balls into x marked boxes, <br> | n marked balls into x marked boxes, <br> | ||
with no multi-packs allowed?]] | with no multi-packs allowed?]] | ||
| [[#case s|composition of ''N'' with ''x'' | | [[#case s|composition of ''N'' with ''x'' उपसमुच्चयs | ||
How many ways can you place <br> | How many ways can you place <br> | ||
n marked balls into x marked boxes, <br> | n marked balls into x marked boxes, <br> | ||
Line 169: | Line 170: | ||
|- | |- | ||
! {{nowrap|1=''f'' ∘ S<sub>''n''</sub><br />(Balls plain, Boxes marked)}} | ! {{nowrap|1=''f'' ∘ S<sub>''n''</sub><br />(Balls plain, Boxes marked)}} | ||
| [[#case fn|''n''- | | [[#case fn|''n''-बहुउपसमुच्चय of ''X'' | ||
How many ways can you place <br> | How many ways can you place <br> | ||
n plain balls into x marked boxes, <br> | n plain balls into x marked boxes, <br> | ||
with no other rules on placement?]] | with no other rules on placement?]] | ||
| [[#case in|''n''- | | [[#case in|''n''-उपसमुच्चय of ''X'' | ||
How many ways can you place <br> | How many ways can you place <br> | ||
n plain balls into x marked boxes, <br> | n plain balls into x marked boxes, <br> | ||
Line 183: | Line 184: | ||
|- | |- | ||
! {{nowrap|1=S<sub>''x''</sub> ∘ ''f''<br />(Balls marked, Boxes plain)}} | ! {{nowrap|1=S<sub>''x''</sub> ∘ ''f''<br />(Balls marked, Boxes plain)}} | ||
| [[#case fx|partition of ''N'' into ≤ ''x'' | | [[#case fx|partition of ''N'' into ≤ ''x'' उपसमुच्चयs | ||
How many ways can you place <br> | How many ways can you place <br> | ||
n marked balls into x plain boxes, <br> | n marked balls into x plain boxes, <br> | ||
Line 191: | Line 192: | ||
n marked balls into x plain boxes, <br> | n marked balls into x plain boxes, <br> | ||
with no multi-packs allowed?]] | with no multi-packs allowed?]] | ||
| [[#case sx|partition of ''N'' into ''x'' | | [[#case sx|partition of ''N'' into ''x'' उपसमुच्चयs | ||
How many ways can you place <br> | How many ways can you place <br> | ||
n marked balls into x plain boxes, <br> | n marked balls into x plain boxes, <br> | ||
Line 212: | Line 213: | ||
=== विभिन्न | === विभिन्न स्थिति का विवरण === | ||
नीचे दिए गए स्थिति को इस तरह से क्रमबद्ध किया गया है कि उन स्थिति को समूहित किया जा सके जिनके लिए गणना में उपयोग किए गए तर्क संबंधित हैं, जो दी गई तालिका में क्रम नहीं है। | |||
यह | ==== ===={{anchor|case f}} N से X तक कार्य करता है ==== | ||
यह स्थिति बिना किसी प्रतिबंध के एक्स के 'एन तत्वों के अनुक्रम' की गणना के समान है: एक फलन {{math|''f'' : ''N'' → ''X''}} N के तत्वों की n छवियों द्वारा निर्धारित किया जाता है, जिनमें से प्रत्येक को x के तत्वों के मध्य स्वतंत्र रूप से चुना जा सकता है। यह कुल x देता है<sup>n</sup> संभावनाएं। | |||
<ब्लॉककोट>उदाहरण: | <ब्लॉककोट>उदाहरण: | ||
Line 224: | Line 224: | ||
<math>\left\vert\{(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)\}\right\vert = 3^2 = 9</math></ब्लॉककोट> | <math>\left\vert\{(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)\}\right\vert = 3^2 = 9</math></ब्लॉककोट> | ||
===={{anchor|case i}} एन से एक्स ==== | ==== ===={{anchor|case i}} एन से एक्स तक अंतःक्षेपक कार्य ==== | ||
यह स्थिति X के n अलग-अलग तत्वों के अनुक्रमों की गणना के समान है, जिसे X का 'एन-क्रमपरिवर्तन' या 'बिना दोहराव वाले अनुक्रम' भी कहा जाता है; फिर से यह क्रम N के तत्वों की n छवियों द्वारा बनता है। यह स्थिति अप्रतिबंधित अनुक्रमों में से एक से भिन्न होता है जिसमें दूसरे तत्व के लिए एक विकल्प कम होता है, तीसरे तत्व के लिए दो कम होते हैं, और इसी तरह। इसलिए x की एक सामान्य शक्ति के बजाय, मान x की गिरती हुई भाज्य शक्ति द्वारा दिया जाता है, जिसमें प्रत्येक क्रमिक कारक पिछले एक से एक कम होता है। सूत्र है | |||
यह | |||
: <math> x^{\underline n} = x(x-1)\cdots(x-n+1).</math> | : <math> x^{\underline n} = x(x-1)\cdots(x-n+1).</math> | ||
ध्यान दें कि अगर {{math|''n'' > ''x''}} तो कोई कारक शून्य प्राप्त करता है, इसलिए इस | ध्यान दें कि अगर {{math|''n'' > ''x''}} तो कोई कारक शून्य प्राप्त करता है, इसलिए इस स्थिति में कोई अंतःक्षेपक कार्य नहीं है {{math|''N'' → ''X''}} बिलकुल; यह कबूतरखाने के सिद्धांत का सिर्फ एक पुनर्कथन है। | ||
<ब्लॉककोट>उदाहरण: | <ब्लॉककोट>उदाहरण: | ||
Line 235: | Line 234: | ||
<math> \left\vert\{(a, b), (a, c), (a,d), (b, a), (b, c), (b,d), (c, a), (c, b), (c,d), (d,a), (d,b), (d,c) \}\right\vert = 4^{\underline2} = 4 \times 3 = 12</math></ब्लॉककोट> | <math> \left\vert\{(a, b), (a, c), (a,d), (b, a), (b, c), (b,d), (c, a), (c, b), (c,d), (d,a), (d,b), (d,c) \}\right\vert = 4^{\underline2} = 4 \times 3 = 12</math></ब्लॉककोट> | ||
===={{anchor|case in}} एन | ==== ===={{anchor|case in}} एन के क्रमपरिवर्तन तक, एन से एक्स तक अंतःक्षेपक कार्य ==== | ||
यह स्थिति X के 'उपसमुच्चयों के साथ n तत्वों' की गणना के समान है, जिसे X का n-संयोजन भी कहा जाता है: X के n विशिष्ट तत्वों के अनुक्रमों के मध्य, जो केवल उनके शब्दों के क्रम में भिन्न होते हैं, उन्हें N के क्रमपरिवर्तन द्वारा पहचाना जाता है। चूंकि सभी स्थिति में यह समूह पूर्णतया n! विभिन्न अनुक्रमों में, हम ऐसे अनुक्रमों की संख्या को n से विभाजित कर सकते हैं! एक्स के एन-संयोजनों की संख्या प्राप्त करने के लिए। इस संख्या को द्विपद गुणांक के रूप में जाना जाता है <math>\tbinom xn</math>, जो इसलिए द्वारा दिया गया है | |||
यह | |||
:<math>\binom xn = \frac{x^{\underline n}}{n!} = \frac{x(x-1)\cdots(x-n+2)(x-n+1)}{n(n-1)\cdots2\cdot1}.</math> | :<math>\binom xn = \frac{x^{\underline n}}{n!} = \frac{x(x-1)\cdots(x-n+2)(x-n+1)}{n(n-1)\cdots2\cdot1}.</math> | ||
Line 244: | Line 242: | ||
<math> \left\vert\{\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\} \}\right\vert = \frac{4^{\underline2}}{2!} = \frac{4 \times 3}{2} = 6</math></ब्लॉककोट> | <math> \left\vert\{\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\} \}\right\vert = \frac{4^{\underline2}}{2!} = \frac{4 \times 3}{2} = 6</math></ब्लॉककोट> | ||
===={{anchor|case fn}} N से X तक के कार्य, N ==== | ==== {{anchor|case fn}} N से X तक के कार्य, N के क्रमपरिवर्तन तक ==== | ||
यह स्थिति X से 'बहु-समुच्चय्स विद एन एलिमेंट्स' की गणना के समान है (जिसे एन-मल्टीकोम्बिनेशन भी कहा जाता है)। इसका कारण यह है कि एक्स के प्रत्येक तत्व के लिए यह निर्धारित किया जाता है कि एन के कितने तत्वों को एफ द्वारा मैप किया जाता है, जबकि दो कार्य जो एक्स के प्रत्येक तत्व को समान गुण प्रदान करते हैं, हमेशा एन के क्रमपरिवर्तन द्वारा दूसरे में परिवर्तित हो सकते हैं। सूत्र सभी फलनों की गणना करता है {{math|''N'' → ''X''}} यहाँ उपयोगी नहीं है, क्योंकि N के क्रमपरिवर्तन द्वारा एक साथ समूहीकृत उनकी संख्या एक फलन से दूसरे फलन में भिन्न होती है। बल्कि, जैसा कि संयोजन#संख्या के संयोजनों की पुनरावृत्ति के अंतर्गत समझाया गया है, x तत्वों वाले एक समुच्चय से n-मल्टीकॉम्बिनेशन की संख्या को एक समुच्चय से n-संयोजनों की संख्या के समान देखा जा सकता है {{math|''x'' + ''n'' − 1}} तत्व। यह समस्या को #स्थिति में बारह गुना कम कर देता है, और परिणाम देता है | |||
यह | |||
: <math> \binom{x+n-1}n = \frac{(x+n-1)(x+n-2)\cdots(x+1)x}{n(n-1)\cdots2\cdot1} = \frac{x^{\overline n}}{n!}.</math> | : <math> \binom{x+n-1}n = \frac{(x+n-1)(x+n-2)\cdots(x+1)x}{n(n-1)\cdots2\cdot1} = \frac{x^{\overline n}}{n!}.</math> | ||
Line 253: | Line 250: | ||
<math>\left\vert\{\{a, a\}, \{a, b\}, \{a, c\}, \{b, b\}, \{b, c\}, \{c, c\}\}\right\vert = \frac{3^{\overline 2}}{2!} = \frac{4 \times 3}{2} = 6</math></ब्लॉककोट> | <math>\left\vert\{\{a, a\}, \{a, b\}, \{a, c\}, \{b, b\}, \{b, c\}, \{c, c\}\}\right\vert = \frac{3^{\overline 2}}{2!} = \frac{4 \times 3}{2} = 6</math></ब्लॉककोट> | ||
===={{anchor|case sn}} N | ==== {{anchor|case sn}} N के क्रमपरिवर्तन तक, N से X तक विशेषण कार्य करता है ==== | ||
यह स्थिति X से n तत्वों के साथ बहु-समुच्चय्स की गणना के समान है, जिसके लिए X का प्रत्येक तत्व कम से कम एक बार होता है। यह x के तत्वों की बहुलताओं को क्रम में सूचीबद्ध करके 'x (गैर-शून्य) पदों के साथ n की 'रचना (संख्या सिद्धांत)' की गणना करने के समान है। फ़ंक्शंस और बहु-समुच्चय्स के मध्य पत्राचार पिछले स्थिति की तरह ही है, और आच्छादन आवश्यकता का अर्थ है कि सभी गुणक कम से कम एक हैं। सभी गुणाओं को 1 से घटाकर, यह पिछले स्थिति में कम हो जाता है; चूँकि परिवर्तन से n का मान x से घट जाता है, परिणाम है | |||
यह | |||
:<math> \binom{n-1}{n-x}.</math> | :<math> \binom{n-1}{n-x}.</math> | ||
Line 261: | Line 257: | ||
:<math> \binom{n-1}{x-1},</math> | :<math> \binom{n-1}{x-1},</math> | ||
चरम | चरम स्थिति को छोड़कर {{math|1=''n'' = ''x'' = 0}}, जहां पूर्व अभिव्यक्ति के साथ सही ढंग से देता है <math>\tbinom{-1}0=1</math>, जबकि बाद वाला गलत देता है <math>\tbinom{-1}{-1}=0</math>. | ||
परिणाम का रूप विशेषण | परिणाम का रूप विशेषण फलनों के एक वर्ग को संबद्ध करने के तरीके की तलाश करने का सुझाव देता है {{math|''N'' → ''X''}} सीधे के एक उपसमुच्चय के लिए {{math|''n'' − ''x''}} कुल में से चुने गए तत्व {{math|''n'' − 1}}, जो निम्नानुसार किया जा सकता है। पहले समुच्चय N और X का कुल क्रम चुनें, और ध्यान दें कि N का उपयुक्त क्रमपरिवर्तन अनुप्रयुक्त करने से, प्रत्येक विशेषण फलन {{math|''N'' → ''X''}} को एक कमजोर रूप से बढ़ते (और निश्चित रूप से अभी भी विशेषण) फलन में परिवर्तित किया जा सकता है। यदि कोई N के तत्वों को क्रम से जोड़ता है {{math|''n'' − 1}} एक [[रेखीय ग्राफ]] में आर्क करता है, फिर किसी भी उपसमुच्चय को चुनता है {{math|''n'' − ''x''}} आर्क्स और बाकी को हटाकर, एक्स कनेक्टेड घटकों के साथ एक ग्राफ प्राप्त करता है, और इन्हें एक्स के क्रमिक तत्वों को भेजकर, एक कमजोर रूप से बढ़ते हुए विशेष कार्य को प्राप्त करता है {{math|''N'' → ''X''}}; कनेक्टेड घटकों के आकार भी x भागों में n की संरचना देते हैं। यह तर्क मूल रूप से सितारों और सलाखों (प्रायिकता) पर दिया गया है, सिवाय इसके कि वहाँ का पूरक विकल्प है {{math|''x'' − 1}} अलग किया जाता है। | ||
<ब्लॉककोट>उदाहरण: | <ब्लॉककोट>उदाहरण: | ||
Line 269: | Line 265: | ||
<math>\left\vert\{\{a, a, b\}, \{a, b, b\}\}\right\vert = \binom{3-1}{3-2} = \binom{2}{1} = \frac{2!}{1!\times (2-1)!} = 2</math></ब्लॉककोट> | <math>\left\vert\{\{a, a, b\}, \{a, b, b\}\}\right\vert = \binom{3-1}{3-2} = \binom{2}{1} = \frac{2!}{1!\times (2-1)!} = 2</math></ब्लॉककोट> | ||
===={{anchor|case ix}} एन से एक्स तक | ==== {{anchor|case ix}} एन से एक्स तक अंतःक्षेपक कार्य, एक्स के क्रमपरिवर्तन तक ==== | ||
इस स्थिति में हम X से अलग-अलग तत्वों के अनुक्रमों पर विचार करते हैं, परन्तु प्रत्येक तत्व पर X के क्रमचय को अनुप्रयुक्त करके एक दूसरे से प्राप्त की पहचान करते हैं। यह देखना आसान है कि ऐसे दो अलग-अलग अनुक्रम हमेशा पहचाने जा सकते हैं: क्रमचय को शब्द को मैप करना चाहिए पहले अनुक्रम के i से दूसरे क्रम के i तक, और चूंकि किसी भी क्रम में दो बार कोई मान नहीं होता है, इसलिए ये आवश्यकताएं एक दूसरे के विपरीत नहीं होती हैं; यह उन तत्वों को मानचित्रित करने के लिए बनी हुई है जो पहले क्रम में नहीं होते हैं, दूसरे क्रम में मनमाने तरीके से घटित नहीं होते हैं। एकमात्र तथ्य जो परिणाम को n और x पर पूर्णतया भी निर्भर करता है, वह यह है कि ऐसे किसी भी अनुक्रम के अस्तित्व की आवश्यकता होती है {{math|''n'' ≤ ''x''}}, कबूतर के सिद्धांत द्वारा। संख्या इसलिए व्यक्त की जाती है <math>[n\leq x]</math>, आइवरसन ब्रैकेट का उपयोग करना। | |||
==== {{anchor|case inx}} एन से एक्स तक अंतःक्षेपक कार्य, एन और एक्सके क्रमपरिवर्तन तक ==== | |||
यह स्थिति पिछले एक तक कम हो गया है: चूँकि X से अलग-अलग तत्वों के सभी अनुक्रमों को पहले से ही उनके प्रत्येक पद के लिए X के क्रमपरिवर्तन को अनुप्रयुक्त करके एक दूसरे में रूपांतरित किया जा सकता है, साथ ही प्रतिबन्धों को फिर से व्यवस्थित करने से कोई नई पहचान नहीं मिलती है; संख्या बनी हुई है <math>[n\leq x]</math>. | |||
===={{anchor|case | ==== {{anchor|case sx}} N से X तक विशेषण फलन, X के क्रमपरिवर्तन तक ==== | ||
यह स्थिति 'एन के एक समुच्चय के एक्स (गैर-खाली) उपसमुच्चय में विभाजन' की गणना करने के समान है, या पूर्णतया एक्स वर्गों के साथ एन पर समकक्ष संबंधों की गणना करने के समान है। दरअसल, किसी विशेषण कार्य के लिए {{math|''f'' : ''N'' → ''X''}}, f के अंतर्गत एक ही छवि होने का संबंध एक ऐसा तुल्यता संबंध है, और जब X का क्रमचय बाद में अनुप्रयुक्त किया जाता है तो यह नहीं बदलता है; इसके विपरीत कोई भी इस तरह के तुल्यता संबंध को x तुल्यता वर्गों में किसी तरह से X के तत्वों को असाइन करके एक विशेषण फलन में बदल सकता है। परिभाषा के अनुसार ऐसे विभाजनों या तुल्यता संबंधों की संख्या दूसरे प्रकार के S(n,x) की स्टर्लिंग संख्या है, जिसे लिखा भी गया है <math>\textstyle\{{n\atop x}\}</math>. इसके मान को एक पुनरावर्ती संबंध का उप[[योग]] करके या उत्पन्न करने वाले फलनों का उपयोग करके वर्णित किया जा सकता है, परन्तु द्विपद गुणांक के विपरीत इन संख्याओं के लिए कोई [[बंद सूत्र]] नहीं है जिसमें एक योग सम्मिलित नहीं है। | |||
==== {{anchor|case s}} एन से एक्स विशेषण कार्य करता है ==== | |||
प्रत्येक विशेषण समारोह के लिए {{math|''f'' : ''N'' → ''X''}}, X के क्रमचय के अंतर्गत इसकी कक्षा में x है! तत्व, चूंकि रचना (बाईं ओर) X के दो अलग-अलग क्रमपरिवर्तन के साथ कभी भी N पर एक ही फलन नहीं देता है (क्रमपरिवर्तन X के कुछ तत्वों पर भिन्न होना चाहिए, जिसे हमेशा कुछ i ∈ N के लिए f(i) के रूप में लिखा जा सकता है, और रचनाएँ तब i) पर भिन्न होंगी। यह इस प्रकार है कि इस स्थिति के लिए संख्या x है! पिछले स्थिति की संख्या का गुना, अर्थात <math>\textstyle x!\{{n\atop x}\}.</math> | |||
===={{anchor|case | |||
प्रत्येक विशेषण समारोह के लिए {{math|''f'' : ''N'' → ''X''}}, X के क्रमचय के अंतर्गत इसकी कक्षा में x है! तत्व, चूंकि रचना (बाईं ओर) X के दो अलग-अलग क्रमपरिवर्तन के साथ कभी भी N पर एक ही | |||
<ब्लॉककोट>उदाहरण: | <ब्लॉककोट>उदाहरण: | ||
<math>X = \{a, b\}, N = \{1, 2, 3\}\text{, then } </math> | <math>X = \{a, b\}, N = \{1, 2, 3\}\text{, then } </math> | ||
<math>\left\vert\{(a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a)\}\right\vert = 2!\left\{{3\atop 2}\right\} = 2 \times 3 = 6</math></ब्लॉककोट> | <math>\left\vert\{(a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a)\}\right\vert = 2!\left\{{3\atop 2}\right\} = 2 \times 3 = 6</math></ब्लॉककोट> | ||
===={{anchor|case fx}} N से X तक कार्य, X ==== | ==== {{anchor|case fx}} N से X तक कार्य, X के क्रमपरिवर्तन तक ==== | ||
यह स्थिति विशेषण फलनों के लिए #केस एसएक्स की तरह है, परन्तु एक्स के कुछ तत्व किसी भी समकक्ष वर्ग के अनुरूप नहीं हो सकते हैं (चूंकि कोई एक्स के क्रमपरिवर्तन तक फलनों को मानता है, इससे कोई फर्क नहीं पड़ता कि कौन से तत्व संबंधित हैं, बस कितने ). एक परिणाम के रूप में एन पर समानता संबंधों की गणना अधिकतम x वर्गों के साथ की जा रही है, और परिणाम x तक के मानों के योग द्वारा उल्लिखित स्थिति से प्राप्त किया जाता है, दे रहा है <math>\textstyle\sum_{k=0}^x \{{ n\atop k}\}</math>. स्थिति में x ≥ n, x का आकार कोई प्रतिबंध नहीं लगाता है, और कोई n तत्वों के समुच्चय पर सभी समतुल्य संबंधों की गणना कर रहा है (समान रूप से ऐसे समुच्चय के सभी विभाजन); इसलिए <math>\textstyle\sum_{k=0}^n \{{ n\atop k}\}</math> [[बेल नंबर|बेल संख्या]] बी के लिए बेल संख्या # योग सूत्र देता है<sub>''n''</sub>. | |||
यह | |||
===={{anchor|case | ==== {{anchor|case snx}} N से X तक विशेषण फलन, N और X के क्रमपरिवर्तन तक ==== | ||
यह स्थिति संख्या n के x गैर-शून्य भागों में 'विभाजन (संख्या सिद्धांत)' की गणना के समान है। गणना के स्थिति की तुलना में #केस एसएक्स केवल (<math>\textstyle \{{n \atop x}\}</math>), कोई केवल समतुल्यता वर्गों के आकार को बरकरार रखता है जो फलन N को विभाजित करता है (प्रत्येक आकार की बहुलता सहित), क्योंकि दो तुल्यता संबंधों को N के क्रमपरिवर्तन द्वारा एक दूसरे में रूपांतरित किया जा सकता है यदि और केवल यदि उनके वर्गों के आकार मिलान। यह ठीक वही है जो n के विभाजन की धारणा को N के विभाजन की धारणा से अलग करता है, इसलिए परिणामस्वरूप व्यक्ति को संख्या p की परिभाषा मिलती है<sub>''x''</sub>(एन) एन के एक्स गैर-शून्य भागों में विभाजन। | |||
यह | ==== {{anchor|case fnx}} N से X तक के कार्य, N और X के क्रमपरिवर्तन तक ==== | ||
यह स्थिति 'संख्या n के विभाजनों को ≤ x भागों' में गिनने के समान है। एसोसिएशन पिछले स्थिति के समान है, सिवाय इसके कि अब विभाजन के कुछ हिस्से 0 के समान हो सकते हैं। (विशेष रूप से, वे एक्स के तत्वों के अनुरूप हैं जो फलन की छवि में नहीं हैं।) एन के प्रत्येक विभाजन में अधिकतम x गैर-शून्य भागों को आवश्यक संख्या में शून्य जोड़कर इस तरह के विभाजन तक बढ़ाया जा सकता है, और यह सभी संभावनाओं के लिए एक बार खाता है, इसलिए परिणाम दिया जाता है <math>\textstyle\sum_{k=0}^x p_k(n)</math>. प्रत्येक x भाग में 1 जोड़ने पर, एक विभाजन प्राप्त होता है {{math|''n'' + ''x''}} x अशून्य भागों में, और यह पत्राचार विशेषण है; इसलिए दिए गए व्यंजक को इस रूप में लिखकर सरल किया जा सकता है <math>p_x(n+x)</math>. | |||
=== चरम | === चरम स्थिति === | ||
उपरोक्त सूत्र सभी परिमित समुच्चय N और X के लिए उचित मान देते हैं। कुछ | उपरोक्त सूत्र सभी परिमित समुच्चय N और X के लिए उचित मान देते हैं। कुछ स्थिति में ऐसे वैकल्पिक सूत्र हैं जो लगभग समतुल्य हैं, परन्तु कुछ चरम स्थिति में सही परिणाम नहीं देते हैं, जैसे कि जब N या X खाली होते हैं। निम्नलिखित विचार ऐसे स्थिति पर अनुप्रयुक्त होते हैं। | ||
* प्रत्येक | * प्रत्येक समुच्चय एक्स के लिए खाली समुच्चय से एक्स तक पूर्णतया एक फलन होता है (निर्दिष्ट करने के लिए इस फलन का कोई मान नहीं है), जो हमेशा अंतःक्षेपक होता है, परन्तु जब तक एक्स (भी) खाली नहीं होता है तब तक विशेषण नहीं होता है। | ||
* प्रत्येक गैर-खाली | * प्रत्येक गैर-खाली समुच्चय एन के लिए, एन से खाली समुच्चय तक कोई फलन नहीं है (फलन का कम से कम एक मान है जिसे निर्दिष्ट किया जाना चाहिए, परन्तु यह नहीं हो सकता)। | ||
* कब {{math|1=''n'' > ''x''}} कोई | * कब {{math|1=''n'' > ''x''}} कोई अंतःक्षेपक कार्य नहीं हैं {{math|''N'' → ''X''}}, और अगर {{math|1=''n'' < ''x''}} कोई विशेषण कार्य नहीं हैं {{math|''N'' → ''X''}}. | ||
* सूत्रों में प्रयुक्त भाव विशेष मान के रूप में होते हैं | * सूत्रों में प्रयुक्त भाव विशेष मान के रूप में होते हैं | ||
::<math>0^0=0^{\underline 0}=0!=\binom00=\binom{-1}0=\left\{{0\atop0}\right\}=p_0(0)=1</math> | ::<math>0^0=0^{\underline 0}=0!=\binom00=\binom{-1}0=\left\{{0\atop0}\right\}=p_0(0)=1</math> | ||
: (पहले तीन एक [[खाली उत्पाद]] के उदाहरण हैं, और value <math>\tbinom{-1}{0} = \tfrac{(-1)^{\underline{0}}}{0!} = 1</math> ऊपरी सूचकांक के मनमाने मूल्यों के लिए द्विपद गुणांक के पारंपरिक विस्तार द्वारा दिया जाता है), जबकि | : (पहले तीन एक [[खाली उत्पाद]] के उदाहरण हैं, और value <math>\tbinom{-1}{0} = \tfrac{(-1)^{\underline{0}}}{0!} = 1</math> ऊपरी सूचकांक के मनमाने मूल्यों के लिए द्विपद गुणांक के पारंपरिक विस्तार द्वारा दिया जाता है), जबकि | ||
::<math>\left\{{n\atop x}\right\}=p_x(n)=0 \quad\hbox{whenever either } n>0=x \hbox{ or }0\leq n<x.</math> | ::<math>\left\{{n\atop x}\right\}=p_x(n)=0 \quad\hbox{whenever either } n>0=x \hbox{ or }0\leq n<x.</math> | ||
विशेष रूप से एक्स से लिए गए एन तत्वों के साथ #केस एफएन के | विशेष रूप से एक्स से लिए गए एन तत्वों के साथ #केस एफएन के स्थिति में, दी गई अभिव्यक्ति <math>\tbinom{n+x-1}n</math> के समान है <math>\tbinom{n+x-1}{x-1}</math>, परन्तु बाद की अभिव्यक्ति स्थिति के लिए 0 देगी {{math|1=''n'' = ''x'' = 0}} (सामान्य परिपाटी के अनुसार ऋणात्मक निम्न सूचकांक वाले द्विपद गुणांक हमेशा 0 होते हैं)। इसी प्रकार, x गैर-शून्य भागों के साथ n के #केस एसएन के स्थिति में, दी गई अभिव्यक्ति <math>\tbinom{n-1}{n-x}</math> अभिव्यक्ति के लगभग समान है <math>\tbinom{n-1}{x-1}</math> सितारों और सलाखों (संभावना) तर्क द्वारा दिया गया है, परन्तु बाद वाला गलत मान देता है {{math|1=''n'' = 0}} और x के सभी मान। उन स्थिति के लिए जहां परिणाम में एक योग सम्मिलित होता है, अर्थात् #केस fx को अधिकतम x गैर-खाली उपसमुच्चय में या #केस fx को अधिकतम x गैर-शून्य भागों में गिनने के लिए, योग सूचकांक को 0 से प्रारंभ करने के लिए लिया जाता है; यद्यपि संगत पद शून्य होता है {{math|''n'' > 0}}, यह अद्वितीय गैर-शून्य शब्द है जब {{math|1=''n'' = 0}}, और परिणाम उन स्थिति के लिए गलत होगा यदि योग को 1 से प्रारंभ करने के लिए लिया गया था। | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
हम क्रमपरिवर्तन के अन्य [[समूह (गणित)]] को N और X पर कार्य करने की अनुमति देकर और सामान्य कर सकते हैं। यदि G, N के क्रमपरिवर्तनों का एक समूह है, और H, X के क्रमपरिवर्तनों का एक समूह है, तो हम | हम क्रमपरिवर्तन के अन्य [[समूह (गणित)]] को N और X पर कार्य करने की अनुमति देकर और सामान्य कर सकते हैं। यदि G, N के क्रमपरिवर्तनों का एक समूह है, और H, X के क्रमपरिवर्तनों का एक समूह है, तो हम फलनों के तुल्यता वर्गों की गणना करते हैं। <math>f \colon N \rightarrow X</math>. दो कार्य {{mvar|f}} और {{mvar|F}} को समतुल्य माना जाता है, और केवल अगर, उपस्थित है <math>g\in G, h \in H</math> ताकि <math> F = h \circ f \circ g </math>. यह विस्तार [[चक्रीय क्रमपरिवर्तन]] और [[डायहेड्रल समूह]] क्रमपरिवर्तन, साथ ही संख्याओं और समुच्चयों के चक्रीय और डायहेड्रल विभाजन जैसी धारणाओं की ओर जाता है। | ||
=== बीस गुना तरीका === | === बीस गुना तरीका === | ||
ट्वेंटीफोल्ड वे नामक एक अन्य सामान्यीकरण केनेथ पी. बोगार्ट द्वारा अपनी पुस्तक कॉम्बिनेटरिक्स थ्रू गाइडेड डिस्कवरी में विकसित किया गया था। वस्तुओं को | ट्वेंटीफोल्ड वे नामक एक अन्य सामान्यीकरण केनेथ पी. बोगार्ट द्वारा अपनी पुस्तक कॉम्बिनेटरिक्स थ्रू गाइडेड डिस्कवरी में विकसित किया गया था। वस्तुओं को संदूकों में वितरित करने की समस्या में वस्तुएँ और संदूकों दोनों समान या भिन्न हो सकते हैं। बोगार्ट 20 स्थिति की पहचान करता है।<ref>Kenneth P. Bogart (2004). [https://math.dartmouth.edu/news-resources/electronic/kpbogart/ ''Combinatorics Through Guided Discovery''], p.57</ref> | ||
{| class="wikitable" style="text-align:center;" border="1" | {| class="wikitable" style="text-align:center;" border="1" | ||
|+ | |+ बीस गुना तरीका; x प्राप्तकर्ताओं के बीच n वस्तुओं के वितरण के लिए मॉडल | ||
! rowspan="2" | № | ! rowspan="2" | № | ||
! rowspan="2" | Objects | ! rowspan="2" | Objects | ||
! rowspan="2" | | ! rowspan="2" | वितरण की | ||
स्थिति | |||
! colspan="2" | Recipients | ! colspan="2" | Recipients | ||
|- | |- | ||
! | ! विशिष्ट | ||
! | ! अभिन्न | ||
|- | |- | ||
! 1 | ! 1 | ||
! {{rh}} rowspan="4" | | ! {{rh}} rowspan="4" | विशिष्ट | ||
! {{rh}} | | ! {{rh}} | प्रतिबंध नहीं | ||
| [[#case f|''n''-sequence in ''X'']]<br>[[#Generalizations f|<math>x^n</math>]] | | [[#case f|''n''-sequence in ''X'']]<br>[[#Generalizations f|<math>x^n</math>]] | ||
| [[#case fx|partition of ''N'' into ≤ ''x'' | | [[#case fx|partition of ''N'' into ≤ ''x'' उपसमुच्चयs]]<br><math>\sum_{i=0}^x\left\{{n \atop i}\right\} </math> | ||
|- | |- | ||
! {{rh}} | 2 | ! {{rh}} | 2 | ||
! {{rh}} | | ! {{rh}} | अधिक से अधिक एक | ||
| [[#case i|''n''-permutation of ''X'']]<br>[[#Generalizations i|<math>x^{\underline n}</math>]] | | [[#case i|''n''-permutation of ''X'']]<br>[[#Generalizations i|<math>x^{\underline n}</math>]] | ||
| [[#Generalizations in|<math>\begin{cases}1 & \text{if } n \leq x \\ 0 & \text{otherwise}\end{cases}</math>]] | | [[#Generalizations in|<math>\begin{cases}1 & \text{if } n \leq x \\ 0 & \text{otherwise}\end{cases}</math>]] | ||
Line 344: | Line 334: | ||
|- | |- | ||
! {{rh}} | 3 | ! {{rh}} | 3 | ||
! {{rh}} | | ! {{rh}} | कम से कम एक | ||
|[[#case s|composition of ''N'' with ''x'' | |[[#case s|composition of ''N'' with ''x'' उपसमुच्चयs]]<br>[[#Generalizations fx|<math>x!\left\{{n \atop x}\right\}</math>]] | ||
|[[#case sx|partition of ''N'' into ''x'' | |[[#case sx|partition of ''N'' into ''x'' उपसमुच्चयs]]<br>[[#Generalizations ix|<math>\left\{{n \atop x}\right\}</math>]] | ||
|- | |- | ||
! {{rh}} | 4 | ! {{rh}} | 4 | ||
! {{rh}} | | ! {{rh}} | यथार्थत: एक | ||
|[[#Generalizations fx|<math>n! = x!</math>]]<br>permutations | |[[#Generalizations fx|<math>n! = x!</math>]]<br>permutations | ||
|<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math> | |<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math> | ||
Line 356: | Line 346: | ||
|- | |- | ||
! {{rh}} | 5 | ! {{rh}} | 5 | ||
! {{rh}} rowspan="2" | | ! {{rh}} rowspan="2" | विशिष्ट, <br/>ordered | ||
! {{rh}} | | ! {{rh}} | प्रतिबंध नहीं | ||
|[[#Generalizations fx|<math>x^{\overline n}</math>]]<br>ordered functions | |[[#Generalizations fx|<math>x^{\overline n}</math>]]<br>ordered functions | ||
|[[#Generalizations ix|<math>\sum_{i=1}^{x}L(n,i)</math>]]<br>broken permutations (<math>\leq x</math> parts)<br>Where <math>L(n,i)</math> is the [[Lah number]] | |[[#Generalizations ix|<math>\sum_{i=1}^{x}L(n,i)</math>]]<br>broken permutations (<math>\leq x</math> parts)<br>Where <math>L(n,i)</math> is the [[Lah number]] | ||
Line 363: | Line 353: | ||
|- | |- | ||
! {{rh}} | 6 | ! {{rh}} | 6 | ||
! {{rh}} | | ! {{rh}} | कम से कम एक | ||
|[[#Generalizations fx|<math>(n)^{\underline {x}}(n-1)^{\underline {n-x}}</math>]]<br>ordered onto functions | |[[#Generalizations fx|<math>(n)^{\underline {x}}(n-1)^{\underline {n-x}}</math>]]<br>ordered onto functions | ||
|[[#Generalizations ix|<math>L(n,x) = \left( {n \atop x} \right) (n-1)^{\underline{n-x}}</math>]]<br>broken permutations (''x'' parts)<br>Where <math>L(n,x)</math> is the [[Lah number]] | |[[#Generalizations ix|<math>L(n,x) = \left( {n \atop x} \right) (n-1)^{\underline{n-x}}</math>]]<br>broken permutations (''x'' parts)<br>Where <math>L(n,x)</math> is the [[Lah number]] | ||
Line 369: | Line 359: | ||
|- | |- | ||
! {{rh}} | 7 | ! {{rh}} | 7 | ||
! {{rh}} rowspan="4" | | ! {{rh}} rowspan="4" | अभिन्न | ||
! {{rh}} | | ! {{rh}} | प्रतिबंध नहीं | ||
|[[#case fn|''n''- | |[[#case fn|''n''-बहुउपसमुच्चय of ''X'']]<br>[[#Generalizations fx|<math>\left({x+n-1\atop n}\right)</math>]] | ||
|[[#Generalizations ix|<math>\sum_{i=1}^{x} p_{i}(n)</math>]]<br>number partitions (<math>\leq x</math> parts) | |[[#Generalizations ix|<math>\sum_{i=1}^{x} p_{i}(n)</math>]]<br>number partitions (<math>\leq x</math> parts) | ||
|- | |- | ||
! {{rh}} | 8 | ! {{rh}} | 8 | ||
! {{rh}} | | ! {{rh}} | अधिक से अधिक एक | ||
|[[#case in|''n''- | |[[#case in|''n''-उपसमुच्चय of ''X'']]<br>[[#Generalizations fx|<math>\left({x\atop n}\right)</math>]] | ||
|<math>\begin{cases}1 & \text{if } n \leq x \\ 0 & \text{otherwise}\end{cases}</math> | |<math>\begin{cases}1 & \text{if } n \leq x \\ 0 & \text{otherwise}\end{cases}</math> | ||
|- | |- | ||
! {{rh}} | 9 | ! {{rh}} | 9 | ||
! {{rh}} | | ! {{rh}} | कम से कम एक | ||
|[[#Generalizations fx|<math>\left({n-1\atop x-1}\right)</math>]]<br>compositions (''x'' parts) | |[[#Generalizations fx|<math>\left({n-1\atop x-1}\right)</math>]]<br>compositions (''x'' parts) | ||
|[[#case snx|partition of ''n'' into ''x'' parts]]<br>[[#Generalizations ix|<math>p_{x}(n)</math>]] | |[[#case snx|partition of ''n'' into ''x'' parts]]<br>[[#Generalizations ix|<math>p_{x}(n)</math>]] | ||
Line 388: | Line 378: | ||
|- | |- | ||
! {{rh}} | 10 | ! {{rh}} | 10 | ||
! {{rh}} | | ! {{rh}} | यथार्थत: एक | ||
|[[#Generalizations fnx|<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math>]] | |[[#Generalizations fnx|<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math>]] | ||
|<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math> | |<math>\begin{cases}1 & \text{if } n = x \\ 0 & \text{otherwise}\end{cases}</math> |
Revision as of 22:37, 29 May 2023
This article may be too technical for most readers to understand.मार्च 2019) (Learn how and when to remove this template message) ( |
साहचर्य में, बारह गुना तरीका दो परिमित समुच्चयों से संबंधित 12 संबंधित गणनात्मक समस्याओं का एक व्यवस्थित वर्गीकरण है, जिसमें गणना क्रमपरिवर्तन, संयोजन, multiset और विभाजन या तो एक समुच्चय या विभाजन (संख्या सिद्धांत) के विभाजन की शास्त्रीय समस्याएं सम्मिलित हैं। वर्गीकरण के विचार का श्रेय जियान-कार्लो रोटा को दिया जाता है, और नाम जोएल स्पेंसर द्वारा सुझाया गया था।[1]
संक्षिप्त विवरण
मान लीजिए कि N और X परिमित समुच्चय हो। मान लीजिए कि और समुच्चय की प्रमुखता हो। इस प्रकार N एक n-समुच्चय, और X एक x-तय करना।
हम जिस सामान्य समस्या पर विचार करते हैं, वह है फलन (गणित) के तुल्यता वर्गों की गणना। .
कार्य निम्नलिखित तीन प्रतिबंधों में से एक के अधीन हैं:
- कोई प्रतिबन्ध नहीं: प्रत्येक a में N द्वारा भेजा जा सकता है f किसी को b में X, और प्रत्येक b कई बार हो सकता है।
- f अंतःक्षेपक है: प्रत्येक मान के लिए a में N एक दूसरे से अलग होना चाहिए, और इसलिए प्रत्येक b में X की छवि (गणित) में अधिकतम एक बार हो सकता है f.
- f विशेषण है: प्रत्येक के लिए b में X कम से कम एक होना चाहिए a में N ऐसा है कि , इस प्रकार प्रत्येक b की छवि में कम से कम एक बार होगा f.
(स्थितिf is Bijection केवल एक विकल्प है जब ; परन्तु तब यह दोनों के समान हैf अंतःक्षेपक है औरf विशेषण है।)
चार अलग-अलग तुल्यता संबंध हैं जिन्हें फलनों के समुच्चय पर परिभाषित किया जा सकता है f से N को X:
फलनों पर तीन प्रतिबन्धों और चार समकक्ष संबंधों को जोड़ा जा सकता है 3 × 4 = 12 तौर तरीकों।
फलनों के समतुल्य वर्गों की गणना की बारह समस्याओं में समान कठिनाइयाँ सम्मिलित नहीं हैं, और उन्हें हल करने के लिए एक व्यवस्थित तरीका नहीं है। समस्याओं में से दो तुच्छ हैं (तुल्यता वर्गों की संख्या 0 या 1 है), पाँच समस्याओं का उत्तर n और x के गुणक सूत्र के संदर्भ में है, और शेष पाँच समस्याओं का उत्तर संयोजक फलनों (स्टर्लिंग संख्या) के संदर्भ में है और दिए गए भागों की संख्या के लिए विभाजन (संख्या सिद्धांत)।
इस समायोजन में शास्त्रीय गणना समस्याओं का समावेश इस प्रकार है।
- एक्स के एन-क्रमपरिवर्तन (अर्थात, आंशिक क्रमपरिवर्तन या पुनरावृत्ति के बिना अनुक्रम) की गणना #केस i|अंतःक्षेपक फलनों की गणना के समान है N → X.
- X के n-संयोजनों की गणना #case ininjective प्रफलनों की गणना करने के समान है N → X N के क्रमपरिवर्तन तक।
- समुच्चय X के क्रमपरिवर्तनों की गणना करना अंतःक्षेपी फलनों की गणना के समान है N → X जब n = x, और #case s|surjective फलनों की गणना करने के लिए भी N → X कब n = x.
- X में तत्वों के आकार n (जिसे पुनरावृत्ति के साथ n-संयोजन के रूप में भी जाना जाता है) के बहु-समुच्चय की गणना करना सभी #case fn|फ़ंक्शंस की गणना करने के समान है N → X N के क्रमपरिवर्तन तक।
- समुच्चय N के x उपसमुच्चय में विभाजनों की गणना करना सभी #केस sx | प्रक्षेप फलनों को गिनने के समान है N → X X के क्रमपरिवर्तन तक।
- संख्या n की x भागों में रचना (संख्या सिद्धांत) की गणना सभी #केस एसएन | प्रक्षेप फलनों की गणना के समान है N → X N के क्रमपरिवर्तन तक।
दृष्टिकोण
बारह प्रकार से विभिन्न समस्याओं पर विभिन्न दृष्टिकोणों से विचार किया जा सकता है।
गेंद और संदूक
पारम्परिक रूप से कई समस्याओं को बारह गुना तरीके से फलनों को परिभाषित करने के बजाय गेंदों को संदूकों (या कुछ इसी तरह के दृश्य) में रखने के संदर्भ में तैयार किया गया है। समुच्चय एन को गेंदों के समुच्चय के साथ पहचाना जा सकता है, और एक्स को संदूक के समुच्चय के साथ पहचाना जा सकता है; समारोह ƒ : N → X फिर गेंदों को बक्से में वितरित करने के तरीके का वर्णन करता है, अर्थात् प्रत्येक गेंद को संदूक ƒ(a) में डालकर। एक फलन अपने कार्यक्षेत्र में प्रत्येक मान के लिए एक अद्वितीय छवि प्रदान करता है; यह संपत्ति इस संपत्ति से परिलक्षित होती है कि कोई भी गेंद केवल एक संदूक में जा सकती है (इस आवश्यकता के साथ कि कोई भी गेंद संदूक के बाहर नहीं रहनी चाहिए), जबकि कोई भी संदूक गेंदों की मनमानी संख्या को समायोजित कर सकता है। इसके अतिरिक्त ƒ को अंतःक्षेपी होने की आवश्यकता का अर्थ है किसी एक संदूक में एक से अधिक गेंद डालने से मना करना, जबकि ƒ को आच्छादक होने की आवश्यकता का अर्थ है कि प्रत्येक संदूक में कम से कम एक गेंद हो।
N या X के तुल्यता संबंध क्रमपरिवर्तन की गणना गेंदों या संदूकों को क्रमशः, अप्रभेद्य कह कर परिलक्षित होती है। यह एक सटीक सूत्रीकरण है, जिसका उद्देश्य यह इंगित करना है कि अलग-अलग विन्यासों को अलग-अलग नहीं गिना जाना चाहिए, यदि गेंदों या संदूकों के कुछ आदान-प्रदान से एक को दूसरे में परिवर्तित किया जा सकता है। परिवर्तन की इस संभावना को क्रमपरिवर्तन द्वारा क्रिया द्वारा औपचारिक रूप दिया जाता है।
प्रतिदर्श
कुछ स्थिति के विषय में सोचने का दूसरा तरीका आंकड़ों में प्रतिदर्श (सांख्यिकी) के संदर्भ में है। एक्स वस्तु (या लोगों) की आबादी की कल्पना करें, जिनमें से हम एन चुनते हैं। दो अलग-अलग योजनाओं को सामान्य रूप से वर्णित किया जाता है, जिन्हें प्रतिस्थापन के साथ प्रतिदर्श और प्रतिस्थापन के बिना प्रतिदर्श के रूप में जाना जाता है। पूर्व स्थिति में (प्रतिस्थापन के साथ प्रतिदर्श), एक बार जब हम एक वस्तु चुन लेते हैं, तो हम इसे आबादी में वापस रख देते हैं, ताकि हम इसे फिर से चुन सकें। परिणाम यह है कि प्रत्येक विकल्प अन्य सभी विकल्पों की सांख्यिकीय स्वतंत्रता है, और प्रतिरूपो के समुच्चय को तकनीकी रूप से स्वतंत्र समान रूप से वितरित के रूप में संदर्भित किया जाता है। हालांकि, बाद वाले स्थिति में, एक बार जब हम एक वस्तु चुन लेते हैं, तो हम उसे एक तरफ रख देते हैं ताकि हम उसे फिर से न चुन सकें। इसका अर्थ है कि किसी वस्तु को चुनने की क्रिया का निम्नलिखित सभी विकल्पों पर प्रभाव पड़ता है (विशेष वस्तु को फिर से नहीं देखा जा सकता है), इसलिए हमारी पसंद एक दूसरे पर निर्भर हैं।
प्रतिदर्श योजनाओं के मध्य एक दूसरा अंतर यह है कि क्या आदेश देना महत्व रखता है। उदाहरण के लिए, यदि हमारे पास दस वस्तु हैं, जिनमें से हम दो चुनते हैं, तो विकल्प (4,7) अलग है (7,4) यदि क्रमण देना महत्व रखता है; दूसरी ओर, यदि आदेश देने से कोई फर्क नहीं पड़ता है, तो विकल्प (4,7) और (7,4) समतुल्य हैं। (इसके विषय में सोचने का एक और तरीका यह है कि प्रत्येक विकल्प को वस्तु संख्या से क्रमबद्ध करें, और परिणाम के किसी भी डुप्लीकेट को फेंक दें।)
नीचे दी गई तालिका की पहली दो पंक्तियाँ और स्तंभ क्रम पर विचार किए बिना और बिना प्रतिस्थापन के प्रतिरूप के अनुरूप हैं। प्रतिस्थापन के साथ प्रतिरूप के स्थिति किसी भी एफ लेबल वाले पंक्ति में पाए जाते हैं, जबकि बिना प्रतिस्थापन के प्रतिरूप के स्थिति अंतःक्षेपक एफ लेबल वाले पंक्ति में पाए जाते हैं। ऐसे स्थिति जहां क्रमण देने वाले स्थिति अलग लेबल वाली पंक्ति में पाए जाते हैं, और ऐसे स्थिति जहां क्रमण देने से कोई फर्क नहीं पड़ता, वे S लेबल वाली पंक्ति में पाए जाते हैंn कक्षाओं। प्रत्येक तालिका प्रविष्टि इंगित करती है कि किसी विशेष प्रतिदर्श योजना में विकल्पों के कितने अलग-अलग समुच्चय हैं। इन तालिका प्रविष्टियों में से तीन संभाव्यता वितरण के अनुरूप भी हैं। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमण महत्व रखता है, एन अलग-अलग यादृच्छिक चर के संयुक्त वितरण का वर्णन करने के लिए तुलनीय है, प्रत्येक एक्स-गुना श्रेणीबद्ध वितरण के साथ। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमण देना महत्व नहीं रखता है, हालांकि, एन के एकल बहुराष्ट्रीय वितरण का वर्णन करने के लिए एक एक्स-गुना श्रेणी से तुलना की जाती है, जहां प्रत्येक श्रेणी के केवल देखे गए संख्या महत्व रखते हैं। प्रतिस्थापन के बिना प्रतिदर्श जहां आदेश देना कोई महत्व नहीं रखता है, एक एकल बहुभिन्नरूपी हाइपरज्यामितीय वितरण के साथ तुलना करने योग्य है। प्रतिस्थापन के बिना प्रतिदर्श जहां आदेश महत्व रखता है वह संभाव्यता वितरण के अनुरूप नहीं लगता है।[2] ध्यान दें कि सभी अंतःक्षेपक स्थिति में (अर्थात प्रतिस्थापन के बिना प्रतिदर्श), विकल्पों के समुच्चय की संख्या शून्य है जब तक कि N ≤ X. (उपर्युक्त स्थिति में तुलनीय का अर्थ है कि संबंधित वितरण के प्रतिरूप स्थान का प्रत्येक तत्व विकल्पों के एक अलग समुच्चय से मेल खाता है, और इसलिए उपयुक्त संदूक में संख्या दिए गए वितरण के लिए प्रतिरूप स्थान के आकार को इंगित करती है।)
प्रतिदर्श के परिप्रेक्ष्य से, विशेषण f लेबल वाला पंक्ति कुछ असामान्य है: अनिवार्य रूप से, हम तब तक प्रतिस्थापन के साथ प्रतिरूप लेते रहते हैं जब तक कि हम प्रत्येक वस्तु को कम से कम एक बार नहीं चुन लेते। फिर, हम गिनते हैं कि हमने कितने चुनाव किए हैं, और यदि यह N के समान नहीं है, तो सम्पूर्ण समुच्चय को बाहर फेंक दें और दोहराएं। यह कूपन कलेक्टर की समस्या के लिए अस्पष्ट रूप से तुलनीय है, जहां प्रक्रिया में प्रत्येक कूपन को कम से कम एक बार देखे जाने तक एक्स कूपन का एक समुच्चय (प्रतिस्थापन के साथ प्रतिदर्श द्वारा) एकत्र करना सम्मिलित है। ध्यान दें कि सभी विशेषण स्थिति में, पसंद के समुच्चय की संख्या शून्य है जब तक कि N ≥ X.
लेबलन, चयन, समूहीकरण
एक समारोह ƒ : N → X को X या N के परिप्रेक्ष्य से माना जा सकता है। यह विभिन्न विचारों की ओर ले जाता है:
- फलन ƒ N के प्रत्येक तत्व को X के एक तत्व द्वारा लेबल करता है।
- फलन ƒ एन के प्रत्येक तत्व के लिए समुच्चय एक्स के एक तत्व (गणित) का चयन करता है (चुनता है), कुल एन विकल्प।
- फलन ƒ N के तत्वों को एक साथ समूहित करता है जिन्हें X के समान तत्व से मैप किया जाता है।
ये दृष्टिकोण सभी स्थिति के लिए समान रूप से अनुकूल नहीं हैं। लेबलन और चयन बिंदु एक्स के तत्वों के क्रमचय के साथ अच्छी तरह से संगत नहीं हैं, क्योंकि यह लेबल या चयन को बदलता है; दूसरी ओर समूहीकरण बिंदु विन्यास के विषय में सम्पूर्ण सूचना नहीं देता है जब तक कि एक्स के तत्वों को स्वतंत्र रूप से अनुमत नहीं किया जा सकता है। जब N को अनुमत नहीं किया जाता है, तो लेबलन और चयन बिंदु लगभग समतुल्य होते हैं, परन्तु जब यह होता है, तो चयन बिंदु अधिक अनुकूल होता है। तब चयन को एक अनियंत्रित चयन के रूप में देखा जा सकता है: X से n तत्वों के एक (बहु-) समुच्चय का एकल विकल्प बनाया जाता है।
लेबलन और पुनरावृत्ति के साथ या बिना चयन
जब ƒ को N के तत्वों की लेबलन के रूप में देखा जाता है, तो बाद वाले को एक क्रम में व्यवस्थित माना जा सकता है, और X से लेबल को क्रमिक रूप से उन्हें सौंपा जा सकता है। एक आवश्यकता जो ƒ अंतःक्षेपी होने का अर्थ है कि किसी भी लेबल का दूसरी बार उपयोग नहीं किया जा सकता है; नतीजा दोहराव के बिना लेबल का अनुक्रम है। ऐसी आवश्यकता के अभाव में, पुनरावृत्ति के साथ शब्दावली अनुक्रम का उपयोग किया जाता है, जिसका अर्थ है कि लेबल का एक से अधिक बार उपयोग किया जा सकता है (हालांकि पुनरावृत्ति के बिना होने वाले अनुक्रमों की भी अनुमति है)।
ƒ को X के तत्वों के एक अनियंत्रित चयन के रूप में देखते समय, उसी प्रकार का भेद अनुप्रयुक्त होता है। यदि ƒ अंतःक्षेपी होना चाहिए, तो चयन में X के विशिष्ट तत्व सम्मिलित होने चाहिए, इसलिए यह आकार n का X का एक उपसमुच्चय है, जिसे n-संयोजन भी कहा जाता है। आवश्यकता के बिना, एक्स का एक और एक ही तत्व चयन में कई बार हो सकता है, और परिणाम एक्स से तत्वों के आकार एन का एक बहु-समुच्चय होता है, जिसे एन-बहुसंयोजन या पुनरावृत्ति के साथ एन-संयोजन भी कहा जाता है।
एन के लेबलन तत्वों के दृष्टिकोण से ƒ विशेषण होने की आवश्यकता का अर्थ है कि प्रत्येक लेबल का कम से कम एक बार उपयोग किया जाना है; एक्स से चयन के दृष्टिकोण से, इसका अर्थ है कि एक्स के प्रत्येक तत्व को चयन में कम से कम एक बार सम्मिलित किया जाना चाहिए। प्रक्षेपण के साथ लेबलन एन के तत्वों के समूह के समान है जिसके बाद प्रत्येक समूह को एक्स के तत्व द्वारा लेबल किया जाता है, और तदनुसार गणितीय रूप से वर्णन करने के लिए कुछ अधिक जटिल है।
समुच्चय और संख्या का विभाजन
ƒ को N के तत्वों के समूह के रूप में देखते समय (जो मानता है कि X के क्रमपरिवर्तन के अंतर्गत पहचान की जाती है), ƒ को विशेषण के रूप में देखने का अर्थ है कि समूहों की संख्या निश्चित रूप से x होनी चाहिए। इस आवश्यकता के बिना समूहों की संख्या अधिकतम x हो सकती है। अंतःक्षेपी ƒ की आवश्यकता का अर्थ है कि N का प्रत्येक तत्व अपने आप में एक समूह होना चाहिए, जो अधिक से अधिक एक मान्य समूह छोड़ता है और इसलिए एक अरोचक गणना समस्या देता है।
इसके अतिरिक्त जब कोई N के क्रमचय के अंतर्गत पहचान करता है, तो इसका अर्थ समूहों को भूल जाना है परन्तु केवल उनके आकार को बनाए रखना है। इसके अतिरिक्त ये आकार किसी निश्चित क्रम में नहीं आते हैं, जबकि एक ही आकार एक से अधिक बार हो सकता है; कोई उन्हें संख्याओं की दुर्बलता से घटती सूची में व्यवस्थित करना चुन सकता है, जिसका योग संख्या n है। यह संख्या n के एक विभाजन (संख्या सिद्धांत) की संयोजी धारणा देता है, पूर्णतया x (आच्छादक ƒ के लिए) या अधिकतम x (यादृच्छिक ƒ के लिए) भागों में।
सूत्र
बारह गुना तरीके के विभिन्न स्थिति के सूत्र निम्नलिखित तालिका में संक्षेपित हैं; प्रत्येक तालिका प्रविष्टि सूत्र की व्याख्या करते हुए नीचे एक उपखंड से जुड़ती है।
f-class | Any f | Injective f | Surjective f | |
---|---|---|---|---|
विशिष्ट f |
n-sequence in X |
n-permutation of X |
composition of N with x उपसमुच्चय | |
Sn orbits f ∘ Sn |
X का n-बहुउपसमुच्चय |
n-उपसमुच्चय of X |
composition of n with x terms |
|
Sx orbits Sx ∘ f |
partition of N into ≤ x उपसमुच्चयs |
partition of N into ≤ x elements |
partition of N into x उपसमुच्चय |
|
Sn×Sx orbits Sx ∘ f ∘ Sn |
partition of n into ≤ x parts |
partition of n into ≤ x parts 1 |
partition of n into x parts |
उपयोग की जाने वाली विशेष संकेत पद्धति हैं:
- गिरती तथ्यात्मक शक्ति ,
- पोचममेर प्रतीक # वैकल्पिक अंकन ,
- तथ्यात्मक
- दूसरी तरह की स्टर्लिंग संख्या , n तत्वों के एक समुच्चय को k उपसमुच्चय में विभाजित करने के तरीकों की संख्या को दर्शाता है
- द्विपद गुणांक
- आइवरसन ब्रैकेट [] एक सत्य मान को 0 या 1 के रूप में विकोडन करता है
- जो संख्या n के k भागों में विभाजन (संख्या सिद्धांत) का
पंक्तियों और स्तंभों का सहज अर्थ
यह त्वरित सारांश है कि विभिन्न स्थिति का क्या अर्थ है। स्थिति का विवरण नीचे दिया गया है।
X क्रमांकित वस्तुओं (1 से x तक क्रमांकित) के एक समुच्चय के विषय में सोचें, जिसमें से हम n चुनते हैं, वस्तुओं की एक आदेशित सूची प्रदान करते हैं: उदा। अगर वहाँ जिन वस्तुओं को हम चुनते हैं परिणाम सूची (5, 2, 10) हो सकता है। फिर हम गिनते हैं कि ऐसी कितनी अलग-अलग सूचियाँ उपस्थित हैं, कभी-कभी पहले सूचियों को उन तरीकों से रूपांतरित करते हैं जो अलग-अलग संभावनाओं की संख्या को कम करते हैं।
तब स्तंभों का अर्थ है:
- कोई भी f
- किसी वस्तु को चयन करने के पश्चात, हम उसे वापस रख देते हैं, ताकि हम उसे फिर से चुन सकें।
- अंतःक्षेपक एफ
- एक वस्तु चयन करने के पश्चात, हम इसे अलग रख देते हैं, इसलिए हम इसे फिर से नहीं चुन सकते; इसलिए हम n विशिष्ट वस्तुओं के साथ समाप्त करेंगे। अनिवार्य रूप से, जब तक , कोई भी सूची पूर्णतया नहीं चुनी जा सकती।
- प्रक्षेप्य एफ
- एक वस्तु चयन करने के पश्चात, हम इसे वापस रख देते हैं, इसलिए हम इसे फिर से चुन सकते हैं - परन्तु अंत में, हमें प्रत्येक वस्तु को कम से कम एक बार चुनना होगा। अनिवार्य रूप से, जब तक , कोई भी सूची पूर्णतया नहीं चुनी जा सकती।
और पंक्तियों का अर्थ है:
- विशिष्ट
- सूचियों को अकेला छोड़ दें; उन्हें सीधे गिनें।
- एसn कक्षाएँ
- गिनने से पहले, चुने गए वस्तुों की वस्तु संख्या द्वारा सूचियों को क्रमबद्ध करें, ताकि क्रम कोई महत्व न रखे, जैसे, (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10)।
- एसx कक्षाएँ
- गिनने से पहले, देखी गई वस्तुओं को फिर से क्रमांकित करें ताकि पहली देखी गई वस्तु की संख्या 1, दूसरी 2, आदि हो। यदि किसी वस्तु को एक से अधिक बार देखा गया था, तो संख्याएँ दोहराई जा सकती हैं, जैसे, (3, 5, 3), (5, 2, 5), (4, 9, 4) → (1, 2, 1) जबकि (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2).
- एसn × एसx कक्षाएँ
- दो सूचियाँ समान मानी जाती हैं यदि यह दोनों को पुन: व्यवस्थित करना और उन्हें ऊपर के रूप में पुन: लेबल करना और समान परिणाम उत्पन्न करना संभव है। उदाहरण के लिए, (3, 5, 3) और (2, 9, 9) को समान माना जाता है क्योंकि उन्हें (3, 3, 5) और (9, 9, 2) के रूप में फिर से क्रमित किया जा सकता है और फिर दोनों को फिर से लेबल करने से समान उत्पादन होता है सूची (1, 1, 2)।
बॉल और संदूक परिदृश्य का उपयोग करके तालिका का सहज अर्थ
नीचे दिया गया तालिका उपरोक्त तालिका के समान है, परन्तु यह सूत्रों को दिखाने के बजाय परिचित गेंदों और बक्से के उदाहरण का उपयोग करके उनके अर्थ की सहज समझ देता है। पंक्तियाँ गेंदों और संदूकों की विशिष्टता का प्रतिनिधित्व करती हैं। यदि मल्टी-पैक (एक संदूक में एक से अधिक गेंद), या खाली संदूक की अनुमति है तो पंक्ति दर्शाते हैं। तालिका के कक्ष उस प्रश्न को दिखाते हैं जिसका उत्तर ऊपर दिए गए सूत्र तालिका में दिए गए सूत्र को हल करके दिया जाता है।
विभिन्न स्थिति का विवरण
नीचे दिए गए स्थिति को इस तरह से क्रमबद्ध किया गया है कि उन स्थिति को समूहित किया जा सके जिनके लिए गणना में उपयोग किए गए तर्क संबंधित हैं, जो दी गई तालिका में क्रम नहीं है।
==== N से X तक कार्य करता है
यह स्थिति बिना किसी प्रतिबंध के एक्स के 'एन तत्वों के अनुक्रम' की गणना के समान है: एक फलन f : N → X N के तत्वों की n छवियों द्वारा निर्धारित किया जाता है, जिनमें से प्रत्येक को x के तत्वों के मध्य स्वतंत्र रूप से चुना जा सकता है। यह कुल x देता हैn संभावनाएं।
<ब्लॉककोट>उदाहरण: </ब्लॉककोट>
==== एन से एक्स तक अंतःक्षेपक कार्य
यह स्थिति X के n अलग-अलग तत्वों के अनुक्रमों की गणना के समान है, जिसे X का 'एन-क्रमपरिवर्तन' या 'बिना दोहराव वाले अनुक्रम' भी कहा जाता है; फिर से यह क्रम N के तत्वों की n छवियों द्वारा बनता है। यह स्थिति अप्रतिबंधित अनुक्रमों में से एक से भिन्न होता है जिसमें दूसरे तत्व के लिए एक विकल्प कम होता है, तीसरे तत्व के लिए दो कम होते हैं, और इसी तरह। इसलिए x की एक सामान्य शक्ति के बजाय, मान x की गिरती हुई भाज्य शक्ति द्वारा दिया जाता है, जिसमें प्रत्येक क्रमिक कारक पिछले एक से एक कम होता है। सूत्र है
ध्यान दें कि अगर n > x तो कोई कारक शून्य प्राप्त करता है, इसलिए इस स्थिति में कोई अंतःक्षेपक कार्य नहीं है N → X बिलकुल; यह कबूतरखाने के सिद्धांत का सिर्फ एक पुनर्कथन है।
<ब्लॉककोट>उदाहरण: </ब्लॉककोट>
==== एन के क्रमपरिवर्तन तक, एन से एक्स तक अंतःक्षेपक कार्य
यह स्थिति X के 'उपसमुच्चयों के साथ n तत्वों' की गणना के समान है, जिसे X का n-संयोजन भी कहा जाता है: X के n विशिष्ट तत्वों के अनुक्रमों के मध्य, जो केवल उनके शब्दों के क्रम में भिन्न होते हैं, उन्हें N के क्रमपरिवर्तन द्वारा पहचाना जाता है। चूंकि सभी स्थिति में यह समूह पूर्णतया n! विभिन्न अनुक्रमों में, हम ऐसे अनुक्रमों की संख्या को n से विभाजित कर सकते हैं! एक्स के एन-संयोजनों की संख्या प्राप्त करने के लिए। इस संख्या को द्विपद गुणांक के रूप में जाना जाता है , जो इसलिए द्वारा दिया गया है
<ब्लॉककोट>उदाहरण: </ब्लॉककोट>
N से X तक के कार्य, N के क्रमपरिवर्तन तक
यह स्थिति X से 'बहु-समुच्चय्स विद एन एलिमेंट्स' की गणना के समान है (जिसे एन-मल्टीकोम्बिनेशन भी कहा जाता है)। इसका कारण यह है कि एक्स के प्रत्येक तत्व के लिए यह निर्धारित किया जाता है कि एन के कितने तत्वों को एफ द्वारा मैप किया जाता है, जबकि दो कार्य जो एक्स के प्रत्येक तत्व को समान गुण प्रदान करते हैं, हमेशा एन के क्रमपरिवर्तन द्वारा दूसरे में परिवर्तित हो सकते हैं। सूत्र सभी फलनों की गणना करता है N → X यहाँ उपयोगी नहीं है, क्योंकि N के क्रमपरिवर्तन द्वारा एक साथ समूहीकृत उनकी संख्या एक फलन से दूसरे फलन में भिन्न होती है। बल्कि, जैसा कि संयोजन#संख्या के संयोजनों की पुनरावृत्ति के अंतर्गत समझाया गया है, x तत्वों वाले एक समुच्चय से n-मल्टीकॉम्बिनेशन की संख्या को एक समुच्चय से n-संयोजनों की संख्या के समान देखा जा सकता है x + n − 1 तत्व। यह समस्या को #स्थिति में बारह गुना कम कर देता है, और परिणाम देता है
<ब्लॉककोट>उदाहरण: </ब्लॉककोट>
N के क्रमपरिवर्तन तक, N से X तक विशेषण कार्य करता है
यह स्थिति X से n तत्वों के साथ बहु-समुच्चय्स की गणना के समान है, जिसके लिए X का प्रत्येक तत्व कम से कम एक बार होता है। यह x के तत्वों की बहुलताओं को क्रम में सूचीबद्ध करके 'x (गैर-शून्य) पदों के साथ n की 'रचना (संख्या सिद्धांत)' की गणना करने के समान है। फ़ंक्शंस और बहु-समुच्चय्स के मध्य पत्राचार पिछले स्थिति की तरह ही है, और आच्छादन आवश्यकता का अर्थ है कि सभी गुणक कम से कम एक हैं। सभी गुणाओं को 1 से घटाकर, यह पिछले स्थिति में कम हो जाता है; चूँकि परिवर्तन से n का मान x से घट जाता है, परिणाम है
ध्यान दें कि जब n < x कोई विशेषण फलन नहीं होता है N → X बिल्कुल भी (खाली कबूतरखाने का एक प्रकार का सिद्धांत); इसे सूत्र में इस बात पर ध्यान दिया जाता है कि यदि निचला सूचकांक ऋणात्मक है तो द्विपद गुणांक हमेशा 0 होता है। वही मान व्यंजक द्वारा भी दिया जाता है
चरम स्थिति को छोड़कर n = x = 0, जहां पूर्व अभिव्यक्ति के साथ सही ढंग से देता है , जबकि बाद वाला गलत देता है .
परिणाम का रूप विशेषण फलनों के एक वर्ग को संबद्ध करने के तरीके की तलाश करने का सुझाव देता है N → X सीधे के एक उपसमुच्चय के लिए n − x कुल में से चुने गए तत्व n − 1, जो निम्नानुसार किया जा सकता है। पहले समुच्चय N और X का कुल क्रम चुनें, और ध्यान दें कि N का उपयुक्त क्रमपरिवर्तन अनुप्रयुक्त करने से, प्रत्येक विशेषण फलन N → X को एक कमजोर रूप से बढ़ते (और निश्चित रूप से अभी भी विशेषण) फलन में परिवर्तित किया जा सकता है। यदि कोई N के तत्वों को क्रम से जोड़ता है n − 1 एक रेखीय ग्राफ में आर्क करता है, फिर किसी भी उपसमुच्चय को चुनता है n − x आर्क्स और बाकी को हटाकर, एक्स कनेक्टेड घटकों के साथ एक ग्राफ प्राप्त करता है, और इन्हें एक्स के क्रमिक तत्वों को भेजकर, एक कमजोर रूप से बढ़ते हुए विशेष कार्य को प्राप्त करता है N → X; कनेक्टेड घटकों के आकार भी x भागों में n की संरचना देते हैं। यह तर्क मूल रूप से सितारों और सलाखों (प्रायिकता) पर दिया गया है, सिवाय इसके कि वहाँ का पूरक विकल्प है x − 1 अलग किया जाता है।
<ब्लॉककोट>उदाहरण: </ब्लॉककोट>
एन से एक्स तक अंतःक्षेपक कार्य, एक्स के क्रमपरिवर्तन तक
इस स्थिति में हम X से अलग-अलग तत्वों के अनुक्रमों पर विचार करते हैं, परन्तु प्रत्येक तत्व पर X के क्रमचय को अनुप्रयुक्त करके एक दूसरे से प्राप्त की पहचान करते हैं। यह देखना आसान है कि ऐसे दो अलग-अलग अनुक्रम हमेशा पहचाने जा सकते हैं: क्रमचय को शब्द को मैप करना चाहिए पहले अनुक्रम के i से दूसरे क्रम के i तक, और चूंकि किसी भी क्रम में दो बार कोई मान नहीं होता है, इसलिए ये आवश्यकताएं एक दूसरे के विपरीत नहीं होती हैं; यह उन तत्वों को मानचित्रित करने के लिए बनी हुई है जो पहले क्रम में नहीं होते हैं, दूसरे क्रम में मनमाने तरीके से घटित नहीं होते हैं। एकमात्र तथ्य जो परिणाम को n और x पर पूर्णतया भी निर्भर करता है, वह यह है कि ऐसे किसी भी अनुक्रम के अस्तित्व की आवश्यकता होती है n ≤ x, कबूतर के सिद्धांत द्वारा। संख्या इसलिए व्यक्त की जाती है , आइवरसन ब्रैकेट का उपयोग करना।
एन से एक्स तक अंतःक्षेपक कार्य, एन और एक्सके क्रमपरिवर्तन तक
यह स्थिति पिछले एक तक कम हो गया है: चूँकि X से अलग-अलग तत्वों के सभी अनुक्रमों को पहले से ही उनके प्रत्येक पद के लिए X के क्रमपरिवर्तन को अनुप्रयुक्त करके एक दूसरे में रूपांतरित किया जा सकता है, साथ ही प्रतिबन्धों को फिर से व्यवस्थित करने से कोई नई पहचान नहीं मिलती है; संख्या बनी हुई है .
N से X तक विशेषण फलन, X के क्रमपरिवर्तन तक
यह स्थिति 'एन के एक समुच्चय के एक्स (गैर-खाली) उपसमुच्चय में विभाजन' की गणना करने के समान है, या पूर्णतया एक्स वर्गों के साथ एन पर समकक्ष संबंधों की गणना करने के समान है। दरअसल, किसी विशेषण कार्य के लिए f : N → X, f के अंतर्गत एक ही छवि होने का संबंध एक ऐसा तुल्यता संबंध है, और जब X का क्रमचय बाद में अनुप्रयुक्त किया जाता है तो यह नहीं बदलता है; इसके विपरीत कोई भी इस तरह के तुल्यता संबंध को x तुल्यता वर्गों में किसी तरह से X के तत्वों को असाइन करके एक विशेषण फलन में बदल सकता है। परिभाषा के अनुसार ऐसे विभाजनों या तुल्यता संबंधों की संख्या दूसरे प्रकार के S(n,x) की स्टर्लिंग संख्या है, जिसे लिखा भी गया है . इसके मान को एक पुनरावर्ती संबंध का उपयोग करके या उत्पन्न करने वाले फलनों का उपयोग करके वर्णित किया जा सकता है, परन्तु द्विपद गुणांक के विपरीत इन संख्याओं के लिए कोई बंद सूत्र नहीं है जिसमें एक योग सम्मिलित नहीं है।
एन से एक्स विशेषण कार्य करता है
प्रत्येक विशेषण समारोह के लिए f : N → X, X के क्रमचय के अंतर्गत इसकी कक्षा में x है! तत्व, चूंकि रचना (बाईं ओर) X के दो अलग-अलग क्रमपरिवर्तन के साथ कभी भी N पर एक ही फलन नहीं देता है (क्रमपरिवर्तन X के कुछ तत्वों पर भिन्न होना चाहिए, जिसे हमेशा कुछ i ∈ N के लिए f(i) के रूप में लिखा जा सकता है, और रचनाएँ तब i) पर भिन्न होंगी। यह इस प्रकार है कि इस स्थिति के लिए संख्या x है! पिछले स्थिति की संख्या का गुना, अर्थात <ब्लॉककोट>उदाहरण: </ब्लॉककोट>
N से X तक कार्य, X के क्रमपरिवर्तन तक
यह स्थिति विशेषण फलनों के लिए #केस एसएक्स की तरह है, परन्तु एक्स के कुछ तत्व किसी भी समकक्ष वर्ग के अनुरूप नहीं हो सकते हैं (चूंकि कोई एक्स के क्रमपरिवर्तन तक फलनों को मानता है, इससे कोई फर्क नहीं पड़ता कि कौन से तत्व संबंधित हैं, बस कितने ). एक परिणाम के रूप में एन पर समानता संबंधों की गणना अधिकतम x वर्गों के साथ की जा रही है, और परिणाम x तक के मानों के योग द्वारा उल्लिखित स्थिति से प्राप्त किया जाता है, दे रहा है . स्थिति में x ≥ n, x का आकार कोई प्रतिबंध नहीं लगाता है, और कोई n तत्वों के समुच्चय पर सभी समतुल्य संबंधों की गणना कर रहा है (समान रूप से ऐसे समुच्चय के सभी विभाजन); इसलिए बेल संख्या बी के लिए बेल संख्या # योग सूत्र देता हैn.
N से X तक विशेषण फलन, N और X के क्रमपरिवर्तन तक
यह स्थिति संख्या n के x गैर-शून्य भागों में 'विभाजन (संख्या सिद्धांत)' की गणना के समान है। गणना के स्थिति की तुलना में #केस एसएक्स केवल (), कोई केवल समतुल्यता वर्गों के आकार को बरकरार रखता है जो फलन N को विभाजित करता है (प्रत्येक आकार की बहुलता सहित), क्योंकि दो तुल्यता संबंधों को N के क्रमपरिवर्तन द्वारा एक दूसरे में रूपांतरित किया जा सकता है यदि और केवल यदि उनके वर्गों के आकार मिलान। यह ठीक वही है जो n के विभाजन की धारणा को N के विभाजन की धारणा से अलग करता है, इसलिए परिणामस्वरूप व्यक्ति को संख्या p की परिभाषा मिलती हैx(एन) एन के एक्स गैर-शून्य भागों में विभाजन।
N से X तक के कार्य, N और X के क्रमपरिवर्तन तक
यह स्थिति 'संख्या n के विभाजनों को ≤ x भागों' में गिनने के समान है। एसोसिएशन पिछले स्थिति के समान है, सिवाय इसके कि अब विभाजन के कुछ हिस्से 0 के समान हो सकते हैं। (विशेष रूप से, वे एक्स के तत्वों के अनुरूप हैं जो फलन की छवि में नहीं हैं।) एन के प्रत्येक विभाजन में अधिकतम x गैर-शून्य भागों को आवश्यक संख्या में शून्य जोड़कर इस तरह के विभाजन तक बढ़ाया जा सकता है, और यह सभी संभावनाओं के लिए एक बार खाता है, इसलिए परिणाम दिया जाता है . प्रत्येक x भाग में 1 जोड़ने पर, एक विभाजन प्राप्त होता है n + x x अशून्य भागों में, और यह पत्राचार विशेषण है; इसलिए दिए गए व्यंजक को इस रूप में लिखकर सरल किया जा सकता है .
चरम स्थिति
उपरोक्त सूत्र सभी परिमित समुच्चय N और X के लिए उचित मान देते हैं। कुछ स्थिति में ऐसे वैकल्पिक सूत्र हैं जो लगभग समतुल्य हैं, परन्तु कुछ चरम स्थिति में सही परिणाम नहीं देते हैं, जैसे कि जब N या X खाली होते हैं। निम्नलिखित विचार ऐसे स्थिति पर अनुप्रयुक्त होते हैं।
- प्रत्येक समुच्चय एक्स के लिए खाली समुच्चय से एक्स तक पूर्णतया एक फलन होता है (निर्दिष्ट करने के लिए इस फलन का कोई मान नहीं है), जो हमेशा अंतःक्षेपक होता है, परन्तु जब तक एक्स (भी) खाली नहीं होता है तब तक विशेषण नहीं होता है।
- प्रत्येक गैर-खाली समुच्चय एन के लिए, एन से खाली समुच्चय तक कोई फलन नहीं है (फलन का कम से कम एक मान है जिसे निर्दिष्ट किया जाना चाहिए, परन्तु यह नहीं हो सकता)।
- कब n > x कोई अंतःक्षेपक कार्य नहीं हैं N → X, और अगर n < x कोई विशेषण कार्य नहीं हैं N → X.
- सूत्रों में प्रयुक्त भाव विशेष मान के रूप में होते हैं
- (पहले तीन एक खाली उत्पाद के उदाहरण हैं, और value ऊपरी सूचकांक के मनमाने मूल्यों के लिए द्विपद गुणांक के पारंपरिक विस्तार द्वारा दिया जाता है), जबकि
विशेष रूप से एक्स से लिए गए एन तत्वों के साथ #केस एफएन के स्थिति में, दी गई अभिव्यक्ति के समान है , परन्तु बाद की अभिव्यक्ति स्थिति के लिए 0 देगी n = x = 0 (सामान्य परिपाटी के अनुसार ऋणात्मक निम्न सूचकांक वाले द्विपद गुणांक हमेशा 0 होते हैं)। इसी प्रकार, x गैर-शून्य भागों के साथ n के #केस एसएन के स्थिति में, दी गई अभिव्यक्ति अभिव्यक्ति के लगभग समान है सितारों और सलाखों (संभावना) तर्क द्वारा दिया गया है, परन्तु बाद वाला गलत मान देता है n = 0 और x के सभी मान। उन स्थिति के लिए जहां परिणाम में एक योग सम्मिलित होता है, अर्थात् #केस fx को अधिकतम x गैर-खाली उपसमुच्चय में या #केस fx को अधिकतम x गैर-शून्य भागों में गिनने के लिए, योग सूचकांक को 0 से प्रारंभ करने के लिए लिया जाता है; यद्यपि संगत पद शून्य होता है n > 0, यह अद्वितीय गैर-शून्य शब्द है जब n = 0, और परिणाम उन स्थिति के लिए गलत होगा यदि योग को 1 से प्रारंभ करने के लिए लिया गया था।
सामान्यीकरण
हम क्रमपरिवर्तन के अन्य समूह (गणित) को N और X पर कार्य करने की अनुमति देकर और सामान्य कर सकते हैं। यदि G, N के क्रमपरिवर्तनों का एक समूह है, और H, X के क्रमपरिवर्तनों का एक समूह है, तो हम फलनों के तुल्यता वर्गों की गणना करते हैं। . दो कार्य f और F को समतुल्य माना जाता है, और केवल अगर, उपस्थित है ताकि . यह विस्तार चक्रीय क्रमपरिवर्तन और डायहेड्रल समूह क्रमपरिवर्तन, साथ ही संख्याओं और समुच्चयों के चक्रीय और डायहेड्रल विभाजन जैसी धारणाओं की ओर जाता है।
बीस गुना तरीका
ट्वेंटीफोल्ड वे नामक एक अन्य सामान्यीकरण केनेथ पी. बोगार्ट द्वारा अपनी पुस्तक कॉम्बिनेटरिक्स थ्रू गाइडेड डिस्कवरी में विकसित किया गया था। वस्तुओं को संदूकों में वितरित करने की समस्या में वस्तुएँ और संदूकों दोनों समान या भिन्न हो सकते हैं। बोगार्ट 20 स्थिति की पहचान करता है।[3]
№ | Objects | वितरण की
स्थिति |
Recipients | |
---|---|---|---|---|
विशिष्ट | अभिन्न | |||
1 | विशिष्ट | प्रतिबंध नहीं | n-sequence in X |
partition of N into ≤ x उपसमुच्चयs |
2 | अधिक से अधिक एक | n-permutation of X |
||
3 | कम से कम एक | composition of N with x उपसमुच्चयs |
partition of N into x उपसमुच्चयs | |
4 | यथार्थत: एक | permutations |
||
5 | विशिष्ट, ordered |
प्रतिबंध नहीं | ordered functions |
broken permutations ( parts) Where is the Lah number |
6 | कम से कम एक | ordered onto functions |
broken permutations (x parts) Where is the Lah number | |
7 | अभिन्न | प्रतिबंध नहीं | n-बहुउपसमुच्चय of X |
number partitions ( parts) |
8 | अधिक से अधिक एक | n-उपसमुच्चय of X |
||
9 | कम से कम एक | compositions (x parts) |
partition of n into x parts | |
10 | यथार्थत: एक |
यह भी देखें
संदर्भ
- ↑ Richard P. Stanley (1997). Enumerative Combinatorics, Volume I. Cambridge University Press. ISBN 0-521-66351-2. p.41
- ↑ Robert V. Hogg and Elliot A. Tanis (2001). Probability and Statistical Inference. Prentice-Hall, Inc. ISBN 0-13-027294-9. p.81
- ↑ Kenneth P. Bogart (2004). Combinatorics Through Guided Discovery, p.57