बारह गुना शैली (ट्वेल्व फोल्ड वे): Difference between revisions

From Vigyanwiki
No edit summary
 
(One intermediate revision by one other user not shown)
Line 379: Line 379:
== संदर्भ ==
== संदर्भ ==
<references/>
<references/>
[[Category: साहचर्य]] [[Category: क्रमपरिवर्तन]]


 
[[Category:All articles that are too technical]]
 
[[Category:Articles with invalid date parameter in template]]
[[Category: Machine Translated Page]]
[[Category:Created On 26/05/2023]]
[[Category:Created On 26/05/2023]]
[[Category:Vigyan Ready]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia articles that are too technical from मार्च 2019]]
[[Category:क्रमपरिवर्तन]]
[[Category:साहचर्य]]

Latest revision as of 09:23, 15 June 2023

साहचर्य में, बारह गुना शैली दो परिमित समुच्चयों से संबंधित 12 संबंधित गणनात्मक समस्याओं का एक व्यवस्थित वर्गीकरण है, जिसमें गणना क्रमचय, संयोजन, बहु-समुच्चय और विभाजन या तो एक समुच्चय या संख्या की शास्त्रीय समस्याएं सम्मिलित हैं। वर्गीकरण के विचार का श्रेय जियान-कार्लो रोटा को दिया जाता है और नाम जोएल स्पेंसर द्वारा सुझाया गया था।[1]


संक्षिप्त विवरण

मान लीजिए कि N और X परिमित समुच्चय हैं और और समुच्चय की प्रमुखता हैं। इस प्रकार N एक n-समुच्चय और X एक x-समुच्चय हैं।

हम जिस सामान्य समस्या पर विचार कर रहे हैं वह फलनों के तुल्यता वर्गों की गणना है।

फलन निम्नलिखित तीन प्रतिबंधों में से एक के अधीन हैं:

  1. कोई प्रतिबन्ध नहीं: N में प्रत्येक a को f द्वारा X में किसी भी b को भेजा जा सकता है, और प्रत्येक b कई बार हो सकता है।
  2. f अंतःक्षेपी है: प्रत्येक मान N में a के लिए में प्रत्येक दूसरे से अलग होना चाहिए और इसलिए X में प्रत्येक b, f छवि में अधिकतम एक बार हो सकता है।
  3. f प्रक्षेप्य है: X में प्रत्येक b के लिए N में कम-से-कम एक a ऐसा होना चाहिए कि , इस प्रकार प्रत्येक b कम-से-कम एक बार f की छवि में होगा।

(स्थिति "f द्विभाजित है" केवल एक विकल्प है जब है; परन्तु तब यह " f अंतःक्षेपी है" और "f प्रक्षेप्य है" दोनों के समान है)।

चार अलग-अलग तुल्यता संबंध हैं जिन्हे N से X तक के फलनों f के समुच्चय पर परिभाषित किया जा सकता है:

  1. समानता;
  2. N के क्रमचय तक समानता;
  3. X के क्रमचय तक समानता;
  4. N और X के क्रमचय तक समानता।

फलनों पर तीन प्रतिबन्धों और चार तुल्यता संबंधों को 3 × 4 = 12 तरीकों से जोड़ा जा सकता है।

फलनों के समतुल्य वर्गों की गणना की बारह समस्याओं में समान कठिनाइयाँ सम्मिलित नहीं हैं और उन्हें हल करने के लिए एक व्यवस्थित शैली नहीं है। समस्याओं में से दो तुच्छ हैं (तुल्यता वर्गों की संख्या 0 या 1 है), पाँच समस्याओं का उत्तर n और x के गुणक सूत्र के संदर्भ में है और शेष पाँच समस्याओं का उत्तर संयोजक फलन (स्टर्लिंग संख्याओं के संदर्भ में है और दिए गए भागों की संख्या के लिए विभाजन फलन) है।

इस समायोजन में शास्त्रीय गणना समस्याओं का समावेश इस प्रकार है।

  • X के n-क्रमचय (अर्थात, आंशिक क्रमचय या पुनरावृत्ति के बिना अनुक्रम) की गणना अंतःक्षेपी फलनों NX की गणना के समान है।
  • X के n-संयोजनों की गणना N के क्रमचय तक अंतःक्षेपी फलनों NX की गणना करने के समान है।
  • समुच्चय X के क्रमचयों की गणना अंतःक्षेपी फलनों NX की गणना के समान है जब n = x, और प्रक्षेप्य फलनों NX की गणना करने के लिए भी जब n = x है।
  • X में तत्वों के आकार n (जिसे पुनरावृत्ति के साथ n-संयोजन के रूप में भी जाना जाता है) के बहु-समुच्चयों की गणना N के क्रमचय तक सभी फलनों NX की गणना के समान है।
  • समुच्चय N के x उपसमुच्चयों में विभाजन की गणना करना, सभी प्रक्षेप्य फलनों NX को X के क्रमचय तक गणना के समान है।
  • संख्या n रचना को x भागों में गणना करना N के क्रमचय तक सभी प्रक्षेप्य फलनों NX की गणना के समान है।

दृष्टिकोण

बारह प्रकार से विभिन्न समस्याओं पर विभिन्न दृष्टिकोणों से विचार किया जा सकता है।

गेंद और संदूक

