समुच्चय का विभाजन

This article is about grouping elements of a set. For partitioning an integer, see Partition (number theory). For the partition calculus of sets, see Infinitary combinatorics.

बंडलों में विभाजित टिकटों का समुच्चय: कोई भी टिकट दो बंडलों में नहीं है, कोई भी बंडल खाली नहीं है, एवं प्रत्येक टिकट बंडल में है।

5 तत्वों वाले समुच्चय का बेल नंबर विभाजन। रंगीन क्षेत्र X के उपसमुच्चय को इंगित करता है जो संलग्न विभाजन का सदस्य बनता है। बिना रंग वाले बिंदु एकल-तत्व उपसमुच्चय को दर्शाते हैं। पहले दिखाए गए विभाजन में पाँच एकल-तत्व उपसमुच्चय हैं; अंतिम विभाजन में पाँच तत्वों वाला उपसमुच्चय है।

जेनजी की कहानी के 54 अध्यायों के लिए पारंपरिक जापानी प्रतीक पांच तत्वों को विभाजित करने के 52 तरीकों पर आधारित हैं (दो लाल प्रतीक ही विभाजन का प्रतिनिधित्व करते हैं, एवं 54 तक पहुंचने के लिए हरा प्रतीक जोड़ा जाता है)।

गणित में, किसी समुच्चय का विभाजन उसके तत्वों को अन्य-रिक्त उपसमुच्चयों में इस प्रकार समूहित करना है कि प्रत्येक तत्व ठीक उपसमुच्चय में सम्मिलित हो जाए।

उपसमुच्चय (गणित) पर प्रत्येक समतुल्य संबंध इस समुच्चय के विभाजन को परिभाषित करता है, एवं प्रत्येक विभाजन समतुल्य संबंध को परिभाषित करता है। तुल्यता संबंध या विभाजन से सुसज्जित समुच्चय को सामान्यतः प्रकार सिद्धांत एवं प्रमाण सिद्धांत में कभी-कभी सेटॉइड कहा जाता है।

परिभाषा एवं संकेतन

समुच्चयअर्थात्, उपसमुच्चय परस्पर असंयुक्त समुच्चय हैं।

समान रूप से, समुच्चय P का परिवार X का विभाजन है यदि एवं केवल यदि निम्नलिखित सभी शर्तें पूरी होती हैं:

