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

From Vigyanwiki

साहचर्य में, बारह गुना शैली दो परिमित समुच्चयों से संबंधित 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 से तत्वों के आकार एन का एक बहु-समुच्चय होता है, जिसे एन-बहुसंयोजन या पुनरावृत्ति के साथ एन-संयोजन भी कहा जाता है।

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

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

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

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

सूत्र

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

The twelve combinatorial objects and their enumeration formulas
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
Sxf
partition of N into ≤ x उपसमुच्चयs
partition of N into ≤ x elements
partition of N into x उपसमुच्चय
Sn×Sx orbits
Sxf ∘ 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)।

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

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

Table of the 12 combinatorial objects - intuitive chart using balls and boxes
Any f

(no rules on placement)

Injective f

(no multi-packs allowed)

Surjective f

(no empty boxes allowed)

f
(Balls and Boxes marked)
एक्स में एन-अनुक्रम

आप कितने तरीकों से रख सकते हैं
एन चिह्नित गेंदों को एक्स चिह्नित बक्से में,
प्लेसमेंट पर कोई अन्य नियम नहीं है?

एक्स में एन-क्रमचय

आप कितने तरीकों से रख सकते हैं
एन चिह्नित गेंदों को एक्स चिह्नित बक्से में,
with no multi-packs allowed?

composition of N with x उपसमुच्चयs

आप कितने तरीकों से रख सकते हैं
एन चिह्नित गेंदों को एक्स चिह्नित बक्से में,
with no empty boxes allowed?

f ∘ Sn
(Balls plain, Boxes marked)
X का n-मल्टीसुबसेट

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

n-उपसमुच्चय of X

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x चिन्हित बॉक्स में
with no multi-packs allowed?

composition of n with x terms

आप कितने तरीकों से रख सकते हैं
n सादे गेंदों को x चिन्हित बॉक्स में
with no empty boxes allowed?

Sxf
(Balls marked, Boxes plain)
N का ≤ x सबसेट में विभाजन

आप कितने तरीकों से रख सकते हैं
एन चिह्नित गेंदों को एक्स सादे बक्से में,
प्लेसमेंट पर कोई अन्य नियम नहीं है?

partition of N into ≤ x elements

आप कितने तरीकों से रख सकते हैं
n marked balls into x plain boxes,
with no multi-packs allowed?

partition of N into x उपसमुच्चयs

आप कितने तरीकों से रख सकते हैं
n marked balls into x plain boxes,
with no empty boxes allowed?

Sxf ∘ Sn
(Balls and Boxes plain)
partition of n into ≤ x parts

आप कितने तरीकों से रख सकते हैं
n plain balls into x plain boxes,
प्लेसमेंट पर कोई अन्य नियम नहीं है?

partition of n into ≤ x parts 1

आप कितने तरीकों से रख सकते हैं
n plain balls into x plain boxes,
with no multi-packs allowed?

partition of n into x parts

आप कितने तरीकों से रख सकते हैं
n plain balls into x plain boxes,
with no empty boxes allowed?


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

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

N से X तक के फलन

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

उदाहरण:

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

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

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

उदाहरण:

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

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

उदाहरण:

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

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

उदाहरण:

N के क्रमचय तक, N से X तक विशेषण फलन

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

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

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

परिणाम का रूप विशेषण फलनों के एक वर्ग को संबद्ध करने के तरीके की खोज करने का सुझाव देता है NX सीधे के एक उपसमुच्चय के लिए nx कुल में से चुने गए तत्व n − 1, जो निम्नानुसार किया जा सकता है। पहले समुच्चय 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 के क्रमचय तक

यह स्थिति 'एन के एक समुच्चय के X (गैर-रिक्त) उपसमुच्चय में विभाजन' की गणना करने के समान है, या पूर्णतया X वर्गों के साथ एन पर तुल्यता संबंधों की गणना करने के समान है। दरअसल, किसी विशेषण फलन के लिए 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 के कुछ तत्व किसी भी तुल्यता वर्ग के अनुरूप नहीं हो सकते हैं (चूंकि कोई X के क्रमचय तक फलनों को मानता है, इससे कोई फर्क नहीं पड़ता कि कौन से तत्व संबंधित हैं, बस कितने ). एक परिणाम के रूप में एन पर समानता संबंधों की गणना अधिकतम x वर्गों के साथ की जा रही है, और परिणाम x तक के मानों के योग द्वारा उल्लिखित स्थिति से प्राप्त किया जाता है, दे रहा है . स्थिति में x ≥ n, x का आकार कोई प्रतिबंध नहीं लगाता है, और कोई n तत्वों के समुच्चय पर सभी समतुल्य संबंधों की गणना कर रहा है (समान रूप से ऐसे समुच्चय के सभी विभाजन); इसलिए बेल संख्या बी के लिए बेल संख्या # योग सूत्र देता हैn.

N से X तक विशेषण फलन, N और X के क्रमचय तक

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

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

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

चरम स्थिति

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

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

विशेष रूप से X से लिए गए एन तत्वों के साथ #केस एफएन के स्थिति में, दी गई अभिव्यक्ति के समान है , परन्तु बाद की अभिव्यक्ति स्थिति के लिए 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]

बीस गुना शैली; x प्राप्तकर्ताओं के बीच n वस्तुओं के वितरण के लिए मॉडल
Objects वितरण की

स्थिति

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

खंडित क्रमचय ( भागों)
जहाँ लाह संख्या है
6 कम-से-कम एक
ordered onto functions

खंडित क्रमचय (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