पारम्परिक रूप से कई समस्याओं को बारह प्रकार से फलनों को परिभाषित करने के बजाय गेंदों को संदूकों (या कुछ इसी तरह के दृश्य) में रखने के संदर्भ में तैयार किया गया है। समुच्चय N को गेंदों के समुच्चयों के साथ पहचाना जा सकता है और X को संदूकों के समुच्चयों के साथ पहचाना जा सकता है; फलन ƒ : NX तब गेंदों को संदूकों में, अर्थात् प्रत्येक गेंद को संदूक ƒ(a) में डालकर वितरित करने के तरीके का वर्णन करता है। एक फलन अपने कार्यक्षेत्र में प्रत्येक मान के लिए एक अद्वितीय छवि प्रदान करता है; यह गुणधर्म इस गुणधर्म से परिलक्षित होती है कि कोई भी गेंद केवल एक संदूक में जा सकती है (इस आवश्यकता के साथ कि कोई भी गेंद संदूक के बाहर नहीं रहनी चाहिए), जबकि कोई भी संदूक गेंदों की यादृच्छिक संख्या को समायोजित कर सकता है। इसके अतिरिक्त ƒ को अंतःक्षेपी होने की आवश्यकता का अर्थ है किसी एक संदूक में एक से अधिक गेंद डालने से मना करना, जबकि ƒ को आच्छादक होने की आवश्यकता का अर्थ है कि प्रत्येक संदूक में कम-से-कम एक गेंद हो।

N या ​​X के तुल्यता संबंध क्रमचय की गणना गेंदों या संदूकों को क्रमशः, "अप्रभेद्य" कह कर परिलक्षित होती है। यह एक सटीक सूत्रीकरण है, जिसका उद्देश्य यह इंगित करना है कि अलग-अलग विन्यासों को अलग-अलग नहीं गिना जाना चाहिए, यदि गेंदों या संदूकों के कुछ आदान-प्रदान से एक को दूसरे में परिवर्तित किया जा सकता है। परिवर्तन की इस संभावना को क्रमचय क्रिया द्वारा औपचारिक रूप दिया जाता है।

प्रतिदर्श

कुछ स्थितियों के विषय में विचार करने का दूसरा तरीका आंकड़ों में प्रतिदर्श के संदर्भ में है। X वस्तु (या लोगों) की समष्टि की कल्पना करें, जिनमें से हम N चुनते हैं। दो अलग-अलग योजनाओं को सामान्य रूप से वर्णित किया जाता है, जिन्हें प्रतिस्थापन के साथ प्रतिदर्श और प्रतिस्थापन के बिना प्रतिदर्श के रूप में जाना जाता है। पूर्व स्थिति में (प्रतिस्थापन के साथ प्रतिदर्श), एक बार जब हम एक वस्तु चुन लेते हैं, तो हम इसे समष्टि में वापस रख देते हैं, ताकि हम इसे फिर से चुन सकें। परिणाम यह है कि प्रत्येक विकल्प अन्य सभी विकल्पों से स्वतंत्र है और प्रतिरूपो के समुच्चय को तकनीकी रूप से स्वतंत्र समान रूप से वितरित के रूप में संदर्भित किया जाता है। हालांकि, बाद वाली स्थिति में, एक बार जब हम एक वस्तु चुन लेते हैं, तो हम उसे एक ओर रख देते हैं ताकि हम उसे फिर से न चुन सकें। इसका अर्थ है कि किसी वस्तु को चुनने की क्रिया का निम्नलिखित सभी विकल्पों पर प्रभाव पड़ता है (विशेष वस्तु को फिर से नहीं देखा जा सकता है), इसलिए हमारी पसंद एक दूसरे पर निर्भर हैं।

प्रतिदर्श योजनाओं के मध्य एक दूसरा अंतर यह है कि क्या क्रमीकरण महत्व रखता है। उदाहरण के लिए, यदि हमारे पास दस वस्तु हैं, जिनमें से हम दो चुनते हैं, तो विकल्प (4,7) भिन्न है (7,4) यदि क्रमीकरण महत्व रखता है; दूसरी ओर, यदि क्रमीकरण से कोई असमानता नहीं होती है, तो विकल्प (4,7) और (7,4) समतुल्य हैं (इसके विषय में विचार करने का एक और तरीका यह है कि प्रत्येक विकल्प को वस्तु संख्या से क्रमबद्ध करें और परिणाम के किसी भी अनुकृति को फेंक दें)।

नीचे दी गई तालिका की पहली दो पंक्तियाँ और स्तंभ क्रम पर विचार किए बिना और बिना प्रतिस्थापन के प्रतिरूप के अनुरूप हैं। प्रतिस्थापन के साथ प्रतिरूप की स्थिति "किसी भी f" लेबल वाले स्तंभ में पाए जाते हैं, जबकि बिना प्रतिस्थापन के प्रतिरूप की स्थिति "अंतःक्षेपी f" लेबल वाले स्तंभ में पाए जाते हैं। ऐसी स्थिति जहां क्रमीकरण वाली स्थिति "भिन्न" लेबल वाली स्तंभ में पाए जाते हैं और ऐसी स्थिति जहां क्रमीकरण से कोई असमानता नहीं होती है, वे "Sn कक्षाएं" लेबल वाली स्तंभ में पाए जाते हैं। प्रत्येक तालिका प्रविष्टि इंगित करती है कि किसी विशेष प्रतिदर्श योजना में विकल्पों के कितने अलग-अलग समुच्चय हैं। इन तालिका प्रविष्टियों में से तीन संभाव्यता वितरण के अनुरूप भी हैं। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमण महत्व रखता है, N अलग-अलग यादृच्छिक चर के संयुक्त वितरण का वर्णन करने के लिए प्रत्येक X-गुना श्रेणीबद्ध वितरण के साथ तुलनीय है। प्रतिस्थापन के साथ प्रतिदर्श जहां क्रमीकरण महत्व नहीं रखता है, हालांकि, N के एकल बहुराष्ट्रीय वितरण का वर्णन करने के लिए एक X-गुना श्रेणी से तुलना की जाती है, जहां प्रत्येक श्रेणी की केवल देखी गयी संख्या महत्व रखती हैं। प्रतिस्थापन के बिना प्रतिदर्श जहां क्रमीकरण कोई महत्व नहीं रखता है, एक एकल बहुभिन्नरूपी हाइपरज्यामितीय वितरण के साथ तुलना करने योग्य है। प्रतिस्थापन के बिना प्रतिदर्श जहां क्रमीकरण महत्व रखता है वह संभाव्यता वितरण के अनुरूप नहीं लगता है।[2] ध्यान दें कि सभी "अंतःक्षेपी" स्थितियों में (अर्थात, प्रतिस्थापन के बिना प्रतिदर्श), विकल्पों के समुच्चयों की संख्या शून्य है जब तक कि NX है (उपर्युक्त स्थिति में तुलनीय का अर्थ है कि संबंधित वितरण के प्रतिरूप स्थान का प्रत्येक तत्व विकल्पों के एक अलग समुच्चय से मेल खाता है और इसलिए उपयुक्त संदूक में संख्या दिए गए वितरण के लिए प्रतिरूप स्थान के आकार को इंगित करती है)।

