समावेशन-अपवर्जन सिद्धांत कैलकुलेटर

समावेशन-अपवर्जन सिद्धांत (Principle of Inclusion-Exclusion) क्या है?

समावेशन-अपवर्जन सिद्धांत (PIE) कॉम्बिनेटॉरिक्स और सेट सिद्धांत में गिनती की एक बुनियादी तकनीक है। यह अतिव्यापी परिमित समुच्चयों (overlapping finite sets) के संघ (union) के आकार के लिए एक सटीक सूत्र प्रदान करता है। इसका मुख्य विचार यह है कि जब आप कई समुच्चयों के आकारों को जोड़ते हैं, तो कुछ तत्वों को एक से अधिक बार गिना जाता है — समावेशन-अपवर्जन इन अतिव्यापी तत्वों को घटाकर और फिर तिहरे अतिव्याप्त तत्वों को वापस जोड़कर इसे ठीक करता है, यह सुनिश्चित करते हुए कि प्रत्येक तत्व को ठीक एक बार गिना जाए।

दो समुच्चयों A और B के लिए सूत्र बहुत सरल है: |A∪B| = |A| + |B| − |A∩B|। यहाँ |A| और |B| को जोड़ने पर A∩B के तत्वों को दो बार गिना जाता है, इसलिए संतुलन के लिए हम |A∩B| को एक बार घटाते हैं।

n समुच्चयों के लिए सामान्य सूत्र

n समुच्चयों A₁, A₂, …, A_n के लिए समावेशन-अपवर्जन का सामान्य सूत्र निम्न है:

|A₁∪…∪A_n| = Σ|A_i| − Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| − … + (−1)ⁿ⁺¹|A₁∩…∩A_n|

इस योग में 2ⁿ−1 पद होते हैं। विषम आकार के उपसमुच्चयों के लिए चिन्ह सकारात्मक (+) और सम आकार के उपसमुच्चयों के लिए चिन्ह नकारात्मक (−) होता है। 2 समुच्चयों के लिए 3 पद; 3 समुच्चयों के लिए 7 पद; 4 समुच्चयों के लिए 15 पद होते हैं।

3 समुच्चयों का सूत्र (3-Set Formula)

तीन समुच्चयों का सूत्र सबसे अधिक उपयोग किया जाने वाला रूप है:

|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

यहाँ व्यक्तिगत समुच्चयों को जोड़ा जाता है, फिर सभी जोड़ियों के प्रतिच्छेदन को घटाया जाता है, और अंत में तीनों के उभयनिष्ठ (intersection) भाग को वापस जोड़ दिया जाता है।

वेन आरेख और क्षेत्रीय गणना

n समुच्चयों के लिए एक वेन आरेख में 2ⁿ क्षेत्र होते हैं। 2 समुच्चयों के लिए: केवल A, केवल B, A∩B, और कोई भी नहीं। 3 समुच्चयों के लिए: 7 आंतरिक क्षेत्र होते हैं। 4 समुच्चयों के लिए: 15 आंतरिक क्षेत्र होते हैं (जिन्हें 4 अतिव्यापी दीर्घवृत्तों द्वारा दर्शाया जाता है क्योंकि चार वृत्त 15 अलग-अलग क्षेत्र नहीं बना सकते)।

प्रायिकता में समावेशन-अपवर्जन

प्रायिकता सिद्धांत में भी यही सिद्धांत लागू होता है: P(A∪B∪C) = P(A)+P(B)+P(C) − P(A∩B) − P(A∩C) − P(B∩C) + P(A∩B∩C)। यदि कुल सार्वत्रिक समुच्चय का आकार |U| ज्ञात है, तो किसी भी घटना की प्रायिकता P = घटना की संख्या / |U| होती है।

समावेशन-अपवर्जन सिद्धांत के अनुप्रयोग

• डीरेंजमेंट (Derangements): उन क्रमपरिवर्तनों (permutations) की संख्या की गणना करना जिनमें कोई भी तत्व अपने मूल स्थान पर नहीं रहता।
• यूलर का टॉटिएंट फ़ंक्शन: φ(n) = n × ∏_p|n(1 − 1/p), जो n से छोटे और उसके सह-अभाज्य पूर्णांकों को गिनता है।
• इरेटोस्थनीज की छलनी (Sieve of Eratosthenes): अभाज्य संख्याओं को खोजने की प्रक्रिया में इसी सिद्धांत का उपयोग होता है।
• बोनफेरोनी असमानताएं: जब पूर्ण गणना असंभव हो, तब श्रृंखला के प्रारंभिक पदों का उपयोग करके संघ का अनुमान लगाना।

हल किया गया उदाहरण: 1 से 100 तक विभाज्यता

1 से 100 तक कितने पूर्णांक 2, 3 या 5 से विभाज्य हैं? मान लें A = 2 के गुणज (50), B = 3 के गुणज (33), C = 5 के गुणज (20)। प्रतिच्छेदन: A∩B = 6 के गुणज (16), A∩C = 10 के गुणज (10), B∩C = 15 के गुणज (6), A∩B∩C = 30 के गुणज (3)। समावेशन-अपवर्जन द्वारा: |A∪B∪C| = 50+33+20−16−10−6+3 = 74। इस प्रकार, 1 से 100 तक 74 पूर्णांक 2, 3 या 5 से विभाज्य हैं और 26 पूर्णांक इनसे विभाज्य नहीं हैं।