• परिवार P में खाली समुच्चय नहीं है (अर्थात $\emptyset \notin P$),
• P में समुच्चयों का संघ (समुच्चय सिद्धांत) X के समान (अर्थात $\textstyle \bigcup _{A\in P}A=X$) है, $P$में समुच्चय को 'एग्जॉस्ट' या 'कवर' X कहा जाता है। सामूहिक रूप से संपूर्ण घटनाओं एवं कवर (टोपोलॉजी) को भी देखें।
• P में किन्हीं दो भिन्न-भिन्न समुच्चयों का प्रतिच्छेदन (समुच्चय सिद्धांत) खाली है (अर्थात $(\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset$) है, P के तत्वों को जोड़ीवार असंयुक्त या परस्पर अपवर्जी कहा जाता है। पारस्परिक विशिष्टता भी देखें।

समुच्चय में $P$ को विभाजन के ब्लॉक, भाग या सेल कहलाते हैं।यदि $a\in X$ तब हम युक्त सेल का $a$ प्रतिनिधित्व $[a]$ द्वारा करते है। अर्थात, $[a]$ में सेल के लिए संकेतन $P$ है जिसमें $a$ है।

हर विभाजन $P$ पर समतुल्य संबंध $X$ से पहचाना जा सकता है, अर्थात् संबंध $\sim _{\!P}$ ऐसा कि किसी के लिए भी $a,b\in X$ अपने पास $a\sim _{\!P}b$ है, यदि एवं केवल यदि $a\in [b]$ (समकक्ष रूप से, यदि एवं केवल यदि $b\in [a]$ है। संकेतन $\sim _{\!P}$ इस विचार को उद्घाटित करता है कि तुल्यता संबंध का निर्माण विभाजन से किया जा सकता है। इसके विपरीत प्रत्येक समतुल्य संबंध को विभाजन के साथ पहचाना जा सकता है। यही कारण है कि कभी-कभी अनौपचारिक रूप से कहा जाता है कि समतुल्य संबंध विभाजन के समान है। यदि P किसी दिए गए तुल्यता संबंध से पहचाना गया विभाजन है $\sim$, फिर कुछ लेखक $P=X/\sim$ लिखते हैं। यह संकेतन इस विचार का सूचक है कि विभाजन समुच्चय X है जो कोशिकाओं में विभाजित है। अंकन इस विचार को भी उद्घाटित करता है कि तुल्यता संबंध से कोई विभाजन का निर्माण कर सकता है।

$P$ का 'रैंक' $|X|-|P|$ है, यदि $X$ परिमित समुच्चय है।

उदाहरण

• खाली समुच्चय $\emptyset$ अर्थात् बिल्कुल ही विभाजन है $\emptyset$. (नोट: यह विभाजन है, विभाजन का सदस्य नहीं।)
• किसी भी अन्य-रिक्त समुच्चय के लिए X, P = { X } X का विभाजन है, जिसे 'तुच्छ विभाजन' कहा जाता है।
  • विशेष रूप से, प्रत्येक सिंगलटन समुच्चय {x} में बिल्कुल विभाजन{ {x} } होता है।
• समुच्चय U के किसी भी अन्य-रिक्त उचित उपसमुच्चय A के लिए, समुच्चय A अपने पूरक (समुच्चय सिद्धांत) के साथ मिलकर U का विभाजन बनाता है, अर्थात्, { A, U ∖ A } होता है।
• समुच्चय {1, 2, 3} में ये पाँच विभाजन हैं (प्रति आइटम विभाजन):
  • { {1}, {2}, {3} }, कभी-कभी 1 | 2 | 3 लिखा जाता है।
  • { {1, 2}, {3} }, या 1 2 | 3,
  • { {1, 3}, {2} }, या 1 3 | 2,
  • { {1}, {2, 3} }, या 1 | 2 3,
  • { {1, 2, 3} }, या 123 (संदर्भों में जहां संख्या के साथ कोई भ्रम नहीं होगा)।
• निम्नलिखित के विभाजन नहीं {1, 2, 3} हैं:
  • { {}, {1, 3}, {2} } विभाजन नहीं है (किसी भी समुच्चय का) क्योंकि इसका तत्व खाली समुच्चय है।
  • { {1, 2}, {2, 3} } विभाजन नहीं है (किसी भी समुच्चय का) क्योंकि तत्व 2 से अधिक ब्लॉक में समाहित है।
  • { {1}, {2} } का विभाजन नहीं है {1, 2, 3} क्योंकि इसके किसी भी ब्लॉक में 3 नहीं है; चूँकि, यह का विभाजन है {1, 2}.

विभाजन एवं तुल्यता संबंध

समुच्चय X पर किसी समतुल्य संबंध के लिए, इसके समतुल्य वर्गों का समुच्चय X का विभाजन है। इसके विपरीत, x ~ y ठीक तब जब x एवं y P में ही भाग में हों। इस प्रकार तुल्यता संबंध एवं विभाजन की धारणाएं अनिवार्य रूप से समतुल्य हैं।

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

विभाजन का परिशोधन

परिशोधन द्वारा आदेशित 4-तत्व समुच्चय के विभाजन

समुच्चय अनौपचारिक रूप से, इसका तात्पर्य है कि α, ρ का विखंडन है। उस स्थिति में, यह लिखा α ≤ ρ लिखा है।

x के विभाजनों के समुच्चय पर यह उत्तम संबंध आंशिक रूप से ऑर्डर किया गया समुच्चय है (इसलिए अंकन ≤ उपयुक्त है)। तत्वों के प्रत्येक समुच्चय में कम से कम ऊपरी सीमा (उनका जुड़ाव) एवं सबसे बड़ी निचली सीमा (उनका मिलन) होती है, जिससे यह जाली (क्रम) बनाता है, एवं अधिक विशेष रूप से (परिमित समुच्चय के विभाजन के लिए) यह ज्यामितीय जाली है। 4-तत्व समुच्चय के विभाजन जाली में 15 तत्व हैं एवं इसे बाईं ओर हासे आरेख में प्रदर्शित किया गया है।

विभाजन α एवं ρ के मिलन एवं जुड़ाव को निम्नानुसार परिभाषित किया गया है। मिलन' $\alpha \wedge \rho$ वह विभाजन है जिसके ब्लॉक खाली समुच्चय को छोड़कर, α के ब्लॉक एवं ρ के ब्लॉक के प्रतिच्छेदन हैं। दूसरे शब्दों में, ब्लॉक $\alpha \wedge \rho$ α के ब्लॉक एवं ρ के ब्लॉक का प्रतिच्छेदन है जो दूसरे से भिन्न नहीं हैं। 'जॉइन' को परिभाषित करने के लिए $\alpha \vee \rho$, यदि A एवं B असंयुक्त नहीं हैं, तो α के ब्लॉक A एवं ρ के ब्लॉक B पर A ~ B द्वारा संबंध बनाएं। तब $\alpha \vee \rho$ वह विभाजन है जिसमें प्रत्येक ब्लॉक C इस संबंध से जुड़े ब्लॉकों के परिवार का मिलन है।

ज्यामितीय जालकों एवं मैट्रोइड्स के मध्य समानता के आधार पर, परिमित समुच्चय के विभाजन की यह जाली मैट्रोइड के समान होती है जिसमें मैट्रोइड के आधार समुच्चय में जाली के परमाणु (क्रम सिद्धांत) होते हैं, अर्थात्, विभाजन के साथ $n-2$ सिंगलटन समुच्चय एवं दो-तत्व समुच्चय होते हैं। ये परमाणु विभाजन पूर्ण ग्राफ़ के किनारों के साथ मेल खाते हैं। परमाणु विभाजनों के समुच्चय का मैट्रोइड क्लोजर ऑपरेटर उन सभी में सबसे अच्छा सामान्य मोटेपन है; ग्राफ़-सैद्धांतिक शब्दों में, यह संपूर्ण ग्राफ़ के वर्टेक्स (ग्राफ़ सिद्धांत) का किनारों के दिए गए समुच्चय द्वारा गठित उपग्राफ़ के कनेक्टेड घटक (ग्राफ़ सिद्धांत) में विभाजन है। इस प्रकार, विभाजन की जाली संपूर्ण ग्राफ़ के ग्राफ़िक मैट्रोइड के फ्लैटों की जाली के समान होती है।

अन्य उदाहरण तुल्यता संबंधों के परिप्रेक्ष्य से विभाजनों के परिशोधन को दर्शाता है। यदि D मानक 52 कार्ड डेक में कार्डों का समुच्चय है, तो D पर समान-रंग जैसा संबंध जिसे ~_C दर्शाया जा सकता है। इसके दो समतुल्य वर्ग समुच्चय {लाल कार्ड} एवं {काले कार्ड} हैं। ~_C के अनुरूप 2 भाग वाला विभाजन इसमें परिशोधन है जो समान सूट जैसा संबंध ~_S उत्पन्न करता है, जिसमें चार समतुल्य वर्ग {हुकुम}, {हीरे}, {दिल}, एवं {क्लब} होते हैं।

नॉनक्रॉसिंग विभाजन

समुच्चय N = {1, 2, ..., n} का संगत समतुल्य संबंध ~ वाला विभाजन 'नॉनक्रॉसिंग विभाजन' है यदि इसमें निम्नलिखित गुण हैं: यदि N के चार तत्व a, b, c एवं d में a < b < c < d है, a ~ c एवं b ~ d को संतुष्ट करता है, तो a ~ b ~ c ~ d होता है। नाम निम्नलिखित समतुल्य परिभाषा से आता है: कल्पना करें कि N के तत्व 1, 2, ..., n को नियमित n-गॉन के n शीर्षों के रूप में (वामावर्त क्रम में) खींचा गया है। फिर प्रत्येक ब्लॉक को बहुभुज (जिसके शीर्ष ब्लॉक के तत्व हैं) के रूप में चित्रित करके विभाजन की कल्पना की जा सकती है। विभाजन तब नॉनक्रॉसिंग होता है यदि एवं केवल यदि ये बहुभुज प्रतिच्छेद नहीं करते हैं।

परिमित समुच्चय के अन्य-क्रॉसिंग विभाजनों की जाली सभी विभाजनों की जाली का उपसमूह बनाती है, परन्तु उपजालक नहीं, क्योंकि दो जाली के जुड़ने के संचालन सहमत नहीं होते हैं।

मुक्त संभाव्यता सिद्धांत में अपनी भूमिका के कारण नॉनक्रॉसिंग विभाजन जाली को हाल ही में महत्व दिया गया है।

विभाजनों की गिनती

n तत्व समुच्चय के विभाजन की कुल संख्या बेल संख्या B_n है. पहले कई बेल नंबर B₀ हैं₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, एवं B₆ = 203 (sequence A000110 in the OEIS), बेल नंबर प्रत्यावर्तन को संतुष्ट करते हैं,

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$,

एवं जनरेटिंग फलन

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}$ है।

बेल त्रिकोण का निर्माण

बेल संख्याओं की गणना बेल त्रिकोण का उपयोग करके भी की जा सकती है।

जिसमें प्रत्येक पंक्ति में प्रथम मान पूर्व पंक्ति के अंत से कॉपी किया जाता है, एवं पश्चात के मानों की गणना, बाईं ओर की संख्या एवं ऊपर की संख्या को जोड़कर की जाती है। इस त्रिभुज के दोनों किनारों पर बेल संख्याएँ दोहराई जाती हैं। त्रिभुज के अंदर की संख्याएँ उन विभाजनों को गिनती हैं जिनमें दिया गया तत्व सबसे बड़ा सिंगलटन (गणित) होता है।

बिल्कुल k (अन्य-रिक्त) भागों में समुच्चय किए गए n तत्व के विभाजनों की संख्या दूसरे प्रकार S(n, k) की स्टर्लिंग संख्या है।

N तत्व समुच्चय के अन्य-क्रॉसिंग विभाजन की संख्या कैटलन संख्या

$C_{n}={1 \over n+1}{2n \choose n}$ है।

यह भी देखें

• सटीक कवर
• ब्लॉक डिज़ाइन
• क्लस्टर विश्लेषण
• विभाजन विषयों की सूची
• लेमिनेशन (टोपोलॉजी)
• एमईसीई सिद्धांत
• आंशिक तुल्यता संबंध
• विभाजन बीजगणित
• विभाजन शोधन
• बिंदु-परिमित संग्रह
• समुच्चय विभाजन द्वारा कविता योजनाएं
• कमजोर क्रम (आदेशित समुच्चय विभाजन)

संदर्भ

• Brualdi, Richard A. (2004). Introductory Combinatorics (4th ed.). Pearson Prentice Hall. ISBN 0-13-100119-1.
• Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0-12-622760-8.