प्रतिदर्श के परिप्रेक्ष्य से, "परिप्रेक्ष्य f" लेबल वाला स्तंभ कुछ असामान्य है: अनिवार्य रूप से, हम तब तक प्रतिस्थापन के साथ प्रतिरूप लेते रहते हैं जब तक कि हम प्रत्येक वस्तु को कम-से-कम एक बार नहीं चुन लेते। फिर, हम गणना करते हैं कि हमने कितने चुनाव किए हैं और यदि यह N के समान नहीं है, तो सम्पूर्ण समुच्चय को बाहर फेंक दें और दोहराएं। यह कूपन संग्रहकर्ता की समस्या के लिए अस्पष्ट रूप से तुलनीय है, जहां प्रक्रिया में प्रत्येक कूपन को कम-से-कम एक बार देखे जाने तक X कूपन का एक समुच्चय (प्रतिस्थापन के साथ प्रतिदर्श द्वारा) एकत्र करना सम्मिलित है। ध्यान दें कि सभी प्रक्षेप्य स्थिति में, विकल्प समुच्चय की संख्या शून्य है जब तक कि NX है।

लेबलन, चयन, समूहीकरण

एक फलन ƒ : NX को X या N के परिप्रेक्ष्य से माना जा सकता है। यह विभिन्न विचारों की ओर ले जाता है:

  • फलन ƒ, N के प्रत्येक तत्व को X के एक तत्व द्वारा लेबल करता है।
  • फलन ƒ, N के प्रत्येक तत्व और कुल n विकल्पों के लिए समुच्चय X के एक तत्व का चयन करता है।
  • फलन ƒ, N के तत्वों को एक साथ समूहित करता है, जिन्हें X के समान तत्व से मानचित्रित किया जाता है।

ये दृष्टिकोण सभी स्थितियों के लिए समान रूप से अनुकूल नहीं हैं। लेबलन और चयन बिंदु X के तत्वों के क्रमचय के साथ अच्छी तरह से संगत नहीं हैं, क्योंकि यह लेबल या चयन को परिवर्तित करता है; दूसरी ओर समूहीकरण बिंदु विन्यास के विषय में सम्पूर्ण सूचना नहीं देता है जब तक कि X के तत्वों को स्वतंत्र रूप से अनुमत नहीं किया जा सकता है। जब N को अनुमत नहीं किया जाता है, तो लेबलन और चयन बिंदु लगभग समतुल्य होते हैं, परन्तु जब यह होता है, तो चयन बिंदु अधिक अनुकूल होता है। तब चयन को एक अनियंत्रित चयन के रूप में देखा जा सकता है: X से n तत्वों के एक (बहु-) समुच्चय का एकल विकल्प बनाया जाता है।

लेबलन और पुनरावृत्ति के साथ या पुनरावृत्ति के बिना

जब ƒ को N के तत्वों के लेबलन के रूप में देखा जाता है, तो बाद वाले को एक क्रम में व्यवस्थित माना जा सकता है और X से लेबल को क्रमिक रूप से उन्हें सौंपा जा सकता है। एक आवश्यकता जो ƒ अंतःक्षेपी होने का अर्थ है कि किसी भी लेबल का दूसरी बार उपयोग नहीं किया जा सकता है; परिणाम दोहराव के बिना लेबल का अनुक्रम है। ऐसी आवश्यकता के अभाव में, पुनरावृत्ति के साथ शब्दावली अनुक्रम का उपयोग किया जाता है, जिसका अर्थ है कि लेबल का एक से अधिक बार उपयोग किया जा सकता है (हालांकि पुनरावृत्ति के बिना होने वाले अनुक्रमों की भी अनुमति है)।

ƒ को X के तत्वों के एक अनियंत्रित चयन के रूप में देखते समय, उसी प्रकार का भेद अनुप्रयुक्त होता है। यदि ƒ अंतःक्षेपी होना चाहिए, तो चयन में X के विशिष्ट तत्व सम्मिलित होने चाहिए, इसलिए यह आकार n का X का एक उपसमुच्चय है, जिसे n-संयोजन भी कहा जाता है। आवश्यकता के बिना, X का एक और एक ही तत्व चयन में कई बार हो सकता है और परिणाम X से तत्वों के आकार n का एक बहु-समुच्चय होता है, जिसे n-बहुसंयोजन या पुनरावृत्ति के साथ n-संयोजन भी कहा जाता है।

N के लेबलन तत्वों के दृष्टिकोण से ƒ प्रक्षेप्य होने की आवश्यकता का अर्थ है कि X से चयन के दृष्टिकोण से, प्रत्येक लेबल का कम-से-कम एक बार उपयोग किया जाना है, इसका अर्थ है कि X के प्रत्येक तत्व को चयन में कम-से-कम एक बार सम्मिलित किया जाना चाहिए। प्रक्षेपण के साथ लेबलन N के तत्वों के समूह के समान है जिसके बाद प्रत्येक समूह को X के तत्व द्वारा लेबल किया जाता है और तदनुसार गणितीय रूप से वर्णन करने के लिए कुछ अधिक जटिल है।

समुच्चय और संख्या का विभाजन

ƒ को N के तत्वों के समूह के रूप में देखते समय (जो मानता है कि X के क्रमचय के अंतर्गत पहचान की जाती है), ƒ को प्रक्षेप्य के रूप में देखने का अर्थ है कि समूहों की संख्या निश्चित रूप से x होनी चाहिए। इस आवश्यकता के बिना समूहों की संख्या अधिकतम x हो सकती है। अंतःक्षेपी ƒ की आवश्यकता का अर्थ है कि N का प्रत्येक तत्व स्वयम में एक समूह होना चाहिए, जो अधिक से अधिक एक मान्य समूह छोड़ता है और इसलिए एक अरोचक गणना समस्या देता है।

इसके अतिरिक्त जब कोई N के क्रमचय के अंतर्गत पहचान करता है, तो इसका अर्थ समूहों को भूल जाना है परन्तु केवल उनके आकार को बनाए रखना है। इसके अतिरिक्त ये आकार किसी निश्चित क्रम में नहीं आते हैं, जबकि एक ही आकार एक से अधिक बार हो सकता है; कोई उन्हें संख्याओं की दुर्बलता से घटती सूची में व्यवस्थित करना चुन सकता है, जिसका योग संख्या n है। पूर्णतया x (आच्छादक ƒ के लिए) या अधिकतम x (यादृच्छिक ƒ के लिए) भागों में,यह संख्या n के एक विभाजन की संयोजी धारणा देता है।

सूत्र

बारह गुना तरीके के विभिन्न स्थितियों के सूत्र निम्नलिखित तालिका में संक्षेपित हैं; प्रत्येक तालिका प्रविष्टि सूत्र की व्याख्या करते हुए नीचे एक उपखंड से जुड़ती है।

बारह मिश्रित वस्तुएँ और उनके गणना के सूत्र
f-वर्ग कोई भी f अंतःक्षेपक f प्रक्षेप्य f
विशिष्ट
f
x में n-अनुक्रम
X का n-क्रमपरिवर्तन
x उपसमुच्चय के साथ n की संरचना
Sn कक्षाएं
f ∘ Sn
X का n- बहु-उपसमुच्चय
X का n-उपसमुच्चय
x पदों के साथ n की संरचना
Sx कक्षाएं
Sxf
N का ≤ x उपसमुच्चय में विभाजन
N का ≤ x तत्वों में विभाजन
N का x उपसमुच्चय में विभाजन
Sn×Sx कक्षाएं
Sxf ∘ Sn
n का ≤ x भागों में विभाजन
n का ≤ x भाग 1 में विभाजन
n का x भागों में विभाजन

उपयोग की जाने वाली विशेष संकेत पद्धति हैं:

  • अवरोही क्रमगुणित घात है।
  • आरोही क्रमगुणित घात है।
  • क्रमगुणित है।
  • दूसरी तरह की स्टर्लिंग संख्या है, n तत्वों के एक समुच्चय को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्याओं को दर्शाता है।
  • द्विपद गुणांक है।
  • आइवरसन कोष्ठक [ ] एक सत्य मान को 0 या 1 के रूप में विकोडन करता है।
  • जो संख्या n के k भागों में का विभाजन है।

पंक्तियों और स्तंभों का सहज अर्थ

यह त्वरित सारांश है कि विभिन्न स्थितियों का क्या अर्थ है। स्थितियों का विवरण नीचे दिया गया है।

X क्रमांकित वस्तुओं (1 से x तक क्रमांकित) के एक समुच्चय के विषय में विचार करें, जिसमें से हम n चुनते हैं, वस्तुओं की एक क्रमित सूची प्रदान करते हैं: उदाहरणार्थ, यदि वहाँ जिन वस्तुओं को हम चुनते हैं परिणाम सूची (5, 2, 10) हो सकता है। फिर हम गणना करते हैं कि ऐसी कितनी अलग-अलग सूचियाँ उपस्थित हैं, कभी-कभी पहले सूचियों को उन तरीकों से रूपांतरित करते हैं जो अलग-अलग संभावनाओं की संख्या को कम करते हैं।

तब स्तंभों का अर्थ है:

कोई भी f
किसी वस्तु को चयन करने के पश्चात, हम उसे वापस रख देते हैं, ताकि हम उसे पुनः चुन सकें।
अंतःक्षेपी f
एक वस्तु चयन करने के पश्चात, हम इसे अलग रख देते हैं, इसलिए हम इसे पुनः नहीं चुन सकते; इसलिए हम n विशिष्ट वस्तुओं के साथ समाप्त करेंगे। अनिवार्य रूप से, जब तक हैं, कोई भी सूची पूर्णतया चुनी नहीं जा सकती हैं।
प्रक्षेप्य f
एक वस्तु चयन करने के पश्चात, हम इसे वापस रख देते हैं, इसलिए हम इसे पुनः चुन सकते हैं - परन्तु अंत में, हमें प्रत्येक वस्तु को कम-से-कम एक बार चुनना होगा। अनिवार्य रूप से, जब तक , कोई भी सूची पूर्णतया चुनी नहीं जा सकती हैं।

और स्तंभयों का अर्थ है:

विशिष्ट
सूचियों को एकाकी छोड़ दें; उन्हें सीधे गिनें।
Sn कक्षाएँ
गणना से पूर्व, चुने गए वस्तुओं की वस्तु संख्या द्वारा सूचियों को क्रमबद्ध करें, ताकि क्रम कोई महत्व न रखे, जैसे, (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10) हैं।
Sx कक्षाएँ
गणना से पूर्व, देखी गई वस्तुओं को पुनः क्रमांकित करें ताकि पहली देखी गई वस्तु की संख्या 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) हैं।
Sn × Sx कक्षाएँ
दो सूचियाँ समान मानी जाती हैं यदि यह दोनों को पुन: व्यवस्थित करना और उन्हें ऊपर के रूप में पुन: लेबल करना और समान परिणाम उत्पन्न करना संभव है। उदाहरण के लिए, (3, 5, 3) और (2, 9, 9) को समान माना जाता है क्योंकि उन्हें (3, 3, 5) और (9, 9, 2) के रूप में पुनः क्रमित किया जा सकता है और फिर दोनों को पुनः लेबल करने से समान उत्पादन होता है सूची (1, 1, 2 देखें)।

गेंद और संदूक परिदृश्य का उपयोग करके तालिका का सहज अर्थ

नीचे दी गयी तालिका उपरोक्त तालिका के समान है, परन्तु यह सूत्रों को दिखाने के बजाय परिचित गेंदों और संदूकों के उदाहरण का उपयोग करके उनके अर्थ की सहज समझ देता है। पंक्तियाँ गेंदों और संदूकों की विशिष्टता का प्रतिनिधित्व करती हैं। यदि बहु-संकुलों (एक संदूक में एक से अधिक गेंद), या रिक्त संदूकों की अनुमति है तो स्तंभ दर्शाते हैं। तालिका के कक्ष उस प्रश्न को दर्शाते हैं जिसका उत्तर ऊपर दिए गए सूत्र तालिका में दिए गए सूत्र को हल करके दिया जाता है।

12 मिश्रित वस्तुओं की तालिका - गेंदों और संदूकों का उपयोग करके सहज ज्ञान युक्त तालिका
कोई भी f

(स्थानन पर कोई नियम नहीं)

अंतःक्षेपी f

(बहु-संकुलों की अनुमति नहीं है)

प्रक्षेप्य f

(रिक्त संदूकों की अनुमति नहीं है)

f
(चिह्नित गेंदे और संदूके)
x में एन-अनुक्रम

आप कितने तरीकों से रख सकते हैं
n चिह्नित गेंदों को x चिह्नित संदूकों में,
स्थानन पर कोई अन्य नियम नहीं है?

x में n-क्रमचय

आप कितने तरीकों से रख सकते हैं
n चिह्नित गेंदों को x चिह्नित संदूकों में,
बहु-
संकुलों की अनुमति नहीं है?

x उपसमुच्चय के साथ n की संरचना

आप कितने तरीकों से रख सकते हैं
n चिह्नित गेंदों को x चिह्नित संदूकों में,
रिक्त संदूकों की अनुमति नहीं है?

f ∘ Sn
(सादी गेंदे, चिह्नित संदूक)
X का n- बहु-उपसमुच्चय

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x चिन्हित संदूकों में
स्थानन पर कोई अन्य नियम नहीं है?

X का n-उपसमुच्चय

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x चिन्हित संदूकों में
बहु-
संकुलों की अनुमति नहीं है?

x पदों के साथ n की रचना

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x चिन्हित संदूकों में
रिक्त संदूकों की अनुमति नहीं है?

Sxf
(चिह्नित गेंद, सादे संदूक)
N का ≤ x उपसमुच्चय में विभाजन

आप कितने तरीकों से रख सकते हैं
n चिह्नित गेंदों को x सादे संदूकों में,
स्थानन पर कोई अन्य नियम नहीं है?

N का ≤ x तत्वों में विभाजन

आप कितने तरीकों से रख सकते हैं
n चिन्हित गेंदें x सादे
संदूकों में,
बहु-संकुलों की अनुमति नहीं है?

N का x उपसमुच्चय में विभाजन

आप कितने तरीकों से रख सकते हैं
n चिन्हित गेंदें x सादे
संदूकों में,
रिक्त संदूकों की अनुमति नहीं है?

Sxf ∘ Sn
(सादी गेंदे और संदूक)
n का ≤ x भागों में विभाजन

आप कितने तरीकों से रख सकते हैं
n
सादे गेंदों को x सादे संदूकों में,
स्थानन पर कोई अन्य नियम नहीं है?

n का ≤ x भाग 1 में विभाजन

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x सादे संदूकों में,
बहु-संकुलों की अनुमति नहीं है?

n का x भागों में विभाजन

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x सादे संदूकों में,
रिक्त संदूकों की अनुमति नहीं है?


विभिन्न स्थितियों का विवरण

नीचे दिए गए स्थितियों को इस तरह से क्रमबद्ध किया गया है कि उन स्थितियों को समूहित किया जा सके जिनके लिए गणना में उपयोग किए गए तर्क संबंधित हैं, जो दी गई तालिका में क्रम नहीं है।

N से X तक के फलन

यह स्थिति बिना किसी प्रतिबंध के X के n तत्वों के अनुक्रमों की गणना के समान है: एक फलन f : NX, N के तत्वों की n छवियों द्वारा निर्धारित किया जाता है, जो प्रत्येक को x के तत्वों के मध्य स्वतंत्र रूप से चुना जा सकता है। यह कुल xn संभावनाएं देता है।

उदाहरण:

N से X तक के अंतःक्षेपी फलन

यह स्थिति X के n अलग-अलग तत्वों के अनुक्रमों की गणना के समान है, जिसे X का "n-क्रमचय" या "बिना दोहराव वाले अनुक्रम" भी कहा जाता है; पुनः यह क्रम N के तत्वों की n छवियों द्वारा बनता है। यह स्थिति अप्रतिबंधित अनुक्रमों में से एक से भिन्न होता है जिसमें दूसरे तत्व के लिए एक विकल्प कम होता है और इसी तरह तीसरे तत्व के लिए दो कम होते हैं। इसलिए x की एक सामान्य घात के बजाय, मान x की अवरोही भाज्य घात द्वारा दिया जाता है, जिसमें प्रत्येक क्रमिक कारक पिछले एक से एक कम होता है। सूत्र है

ध्यान दें कि यदि n > x तो कोई कारक शून्य प्राप्त करता है, इसलिए इस स्थिति में कोई अंतःक्षेपी फलन NX पूर्णतया नहीं है; यह कोष्ठ के सिद्धांत का केवल एक पुनर्कथन है।

उदाहरण:

N के क्रमचय तक, N से X तक अंतःक्षेपी फलन

यह स्थिति X के उपसमुच्चयों के साथ n तत्वों की गणना के समान है, जिसे X का n-संयोजन भी कहा जाता है: X के n विशिष्ट तत्वों के अनुक्रमों के मध्य, जो केवल उनके शब्दों के क्रम में भिन्न होते हैं, उन्हें N के क्रमचय द्वारा पहचाना जाता है। चूंकि सभी स्थिति में यह समूह पूर्णतया n! विभिन्न अनुक्रमों में, X के n-संयोजनों की संख्या प्राप्त करने के लिए, हम ऐसे अनुक्रमों की संख्या को n! से विभाजित कर सकते हैं। इस संख्या को द्विपद गुणांक के रूप में जाना जाता है, जो इसलिए द्वारा दिया गया है:

उदाहरण:

N से X तक के फलन, N के क्रमचय तक

यह स्थिति X से n तत्वों के साथ बहु-समुच्चय की गणना के समान है (जिसे n-बहुसंयोजन भी कहा जाता है)। इसका कारण यह है कि X के प्रत्येक तत्व के लिए यह निर्धारित किया जाता है कि N के कितने तत्वों को f द्वारा मानचित्रित किया जाता है, जबकि दो फलन जो X के प्रत्येक तत्व को समान गुण प्रदान करते हैं, सदैव N के क्रमचय द्वारा दूसरे में परिवर्तित हो सकते हैं। सूत्र सभी फलनों NX की गणना यहाँ उपयोगी नहीं है, क्योंकि N के क्रमचय द्वारा एक साथ समूहीकृत उनकी संख्या एक फलन से दूसरे फलन में भिन्न होती है। बल्कि, जैसा कि संयोजनों की पुनरावृत्ति के अंतर्गत समझाया गया है, x तत्वों वाले समुच्चय से n-बहुसंयोजन की संख्या x + n − 1 तत्वों वाले समुच्चय से n-संयोजनों की संख्या के समान देखा जा सकता है। यह समस्या को बारह गुना तरीके से कम कर देता है और परिणाम देता है:

उदाहरण:

N के क्रमचय तक, N से X तक प्रक्षेप्य फलन

यह स्थिति X से n तत्वों के साथ बहु-समुच्चयों की गणना के समान है, जिसके लिए X का प्रत्येक तत्व कम-से-कम एक बार होता है। यह x के तत्वों की बहुलताओं को क्रम में सूचीबद्ध करके, x (गैर-शून्य) पदों के साथ n की रचनाओं की गणना करने के समान है। फलनों और बहु-समुच्चयों के मध्य पत्राचार पूर्व स्थिति की तरह ही है और प्रक्षेप्य आवश्यकता का अर्थ है कि सभी गुणक कम-से-कम एक हैं। सभी गुणाओं को 1 से घटाकर, यह पूर्व स्थिति में कम हो जाता है; चूँकि परिवर्तन से n का मान x से घट जाता है, परिणाम है:

ध्यान दें कि जब n < x कोई प्रक्षेप्य फलन नहीं होता है तो NX (एक प्रकार का "रिक्त कोष्ठ" सिद्धांत) है; इसे सूत्र में इस तथ्य पर ध्यान दिया जाता है कि यदि निचला सूचकांक ऋणात्मक है तो द्विपद गुणांक सदैव 0 होता है। वही मान व्यंजक द्वारा भी दिया जाता है;

चरम स्थिति को छोड़कर n = x = 0, जहां पूर्व अभिव्यक्ति सही ढंग से देती है, जबकि बाद वाला गलत देता है।

परिणाम का रूप कुल n − 1 में से चुने गए, nx तत्वों के एक उपसमुच्चय से स्पष्टतः प्रक्षेप्य फलनों NX के एक वर्ग को संबद्ध करने के तरीके की खोज करने का सुझाव देता है जिसे निम्नानुसार किया जा सकता है। सर्वप्रथम, समुच्चय N और X का कुल क्रम चुनें और ध्यान दें कि N का उपयुक्त क्रमचय अनुप्रयुक्त करके, प्रत्येक प्रक्षेप्य फलन NX को एक अद्वितीय दुर्बलता से बढ़ते हुए (और निश्चित रूप से अभी भी प्रक्षेप्य) फलन में परिवर्तित किया जा सकता है। यदि कोई N के तत्वों को क्रम n − 1 चाप से एक रेखीय आलेख से जोड़ता है, तो nx चाप के किसी भी उपसमुच्चय को चुनकर और बाकी को हटाकर, x संसक्त घटकों के साथ एक आलेख प्राप्त करता है और इन्हें X के क्रमिक तत्वों को भेजकर, एक दुर्बलता से बढ़ते हुए विशेष फलन NX को प्राप्त करता है; संसक्त घटकों के आकार भी x भागों में n की संरचना देते हैं। यह तर्क मूल रूप से सितारे और बार (प्रायिकता) पर दिया गया है, अतिरिक्त इसके कि वहाँ x − 1 "पृथक्करण" का पूरक विकल्प बनाया गया है।

उदाहरण:

N से X तक अंतःक्षेपी फलन, X के क्रमचय तक

इस स्थिति में हम X से अलग-अलग तत्वों के अनुक्रमों पर विचार करते हैं, परन्तु प्रत्येक तत्व पर X के क्रमचय को अनुप्रयुक्त करके एक दूसरे से प्राप्त की पहचान करते हैं। यह देखना सरल है कि ऐसे दो अलग-अलग अनुक्रम सदैव पहचाने जा सकते हैं: क्रमचय को शब्द को मानचित्रित करना चाहिए पहले अनुक्रम के i से दूसरे क्रम के i तक, और चूंकि किसी भी क्रम में दो बार कोई मान नहीं होता है, इसलिए ये आवश्यकताएं एक दूसरे के विपरीत नहीं होती हैं; यह उन तत्वों को मानचित्रित करने के लिए बनी हुई है जो पहले क्रम में नहीं होते हैं, दूसरे क्रम में यादृच्छिक तरीके से घटित नहीं होते हैं। एकमात्र तथ्य जो परिणाम को n और x पर पूर्णतया भी निर्भर करता है, वह यह है कि कोष्ठ के सिद्धांत द्वारा ऐसे किसी भी अनुक्रम nx के अस्तित्व की आवश्यकता होती है। आइवरसन कोष्ठक का उपयोग करके, इसलिए संख्या व्यक्त की जाती है।

N से X तक अंतःक्षेपी फलन, N से X के क्रमचय तक

यह स्थिति पूर्व एक तक कम हो गया है: चूँकि X से अलग-अलग तत्वों के सभी अनुक्रमों को पूर्व से ही उनके प्रत्येक पद के लिए X के क्रमचय को अनुप्रयुक्त करके एक दूसरे में रूपांतरित किया जा सकता है, साथ ही प्रतिबन्धों को पुनः व्यवस्थित करने से कोई नई पहचान नहीं मिलती है; संख्या बनी हुई है।

N से X तक प्रक्षेप्य फलन, X के क्रमचय तक

यह स्थिति N के x (गैर-रिक्त) उपसमुच्चयों में विभाजन की गणना करने के समान है, या पूर्णतया x वर्गों के साथ N पर तुल्यता संबंधों की गणना करने के समान है। वास्तव में, किसी प्रक्षेप्य फलन f : NX के लिए, f के अंतर्गत एक ही छवि होने का संबंध एक ऐसा तुल्यता संबंध है और जब X का क्रमचय बाद में अनुप्रयुक्त किया जाता है तो यह परिवर्तित नहीं होता है; इसके विपरीत कोई भी इस तरह के तुल्यता संबंध को x तुल्यता वर्गों में किसी तरह से X के तत्वों को निर्दिष्ट करके एक प्रक्षेप्य फलन में परिवर्तित कर सकता है। परिभाषा के अनुसार ऐसे विभाजनों या तुल्यता संबंधों की संख्या दूसरे प्रकार के S(n,x) की स्टर्लिंग संख्या है, जिसे लिखा भी गया है। इसके मान को एक पुनरावर्ती संबंध का उपयोग करके या उत्पन्न करने वाले फलनों का उपयोग करके वर्णित किया जा सकता है, परन्तु द्विपद गुणांक के विपरीत इन संख्याओं के लिए कोई संवृत सूत्र नहीं है जिसमें एक योग सम्मिलित नहीं है।

N से X तक प्रक्षेप्य फलन

प्रत्येक प्रक्षेप्य फलन f : NX के लिए, X के क्रमचय के अंतर्गत इसकी कक्षा में x! तत्व है, चूंकि रचना (बाईं ओर) X के दो अलग-अलग क्रमचय के साथ कभी भी N पर एक ही फलन नहीं देता है (क्रमचय X के कुछ तत्वों पर भिन्न होना चाहिए, जिसे सदैव कुछ i ∈ N के लिए f(i) के रूप में लिखा जा सकता है और रचनाएँ तब i है) पर भिन्न होंगी। यह इस प्रकार है कि इस स्थिति के लिए संख्या x! है, पूर्व स्थिति की संख्या का गुना, अर्थात है।

उदाहरण:

N से X तक फलन, X के क्रमचय तक

यह स्थिति प्रक्षेप्य फलनों के लिए संबंधित एक जैसा है, परन्तु X के कुछ तत्व किसी भी तुल्यता वर्ग के अनुरूप नहीं हो सकते हैं (चूंकि कोई X के क्रमचय तक फलनों पर विचार करता है, इससे कोई असमानता नहीं होती कि कौन से तत्व संबंधित हैं, केवल कितने हैं)। एक परिणाम के रूप में, N पर समानता संबंधों की गणना अधिकतम x वर्गों के साथ की जा रही है और परिणाम x तक के मानों के योग द्वारा उल्लिखित स्थिति से प्राप्त किया जाता है, दे रहा है। स्थिति x ≥ n में, x का आकार कोई प्रतिबंध नहीं लगाता है और कोई n तत्वों के समुच्चय पर सभी समतुल्य संबंधों की गणना कर रहा है (समान रूप से ऐसे समुच्चय के सभी विभाजन); इसलिए बेल संख्या Bn के लिए एक व्यंजक देता है।

N से X तक प्रक्षेप्य फलन, N और X के क्रमचय तक

यह स्थिति संख्या n के x गैर-शून्य भागों में विभाजन की गणना के समान है। केवल X के क्रमचय तक प्रक्षेप्य फलनों की गणना की स्थिति () की तुलना में, कोई केवल समतुल्यता वर्गों के आकार को बनाए रखता है, जो फलन N को विभाजित करता है (प्रत्येक आकार की बहुलता सहित), क्योंकि दो तुल्यता संबंधों को एक दूसरे में रूपांतरित किया जा सकता है, N का यदि और केवल यदि उनकी कक्षाओं के आकार मेल खाते हैं। यह ठीक वही है जो n के विभाजन की धारणा को N के विभाजन की धारणा से भिन्न करता है, इसलिए एक परिणाम के रूप में, x गैर-शून्य भागों में n के विभाजनों की संख्या px(n) परिभाषा के अनुसार मिलती है।

N से X तक के फलन, N और X के क्रमचय तक

यह स्थिति संख्या n के विभाजनों ≤ x भागों की गणना के समान है। संघ पूर्व स्थिति के समान है, अतिरिक्त इसके कि अब विभाजन के कुछ भाग 0 के समान हो सकते हैं (विशेष रूप से, वे X के तत्वों के अनुरूप हैं जो फलन की छवि में नहीं हैं)। n के प्रत्येक विभाजन में अधिकतम x गैर-शून्य भागों को आवश्यक संख्या में शून्य जोड़कर इस तरह के विभाजन तक बढ़ाया जा सकता है और यह सभी संभावनाओं के लिए एक बार खाता है, इसलिए परिणाम दिया जाता है। x भागों में से प्रत्येक में 1 जोड़कर, n + x का x गैर-शून्य भागों में विभाजन प्राप्त करता है, और यह पत्राचार विशेषण है; इसलिए दिए गए व्यंजक को इस रूप में लिखकर सरल किया जा सकता है।

चरम स्थिति

उपरोक्त सूत्र सभी परिमित समुच्चय N और X के लिए उचित मान देते हैं। कुछ स्थितियों में ऐसे वैकल्पिक सूत्र हैं जो लगभग समतुल्य हैं, परन्तु कुछ चरम स्थितियों में सही परिणाम नहीं देते हैं, जैसे कि जब N या X रिक्त होते हैं। निम्नलिखित विचार ऐसे स्थितियों पर अनुप्रयुक्त होते हैं।

  • प्रत्येक समुच्चय X के लिए रिक्त समुच्चय से X तक पूर्णतया एक फलन होता है (निर्दिष्ट करने के लिए इस फलन का कोई मान नहीं है), जो सदैव अंतःक्षेपी होता है, परन्तु जब तक X (भी) रिक्त नहीं होता है तब तक प्रक्षेप्य नहीं होता है।
  • प्रत्येक गैर-रिक्त समुच्चय N के लिए, N से रिक्त समुच्चय तक कोई फलन नहीं है (फलन का कम-से-कम एक मान है जिसे निर्दिष्ट किया जाना चाहिए, परन्तु यह नहीं हो सकता)।
  • जब n > x कोई अंतःक्षेपी फलन नहीं होता है तो NX, और यदि n < x कोई प्रक्षेप्य फलन NX नहीं हैं।
  • सूत्रों में प्रयुक्त भाव विशेष मान के रूप में होते हैं।
(प्रथम तीन एक रिक्त उत्पाद और मान के उदाहरण हैं, द्विपद गुणांक के पारंपरिक विस्तार द्वारा दिया जाता है, ऊपरी सूचकांक के यादृच्छिक मान है), जबकि

विशेष रूप से, X से लिए गए n तत्वों के साथ बहु-समुच्चय की गणना स्थिति में, दी गई अभिव्यक्ति के समान है, परन्तु बाद की अभिव्यक्ति की स्थिति n = x = 0 के लिए 0 देगा, (सामान्य परिपाटी के अनुसार ऋणात्मक निम्न सूचकांक वाले द्विपद गुणांक सदैव 0 होते हैं)। इसी प्रकार, x गैर-शून्य भागों के साथ n की गणना रचनाओं की स्थिति में, दी गई अभिव्यक्ति के लगभग व्यंजक के समतुल्य है। सितारों और बारों के तर्क द्वारा दिया गया है, परन्तु बाद वाला n = 0 और x के सभी मानों के लिए गलत मान देता है। उन स्थितियों के लिए जहां परिणाम में एक योग सम्मिलित होता है, अर्थात् अधिकतम x गैर-रिक्त उपसमुच्चय में N विभाजन की गणना या n के अधिकांश x गैर-शून्य भागों में विभाजन, योग सूचकांकों को 0 से प्रारंभ करने के लिए लिया जाता है; जब भी n > 0 होता है, यह अद्वितीय गैर-शून्य शब्द है जब n = 0 और परिणाम उन स्थितियों के लिए गलत होगा यदि योग और परिणाम उन स्थितियों के लिए गलत होगा यदि योग 1 से प्रारंभ करने के लिए लिया गया था।

सामान्यीकरण

हम क्रमचय के अन्य समूहों को N और X पर कार्य करने की अनुमति देकर और सामान्य कर सकते हैं। यदि G, N और H, X के क्रमचयों का एक समूह है, तो हम फलनों के तुल्यता वर्गों की गणना करते हैं। दो फलन f और F को समतुल्य माना जाता है और केवल यदि, ताकि उपस्थित है। यह विस्तार चक्रीय क्रमचय और द्वितल समूह क्रमचय, साथ ही संख्याओं और समुच्चयों के चक्रीय और द्वितल विभाजन जैसी धारणाओं की ओर जाता है।

बीस गुना शैली

बीस गुना वे नामक एक अन्य सामान्यीकरण केनेथ पी. बोगार्ट द्वारा अपनी पुस्तक "निर्देशित खोज के माध्यम से साहचर्य" में विकसित किया गया था। वस्तुओं को संदूकों में वितरित करने की समस्या में वस्तुएँ और संदूकों दोनों समान या भिन्न हो सकते हैं। बोगार्ट 20 स्थितियों की पहचान करता है।[3]

बीस गुना शैली; x प्राप्तकर्ताओं के मध्य n वस्तुओं के वितरण के लिए प्रतिरूप
क्रमांक वस्तुएं वितरण की

स्थिति

प्राप्तकर्ता
विशिष्ट अभिन्न
1 विशिष्ट कोई प्रतिबंध नहीं X में n-अनुक्रम
N का ≤ x उपसमुच्चय में विभाजन
2 अधिक से अधिक एक X का n-क्रमचय
3 कम-से-कम एक x उपसमुच्चय के साथ N की संरचना
N का x उपसमुच्चय में विभाजन
4 यथार्थत: एक
क्रमचय
5 विशिष्ट,
क्रमवार
प्रतिबंध नहीं
क्रमित फलन

खंडित क्रमचय ( भागों)
जहाँ लाह संख्या है।
6 कम-से-कम एक
फलनों पर क्रमवार

खंडित क्रमचय (x भागों)
जहाँ लाह संख्या है।
7 अभिन्न प्रतिबंध नहीं X का n- बहु-उपसमुच्चय

संख्या विभाजन ( भागों)
8 अधिक से अधिक एक X का n-उपसमुच्चय
9 कम-से-कम एक
रचनाएँ (x भाग)
n का x भागों में विभाजन
10 यथार्थत: एक


यह भी देखें

संदर्भ

  1. Richard P. Stanley (1997). Enumerative Combinatorics, Volume I. Cambridge University Press. ISBN 0-521-66351-2. p.41
  2. Robert V. Hogg and Elliot A. Tanis (2001). Probability and Statistical Inference. Prentice-Hall, Inc. ISBN 0-13-027294-9. p.81
  3. Kenneth P. Bogart (2004). Combinatorics Through Guided Discovery, p.57