समावेशन-बहिष्करण सिद्धांत

वेन आरेख सेट ए और बी के मिलन को दर्शाता है क्योंकि सब कुछ सफेद रंग में नहीं है

साहचर्य में, गणित की एक शाखा, समावेशन-बहिष्करण सिद्धांत एक गिनती तकनीक है जो दो परिमित सेटों के संघ (सेट सिद्धांत) में तत्वों की संख्या प्राप्त करने की परिचित विधि को सामान्यीकृत करती है; प्रतीकात्मक रूप से व्यक्त किया गया है

$|A\cup B|=|A|+|B|-|A\cap B|$

जहाँ A और B दो परिमित समुच्चय हैं और |S एक समुच्चय S का (जिसे समुच्चय के तत्वों की संख्या माना जा सकता है, यदि समुच्चय परिमित समुच्चय है)। सूत्र इस तथ्य को व्यक्त करता है कि दो सेटों के आकारों का योग बहुत बड़ा हो सकता है क्योंकि कुछ तत्वों को दो बार गिना जा सकता है। दोहरी गिनती वाले तत्व दो सेटों के प्रतिच्छेदन (सेट सिद्धांत) में हैं और गणना को प्रतिच्छेदन के आकार को घटाकर सही किया जाता है।

समावेशन-बहिष्करण सिद्धांत, दो-सेट मामले का सामान्यीकरण होने के नाते, शायद तीन सेटों के मामले में अधिक स्पष्ट रूप से देखा जाता है, जो सेट ए, बी और सी के लिए दिया गया है

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

इस सूत्र को यह गिनकर सत्यापित किया जा सकता है कि वेन आरेख चित्र में प्रत्येक क्षेत्र सूत्र के दाईं ओर कितनी बार शामिल है। इस मामले में, अधिक गिने गए तत्वों के योगदान को हटाते समय, तीन सेटों के पारस्परिक प्रतिच्छेदन में तत्वों की संख्या बहुत बार घटा दी गई है, इसलिए सही कुल प्राप्त करने के लिए इसे वापस जोड़ा जाना चाहिए।

समावेशन-बहिष्करण तीन सेटों के लिए वेन आरेख द्वारा दर्शाया गया है

इन उदाहरणों के परिणामों को सामान्यीकृत करने से समावेशन-बहिष्करण का सिद्धांत मिलता है। के मिलन की प्रमुखता का पता लगाना n सेट:

1. सेट की प्रमुखताएं शामिल करें.
2. जोड़ीवार चौराहों की कार्डिनैलिटी को छोड़ दें।
3. ट्रिपल-वार चौराहों की प्रमुखताओं को शामिल करें।
4. चतुर्गुण-वार प्रतिच्छेदन की प्रमुखताओं को छोड़ दें।
5. क्विंटुपल-वार चौराहों की प्रमुखताओं को शामिल करें।
6. जारी रखें, जब तक कि कार्डिनैलिटी न हो जाए n-टुपल-वार चौराहा शामिल है (यदि n विषम है) या बहिष्कृत (n यहां तक ​​की)।

यह नाम इस विचार से आया है कि सिद्धांत अत्यधिक उदार समावेशन पर आधारित है, जिसके बाद क्षतिपूर्ति बहिष्करण होता है। इस अवधारणा का श्रेय अब्राहम डी मोइवरे (1718) को दिया जाता है। हालाँकि यह पहली बार डैनियल दा सिल्वा (गणितज्ञ) (1854) के पेपर में दिखाई देता है और बाद में जे. जे. सिल्वेस्टर (1883) के एक पेपर में। कभी-कभी इन प्रकाशनों के कारण सिद्धांत को दा सिल्वा या सिल्वेस्टर के सूत्र के रूप में जाना जाता है। इस सिद्धांत को संख्या सिद्धांत में व्यापक रूप से उपयोग किए जाने वाले छलनी सिद्धांत के उदाहरण के रूप में देखा जा सकता है और इसे कभी-कभी छलनी सूत्र के रूप में भी जाना जाता है। चूंकि परिमित संभावनाओं की गणना संभाव्यता स्थान की कार्डिनैलिटी के सापेक्ष गणना के रूप में की जाती है, इसलिए समावेशन-बहिष्करण के सिद्धांत के सूत्र तब मान्य रहते हैं जब सेट की कार्डिनैलिटी को सीमित संभावनाओं द्वारा प्रतिस्थापित किया जाता है। अधिक सामान्यतः, सिद्धांत के दोनों संस्करणों को माप सिद्धांत की सामान्य छतरी के नीचे रखा जा सकता है।

एक बहुत ही अमूर्त सेटिंग में, समावेशन-बहिष्करण के सिद्धांत को एक निश्चित मैट्रिक्स के व्युत्क्रम की गणना के रूप में व्यक्त किया जा सकता है। इस व्युत्क्रम की एक विशेष संरचना है, जो सिद्धांत को कॉम्बिनेटरिक्स और गणित के संबंधित क्षेत्रों में एक अत्यंत मूल्यवान तकनीक बनाती है। जैसा कि जियान-कार्लो रोटा ने कहा: <ब्लॉककोट> असतत संभाव्यता और संयोजक सिद्धांत में गणना के सबसे उपयोगी सिद्धांतों में से एक समावेशन-बहिष्करण का प्रसिद्ध सिद्धांत है। जब कुशलता से लागू किया जाता है, तो इस सिद्धांत ने कई संयुक्त समस्याओं का समाधान दिया है। </ब्लॉककोट>

सूत्र

इसके सामान्य सूत्र में, समावेशन-बहिष्करण का सिद्धांत कहता है कि परिमित सेटों के लिए A₁, …, A_n, एक की पहचान होती है

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$

(1)

समावेशन-बहिष्करण सूत्र का प्रत्येक पद धीरे-धीरे गिनती को सही करता है जब तक कि अंततः वेन आरेख के प्रत्येक भाग को बिल्कुल एक बार नहीं गिना जाता।

इसे संक्षिप्त रूप में इस प्रकार लिखा जा सकता है

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)$

या

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.$

शब्दों में, परिमित समुच्चयों के एक परिमित संघ में तत्वों की संख्या गिनने के लिए, पहले अलग-अलग समुच्चयों की प्रमुखताओं का योग करें, फिर कम से कम दो समुच्चयों में दिखाई देने वाले तत्वों की संख्या घटाएँ, फिर दिखाई देने वाले तत्वों की संख्या वापस जोड़ें कम से कम तीन सेट, फिर कम से कम चार सेट में दिखाई देने वाले तत्वों की संख्या घटाएं, और इसी तरह। यह प्रक्रिया हमेशा समाप्त होती है क्योंकि संघ में सेटों की संख्या से अधिक कोई भी तत्व प्रकट नहीं हो सकता है। (उदाहरण के लिए, यदि $n=4,$ ऐसे कोई तत्व नहीं हो सकते जो इससे अधिक में प्रकट हों $4$ सेट; समान रूप से, ऐसे कोई तत्व नहीं हो सकते जो कम से कम दिखाई दें $5$ सेट.)

अनुप्रयोगों में सिद्धांत को उसके पूरक रूप में व्यक्त होते देखना आम बात है। यानी देना S एक परिमित सार्वभौमिक समुच्चय बनें जिसमें सभी शामिल हों A_i और देना ${\bar {A_{i}}}$ के पूरक को निरूपित करें A_i में S, डी मॉर्गन के नियमों के अनुसार हमारे पास है

$\left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.$

कथन के दूसरे संस्करण के रूप में, आइए P₁, ..., P_n एक सेट के तत्वों के गुणों की एक सूची बनें S हो भी सकता है और नहीं भी, तब समावेशन-बहिष्करण का सिद्धांत तत्वों की संख्या की गणना करने का एक तरीका प्रदान करता है S जिसमें कोई भी गुण नहीं है। बस जाने A_i के तत्वों का उपसमुच्चय हो S जिसके पास संपत्ति है P_i और सिद्धांत को उसके पूरक रूप में उपयोग करें। यह संस्करण जे. जे. सिल्वेस्टर के कारण है।

ध्यान दें कि यदि आप केवल पहले को ही ध्यान में रखते हैं m<n दाहिनी ओर योग (सिद्धांत के सामान्य रूप में), तो आपको अधिक अनुमान मिलेगा यदि m अजीब है और यदि कम आंका गया है m सम है।

उदाहरण

पूर्णांकों की गिनती

समावेशन-बहिष्करण के सिद्धांत के उपयोग के एक सरल उदाहरण के रूप में, इस प्रश्न पर विचार करें:

{1,…, 100} में कितने पूर्णांक 2, 3 या 5 से विभाज्य नहीं हैं?

माना S = {1,…,100} और P₁ वह गुण कि एक पूर्णांक 2, P से विभाज्य है₂ वह गुण कि एक पूर्णांक 3 और P से विभाज्य है₃ वह गुण कि एक पूर्णांक 5 से विभाज्य है। मान लीजिए A_i S का उपसमुच्चय बनें जिसके तत्वों का गुण P है_i प्रारंभिक गिनती से हमारे पास है: |ए₁| = 50, |ए₂| = 33, और |ए₃| = 20. इनमें से 16 ऐसे पूर्णांक हैं जो 6 से विभाज्य हैं, 10 पूर्णांक 10 से विभाज्य हैं, और 6 पूर्णांक 15 से विभाज्य हैं। अंत में, केवल 3 पूर्णांक हैं जो 30 से विभाज्य हैं, इसलिए पूर्णांकों की संख्या 2, 3 या 5 में से किसी से भी विभाज्य नहीं है। द्वारा दिया गया है:

100 - (50 + 33 + 20) + (16 + 10 + 6) - 3 = 26।

विकृतियों की गिनती

एक अधिक जटिल उदाहरण निम्नलिखित है.

मान लीजिए कि 1 से n तक क्रमांकित n कार्डों का एक डेक है। मान लीजिए कि m क्रमांकित कार्ड सही स्थिति में है यदि यह डेक में mवां कार्ड है। कम से कम 1 कार्ड सही स्थिति में होने पर कितने तरीकों से कार्डों को फेंटा जा सकता है?

सेट ए को परिभाषित करके प्रारंभ करें_m, जो कि mth कार्ड वाले कार्डों के सभी ऑर्डर सही हैं। तब कम से कम एक कार्ड सही स्थिति में होने पर ऑर्डरों की संख्या, W, m है

$W=\left|\bigcup _{m=1}^{n}A_{m}\right|.$

समावेशन-बहिष्करण का सिद्धांत लागू करें,

$W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots$

प्रत्येक मान $A_{m_{1}}\cap \cdots \cap A_{m_{p}}$ कम से कम p मान m वाले शफ़ल के सेट का प्रतिनिधित्व करता है₁, …, एम_pसही स्थिति में. ध्यान दें कि कम से कम p मान सही होने पर फेरबदल की संख्या केवल p पर निर्भर करती है, विशेष मान पर नहीं $m$. उदाहरण के लिए, पहले, तीसरे और 17वें कार्ड को सही स्थिति में रखने वाले शफ़ल की संख्या दूसरे, 5वें और 13वें कार्ड को सही स्थिति पर रखने वाले शफ़ल की संख्या के समान है। यह केवल इतना मायने रखता है कि n कार्डों में से 3 को सही स्थिति में चुना गया था। इस प्रकार हैं ${\textstyle {n \choose p}}$ पीटीएच योग में समान पद (संयोजन देखें)।

$W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots$

$|A_{1}\cap \cdots \cap A_{p}|$ सही स्थिति में पी तत्वों वाले ऑर्डर की संख्या है, जो शेष एन - पी तत्वों, या (एन - पी) को ऑर्डर करने के तरीकों की संख्या के बराबर है! इस प्रकार हम अंततः प्राप्त करते हैं:

${\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!(n-p)!}}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!}}\end{aligned}}$

ऐसा क्रमपरिवर्तन जहां कोई भी कार्ड सही स्थिति में न हो, विव्यवस्था कहलाता है। एन लेना! क्रमपरिवर्तन की कुल संख्या होने के लिए, संभावना Q कि एक यादृच्छिक फेरबदल एक विक्षोभ उत्पन्न करता है, द्वारा दी गई है

$Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},$

ई की टेलर श्रृंखला के n + 1 शब्दों का कटाव⁻¹. इस प्रकार ताश के पत्तों के फेंटे गए डेक के क्रम का अनुमान लगाने और प्रत्येक पत्ते के बारे में गलत होने की संभावना लगभग ई है⁻¹या 37%।

एक विशेष मामला

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

$A_{J}:=\bigcap _{j\in J}A_{j}$

समान कार्डिनैलिटी है, मान लीजिए α_k= |ए_J|, फिर, {1,…,n} के प्रत्येक के-तत्व उपसमुच्चय J के लिए

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.$

या, पूरक रूप में, जहां सार्वभौमिक सेट एस में कार्डिनैलिटी α है₀,

$\left|S\smallsetminus \bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.$

सूत्र सामान्यीकरण

उपसमुच्चय A के समुच्चय|परिवार (दोहराव की अनुमति) का एक परिवार दिया गया है₁, ए₂, ..., ए_n एक सार्वभौमिक समुच्चय S में, समावेशन-बहिष्करण का सिद्धांत इनमें से किसी भी उपसमुच्चय में S के तत्वों की संख्या की गणना नहीं करता है। इस अवधारणा का सामान्यीकरण एस के तत्वों की संख्या की गणना करेगा जो इन सेटों के कुछ निश्चित एम में दिखाई देते हैं।

मान लीजिए N = [n] = {1,2,…,n}। यदि हम परिभाषित करें $A_{\emptyset }=S$, तो पिछले अनुभाग के नोटेशन का उपयोग करके समावेशन-बहिष्करण के सिद्धांत को इस प्रकार लिखा जा सकता है; A में से किसी में भी शामिल S के तत्वों की संख्या नहीं_i है:

$\sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.$

यदि I सूचकांक सेट N का एक निश्चित उपसमुच्चय है, तो A से संबंधित तत्वों की संख्या_i I में सभी i के लिए और किसी अन्य मान के लिए नहीं है:

$\sum _{I\subseteq J}(-1)^{|J|-|I|}|A_{J}|.$

सेट को परिभाषित करें

$B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\smallsetminus I.$

हम बी में से किसी में भी तत्वों की संख्या की तलाश नहीं कर रहे हैं_k जो, समावेशन-बहिष्करण के सिद्धांत द्वारा (साथ) $B_{\emptyset }=A_{I}$), है

$\sum _{K\subseteq N\smallsetminus I}(-1)^{|K|}|B_{K}|.$

N के उपसमुच्चय और I वाले N के उपसमुच्चय के बीच पत्राचार K ↔ J = I ∪ K एक आक्षेप है और यदि J और K इस मानचित्र के अंतर्गत मेल खाते हैं तो B_K = ए_J, यह दर्शाता है कि परिणाम वैध है।

संभावना में

प्रायिकता में, घटनाओं के लिए ए₁, ..., ए_n संभाव्यता स्थान में $(\Omega ,{\mathcal {F}},\mathbb {P} )$, समावेशन-बहिष्करण सिद्धांत n = 2 के लिए बन जाता है

$\mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),$

n=3 के लिए

$\mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})$

और सामान्य तौर पर

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\cdots +(-1)^{n-1}\sum _{i<...<n}\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right),$

जिसे बंद रूप में इस प्रकार लिखा जा सकता है

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{I\subseteq \{1,\ldots ,n\} \atop |I|=k}\mathbb {P} (A_{I})\right),$

जहां अंतिम योग सूचकांक 1, ..., n के सभी उपसमुच्चय I पर चलता है जिसमें बिल्कुल k तत्व होते हैं, और

$A_{I}:=\bigcap _{i\in I}A_{i}$

उन सभी ए के प्रतिच्छेदन को दर्शाता है_iI में सूचकांक के साथ.

बूले की असमानता#बोनफेरोनी असमानताओं के अनुसार, सूत्र में पहले शब्दों का योग वैकल्पिक रूप से एक समीकरण के पक्षों के लिए एक ऊपरी सीमा और एक निचली सीमा होती है। इसका उपयोग उन मामलों में किया जा सकता है जहां पूरा फॉर्मूला बहुत बोझिल है।

एक सामान्य माप स्थान (एस,Σ,μ) और मापने योग्य उपसमुच्चय ए के लिए₁, …, ए_n परिमित माप में, उपरोक्त सर्वसमिकाएँ संभाव्यता मापते समय भी मान्य होती हैं $\mathbb {P}$ माप μ द्वारा प्रतिस्थापित किया जाता है।

विशेष मामला

यदि, समावेशन-बहिष्करण सिद्धांत के संभाव्य संस्करण में, प्रतिच्छेदन ए की संभावना_I केवल I की प्रमुखता पर निर्भर करता है, जिसका अर्थ है कि {1,…,n} में प्रत्येक k के लिए एक a है_kऐसा है कि

$a_{k}=\mathbb {P} (A_{I}){\text{ for every }}I\subset \{1,\ldots ,n\}{\text{ with }}|I|=k,$

तब उपरोक्त सूत्र सरल हो जाता है

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}$

द्विपद गुणांक की संयुक्त व्याख्या के कारण ${\textstyle {\binom {n}{k}}}$. उदाहरण के लिए, यदि घटनाएँ $A_{i}$ तब स्वतंत्र और समान रूप से वितरित होते हैं $\mathbb {P} (A_{i})=p$ मेरे और हमारे पास जो कुछ भी है उसके लिए $a_{k}=p^{k}$, जिस स्थिति में उपरोक्त अभिव्यक्ति सरल हो जाती है

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=1-(1-p)^{n}.$

(घटनाओं के पूरकों के प्रतिच्छेदन पर विचार करके भी यह परिणाम अधिक सरलता से प्राप्त किया जा सकता है $A_{i}$.)

सामान्य माप स्थान के मामले में एक समान सरलीकरण संभव है (S, Σ, μ) और मापने योग्य उपसमुच्चय A₁, …, ए_n परिमित माप का.

अन्य सूत्र

सिद्धांत को कभी-कभी रूप में बताया जाता है वह कहता है कि यदि

$g(A)=\sum _{S\subseteq A}f(S)$

तब

$f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S)$

(⁎⁎)

समावेशन-बहिष्करण सिद्धांत का संयोजक और संभाव्य संस्करण इसके उदाहरण हैं (⁎⁎).

Proof

Take ${\underline {m}}=\{1,2,\ldots ,m\}$, $f({\underline {m}})=0$, and

$f(S)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right|{\text{ and }}f(S)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right)$

respectively for all sets $S$ with $S\subsetneq {\underline {m}}$. Then we obtain

$g(A)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right|,\quad g({\underline {m}})=\left|\bigcup _{i\in {\underline {m}}}A_{i}\right|{\text{ and }}g(A)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right),~~g({\underline {m}})=\mathbb {P} \left(\bigcup _{i\in {\underline {m}}}A_{i}\right)$

respectively for all sets $A$ with $A\subsetneq {\underline {m}}$. This is because elements $a$ of $\cap _{i\in {\underline {m}}\smallsetminus A}A_{i}$ can be contained in other $A_{i}$ ($A_{i}$ with $i\in A$) as well, and the $\cap \smallsetminus \cup$-formula runs exactly through all possible extensions of the sets $\{A_{i}\mid i\in {\underline {m}}\smallsetminus A\}$ with other $A_{i}$, counting $a$ only for the set that matches the membership behavior of $a$, if $S$ runs through all subsets of $A$ (as in the definition of $g(A)$).

Since $f({\underline {m}})=0$, we obtain from (⁎⁎) with $A={\underline {m}}$ that

$\sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{|T|-1}g({\underline {m}}\smallsetminus T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-|S|-1}g(S)=g({\underline {m}})$

and by interchanging sides, the combinatorial and the probabilistic version of the inclusion–exclusion principle follow.

अगर किसी को कोई नंबर दिखता है $n$ इसके प्रमुख कारकों के एक सेट के रूप में, फिर (⁎⁎) वर्ग-मुक्त पूर्णांक|वर्ग-मुक्त प्राकृतिक संख्याओं के लिए मोबियस व्युत्क्रम सूत्र का सामान्यीकरण है। इसलिए, (⁎⁎) को ए के सभी उपसमुच्चयों के आंशिक रूप से क्रमित सेट की घटना बीजगणित के लिए मोबियस व्युत्क्रम सूत्र के रूप में देखा जाता है।

मोबियस व्युत्क्रम सूत्र के पूर्ण संस्करण के सामान्यीकरण के लिए, (⁎⁎) को मल्टीसेट्स के लिए सामान्यीकृत किया जाना चाहिए। सेट के बजाय मल्टीसेट के लिए, (⁎⁎) बन जाता है

$f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)$

(⁎⁎⁎)

कहाँ $A-S$ जिसके लिए मल्टीसेट है $(A-S)\uplus S=A$, और

• μ(S) = 1 यदि S सम और विषम संख्या कार्डिनैलिटी का एक सेट (यानी दोहरे तत्वों के बिना एक मल्टीसेट) है।
• μ(S) = −1 यदि S विषम कार्डिनैलिटी का एक सेट (यानी डबल तत्वों के बिना एक मल्टीसेट) है।
• μ(S) = 0 यदि S एक उचित मल्टीसेट है (अर्थात S में दोहरे तत्व हैं)।

नोटिस जो $\mu (A-S)$ बस है $(-1)^{|A|-|S|}$ का (⁎⁎) यदि $A-S$ एक सेट है.

Proof of (⁎⁎⁎)

Substitute

$$g(S)=\sum _{T\subseteq S}f(T)$$

on the right hand side of (⁎⁎⁎). Notice that $f(A)$ appears once on both sides of (⁎⁎⁎). So we must show that for all $T$ with $T\subsetneq A$, the terms $f(T)$ cancel out on the right hand side of (⁎⁎⁎). For that purpose, take a fixed $T$ such that $T\subsetneq A$ and take an arbitrary fixed $a\in A$ such that $a\notin T$.

Notice that $A-S$ must be a set for each positive or negative appearance of $f(T)$ on the right hand side of (⁎⁎⁎) that is obtained by way of the multiset $S$ such that $T\subseteq S\subseteq A$. Now each appearance of $f(T)$ on the right hand side of (⁎⁎⁎) that is obtained by way of $S$ such that $A-S$ is a set that contains $a$ cancels out with the one that is obtained by way of the corresponding $S$ such that $A-S$ is a set that does not contain $a$. This gives the desired result.

अनुप्रयोग

समावेशन-बहिष्करण सिद्धांत का व्यापक रूप से उपयोग किया जाता है और इसके केवल कुछ अनुप्रयोगों का उल्लेख यहां किया जा सकता है।

विकृतियों की गिनती

Main article: Derangement

समावेशन-बहिष्करण सिद्धांत का एक प्रसिद्ध अनुप्रयोग एक परिमित सेट के सभी विक्षोभों की गिनती की संयुक्त समस्या के लिए है। समुच्चय A का विचलन A से अपने आप में एक विक्षेपण है जिसका कोई निश्चित बिंदु नहीं है। समावेशन-बहिष्करण सिद्धांत के माध्यम से कोई यह दिखा सकता है कि यदि ए की कार्डिनैलिटी एन है, तो विचलन की संख्या [एन! / e] जहां [x] x के निकटतम पूर्णांक फ़ंक्शन को दर्शाता है; एक विस्तृत प्रमाण उपलब्ध है यादृच्छिक क्रमपरिवर्तन आँकड़े#क्रमपरिवर्तन की संख्या जो कि विक्षिप्त हैं और ऊपर #उदाहरण भी देखें।

विक्षोभों की संख्या गिनने की समस्या की पहली घटना संयोग के खेल पर एक प्रारंभिक पुस्तक में है: पी. आर. डी मोंटमॉर्ट (1678 - 1719) द्वारा लिखित एस्साई डी'एनालिसिस सुर लेस ज्यूक्स डे हैजर्ड और इसे या तो मोंटमॉर्ट की समस्या के रूप में जाना जाता था या उसने इसे जो नाम दिया, वह है प्रॉब्लम डेस रेनकॉन्ट्रेस। इस समस्या को हैचचेक समस्या के नाम से भी जाना जाता है।

विक्षोभों की संख्या को n के उपकारक के रूप में भी जाना जाता है, जिसे !n लिखा जाता है। इसका तात्पर्य यह है कि यदि सभी आक्षेपों को एक ही संभावना दी गई है, तो संभावना है कि एक यादृच्छिक आक्षेप एक विक्षिप्तता है, जैसे-जैसे n बढ़ता है, तेजी से 1/e तक पहुंच जाता है।

चौराहों की गिनती

समावेशन-बहिष्करण के सिद्धांत को, डी मॉर्गन के नियम के साथ मिलाकर, सेटों के प्रतिच्छेदन की प्रमुखता की गणना करने के लिए भी इस्तेमाल किया जा सकता है। होने देना ${\overline {A_{k}}}$ ए के पूरक का प्रतिनिधित्व करें_kकुछ सार्वभौमिक सेट ए के संबंध में ऐसा है कि $A_{k}\subseteq A$ प्रत्येक k के लिए तो हमारे पास हैं

$\bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A_{i}}}}}$

इस प्रकार एक प्रतिच्छेदन खोजने की समस्या को एक संघ खोजने की समस्या में बदल दिया जाता है।

ग्राफ़ रंग

समावेशन बहिष्करण सिद्धांत कई एनपी-हार्ड ग्राफ़ विभाजन समस्याओं, जैसे ग्राफ़ रंग, के लिए एल्गोरिदम का आधार बनाता है। सिद्धांत का एक प्रसिद्ध अनुप्रयोग एक ग्राफ के रंगीन बहुपद का निर्माण है।

द्विपक्षीय ग्राफ पूर्ण मिलान

द्विदलीय ग्राफ के पूर्ण मिलान की संख्या की गणना सिद्धांत का उपयोग करके की जा सकती है।

ऑन्टोफ़ फ़ंक्शंस की संख्या

परिमित समुच्चय A और B दिए जाने पर, A से B तक कितने विशेषण फलन (कार्यों पर) हैं? व्यापकता के किसी भी नुकसान के बिना हम ए = {1, ..., के} और बी = {1, ..., एन} ले सकते हैं, क्योंकि केवल सेट की प्रमुखताएं मायने रखती हैं। ए से बी तक सभी फ़ंक्शन (गणित) के सेट के रूप में एस का उपयोग करके, और बी में प्रत्येक i के लिए, संपत्ति पी को परिभाषित करना_iचूंकि फ़ंक्शन बी में तत्व i को मिस करता है (i फ़ंक्शन की छवि (गणित) में नहीं है), समावेशन-बहिष्करण का सिद्धांत ए और बी के बीच ऑन्ट फ़ंक्शंस की संख्या देता है:

$\sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.$

निषिद्ध पदों के साथ क्रमपरिवर्तन

समुच्चय S = {1, ..., n} का क्रमपरिवर्तन जहाँ S का प्रत्येक तत्व कुछ निश्चित स्थितियों में न होने तक सीमित है (यहाँ क्रमपरिवर्तन को S के तत्वों के क्रम के रूप में माना जाता है) को निषिद्ध क्रमपरिवर्तन कहा जाता है पद. उदाहरण के लिए, एस = {1,2,3,4} के साथ, इस प्रतिबंध के साथ क्रमपरिवर्तन कि तत्व 1 स्थिति 1 या 3 में नहीं हो सकता है, और तत्व 2 स्थिति 4 में नहीं हो सकता है: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 और 4321। ए देकर_iउन स्थितियों का सेट बनें जिनमें तत्व i को रखने की अनुमति नहीं है, और संपत्ति P_i यह वह गुण है जो क्रमपरिवर्तन तत्व i को A में एक स्थिति में रखता है_i, समावेशन-बहिष्करण के सिद्धांत का उपयोग उन क्रमपरिवर्तनों की संख्या की गणना करने के लिए किया जा सकता है जो सभी प्रतिबंधों को पूरा करते हैं। दिए गए उदाहरण में, गुण P के साथ 12 = 2(3!) क्रमपरिवर्तन हैं₁, 6 = 3! संपत्ति पी के साथ क्रमपरिवर्तन₂ और किसी भी क्रमपरिवर्तन में गुण P नहीं है₃ या पी₄ क्योंकि इन दोनों तत्वों के लिए कोई प्रतिबंध नहीं है। प्रतिबंधों को संतुष्ट करने वाले क्रमपरिवर्तनों की संख्या इस प्रकार है:

4! - (12 + 6 + 0 + 0) + (4) = 24 - 18 + 4 = 10।

इस गणना में अंतिम 4 दोनों गुणों पी वाले क्रमपरिवर्तन की संख्या है₁ और पी₂. सूत्र में कोई अन्य गैर-शून्य योगदान नहीं है।

दूसरे प्रकार की स्टर्लिंग संख्याएँ

Main article: Stirling numbers of the second kind

दूसरे प्रकार की स्टर्लिंग संख्याएँ, S(n,k) n तत्वों के एक समूह के विभाजन की संख्या को k गैर-रिक्त उपसमुच्चय (अप्रभेद्य बक्से) में गिनती हैं। उनके लिए एक स्पष्ट सूत्र बहुत निकट से संबंधित समस्या में समावेशन-बहिष्करण के सिद्धांत को लागू करके प्राप्त किया जा सकता है, अर्थात्, एन-सेट के विभाजन की संख्या को के गैर-रिक्त लेकिन अलग-अलग बक्से में गिनना (ऑर्डर किया गया सेट गैर-रिक्त उपसमुच्चय) ). एन-सेट के सभी विभाजनों से युक्त सार्वभौमिक सेट का उपयोग करके के (संभवतः खाली) अलग-अलग बक्सों में, ए₁, ए₂, …, ए_k, और गुण पी_iमतलब कि विभाजन में बॉक्स ए है_iखाली, समावेशन-बहिष्करण का सिद्धांत संबंधित परिणाम का उत्तर देता है। k से विभाजित करना! कृत्रिम क्रम को हटाने के लिए दूसरे प्रकार का स्टर्लिंग नंबर दिया जाता है:

$S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.$

रूक बहुपद

Main article: Rook polynomial

एक रूक बहुपद एक बोर्ड बी पर गैर-आक्रमणकारी रूक (शतरंज) को रखने के तरीकों की संख्या का जनक बहुपद है जो एक बिसात के वर्गों के सबसेट की तरह दिखता है; अर्थात्, कोई भी दो रूक एक ही पंक्ति या स्तंभ में नहीं हो सकते। बोर्ड बी एन पंक्तियों और एम कॉलम वाले आयताकार बोर्ड के वर्गों का कोई उपसमूह है; हम इसे उन वर्गों के रूप में सोचते हैं जिनमें किसी को किश्ती लगाने की अनुमति है। गुणांक, आर_k(बी) एक्स का^kरूक बहुपद R में_B(x) उन तरीकों की संख्या है जिनसे k रुकता है, जिनमें से कोई भी दूसरे पर हमला नहीं करता है, उन्हें B के वर्गों में व्यवस्थित किया जा सकता है। किसी भी बोर्ड B के लिए, एक पूरक बोर्ड होता है $B'$ इसमें आयताकार बोर्ड के वर्ग शामिल हैं जो बी में नहीं हैं। इस पूरक बोर्ड में एक रूक बहुपद भी है $R_{B'}(x)$ गुणांक के साथ $r_{k}(B').$ पूरक बोर्ड के रूक बहुपद के गुणांकों के संदर्भ में रूक बहुपद के उच्चतम गुणांक की गणना करने में सक्षम होना कभी-कभी सुविधाजनक होता है। व्यापकता खोए बिना हम मान सकते हैं कि n ≤ m, इसलिए यह गुणांक r है_n(बी)। पूर्ण n × m चेकरबोर्ड पर n गैर-आक्रमणकारी बदमाशों को रखने के तरीकों की संख्या (बिना इस बात की परवाह किए कि क्या बदमाशों को बोर्ड बी के वर्गों में रखा गया है) गिरते हुए फैक्टोरियल द्वारा दिया गया है:

$(m)_{n}=m(m-1)(m-2)\cdots (m-n+1).$

लेटिंग पी_i संपत्ति यह है कि पूर्ण बोर्ड पर एन गैर-आक्रमणकारी रूक्स के असाइनमेंट में कॉलम I में एक रूक है जो बोर्ड बी के एक वर्ग में नहीं है, तो समावेशन-बहिष्करण के सिद्धांत से हमारे पास है:

$r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').$

यूलर का फाई फ़ंक्शन

Main article: Euler's totient function

यूलर का टोटिएंट या फाई फ़ंक्शन, φ(n) एक अंकगणितीय फ़ंक्शन है जो n से कम या उसके बराबर सकारात्मक पूर्णांकों की संख्या की गणना करता है जो n के लिए अपेक्षाकृत अभाज्य हैं। अर्थात्, यदि n एक धनात्मक पूर्णांक है, तो φ(n) 1 ≤ k ≤ n की श्रेणी में पूर्णांक k की संख्या है, जिसमें 1 के अलावा n के साथ कोई सामान्य कारक नहीं है। समावेशन-बहिष्करण के सिद्धांत का उपयोग प्राप्त करने के लिए किया जाता है φ(n) के लिए एक सूत्र। मान लीजिए कि S समुच्चय {1, …, n} है और गुण P को परिभाषित करता है_iऐसा प्रतीत होता है कि S में एक संख्या अभाज्य संख्या p से विभाज्य है_i, 1 ≤ i ≤ r के लिए, जहां का अभाज्य गुणनखंडन

$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.$

तब,

$\varphi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leqslant i<j\leqslant r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).$

पतला समावेशन-बहिष्करण सिद्धांत

See also: Bonferroni inequalities

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

चलो ए₁, ..., ए_n मनमाना सेट और पी बनें₁, …, पी_n बंद इकाई अंतराल में वास्तविक संख्याएँ [0, 1]. फिर, {0,…, n} में प्रत्येक सम संख्या k के लिए, सूचक कार्य असमानता को संतुष्ट करते हैं:

$1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots p_{i_{j}}\,1_{A_{i_{1}}\cap \cdots \cap A_{i_{j}}}.$

मुख्य कथन का प्रमाण

सभी सेटों के संघ में निहित एक तत्व चुनें और जाने दें $A_{1},A_{2},\dots ,A_{t}$ इसमें शामिल व्यक्तिगत सेट बनें। (ध्यान दें कि t > 0.) चूँकि तत्व को समीकरण के बाईं ओर से एक बार सटीक रूप से गिना जाता है (1), हमें यह दिखाने की ज़रूरत है कि इसे दाहिनी ओर से ठीक एक बार गिना जाता है। दाहिनी ओर, एकमात्र गैर-शून्य योगदान तब होता है जब किसी विशेष पद के सभी उपसमुच्चयों में चुना हुआ तत्व होता है, अर्थात, सभी उपसमुच्चयों का चयन किया जाता है $A_{1},A_{2},\dots ,A_{t}$. इनमें से प्रत्येक सेट के लिए योगदान एक है (शब्द के आधार पर प्लस या माइनस) और इसलिए यह शब्द में उपयोग किए गए इन सबसेट की केवल (हस्ताक्षरित) संख्या है। फिर हमारे पास है:

${\begin{aligned}|\{A_{i}\mid 1\leqslant i\leqslant t\}|&-|\{A_{i}\cap A_{j}\mid 1\leqslant i<j\leqslant t\}|+\cdots +(-1)^{t+1}|\{A_{1}\cap A_{2}\cap \cdots \cap A_{t}\}|={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}}.\end{aligned}}$

द्विपद प्रमेय द्वारा,

$0=(1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}.$

इस तथ्य का उपयोग करते हुए ${\binom {t}{0}}=1$ और शब्दों को पुनर्व्यवस्थित करना, हमारे पास है

$1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}},$

और इसलिए, चुने गए तत्व को समीकरण के दाईं ओर केवल एक बार गिना जाता है (1).

बीजगणितीय प्रमाण

संकेतक फ़ंक्शंस (जिन्हें विशिष्ट फ़ंक्शंस के रूप में भी जाना जाता है) का उपयोग करके एक बीजगणितीय प्रमाण प्राप्त किया जा सकता है। समुच्चय X के उपसमुच्चय S का सूचक फलन है

${\begin{aligned}&\mathbf {1} _{S}:X\to \{0,1\}\\&\mathbf {1} _{S}(x)={\begin{cases}1&x\in S\\0&x\notin S\end{cases}}\end{aligned}}$

अगर $A$ और $B$ के दो उपसमुच्चय हैं $X$, तब

$\mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.$

मान लीजिए A संघ को दर्शाता है ${\textstyle \bigcup _{i=1}^{n}A_{i}}$ सेट का A₁, …, ए_n. समावेशन-बहिष्करण सिद्धांत को सामान्य रूप से सिद्ध करने के लिए, हम पहले पहचान को सत्यापित करते हैं

$\mathbf {1} _{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop |I|=k}\mathbf {1} _{A_{I}}$

(⁎)

सूचक कार्यों के लिए, जहां:

$A_{I}=\bigcap _{i\in I}A_{i}.$

निम्नलिखित फ़ंक्शन

$\left(\mathbf {1} _{A}-\mathbf {1} _{A_{1}}\right)\left(\mathbf {1} _{A}-\mathbf {1} _{A_{2}}\right)\cdots \left(\mathbf {1} _{A}-\mathbf {1} _{A_{n}}\right),$

समान रूप से शून्य है क्योंकि: यदि x, A में नहीं है, तो सभी कारक 0 − 0 = 0 हैं; और अन्यथा, यदि x किसी A से संबंधित है_m, फिर संगत एम^वां कारक 1 − 1 = 0 है। बायीं ओर उत्पाद का विस्तार करके, समीकरण (⁎) अनुसरण करता है।

सेट की कार्डिनैलिटी के लिए समावेशन-बहिष्करण सिद्धांत को सिद्ध करने के लिए, समीकरण का योग करें (⁎) A के मिलन में सभी x पर₁, …, ए_n. संभाव्यता में प्रयुक्त संस्करण प्राप्त करने के लिए, अपेक्षित मान लें (⁎). सामान्य तौर पर, लेबेस्ग ने समीकरण को एकीकृत किया (⁎) μ के संबंध में। इन व्युत्पत्तियों में हमेशा रैखिकता का उपयोग करें।

यह भी देखें

• Boole's inequality
• Combinatorial principles
• Maximum-minimums identity
• Necklace problem
• Pigeonhole principle
• Schuette–Nesbitt formula

संदर्भ

• Allenby, R.B.J.T.; Slomson, Alan (2010), How to Count: An Introduction to Combinatorics, Discrete Mathematics and Its Applications (2 ed.), CRC Press, pp. 51–60, ISBN 9781420082609
• Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing, 39 (2): 546–563, doi:10.1137/070683933
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice–Hall, ISBN 9780136020400
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0
• Fernández, Roberto; Fröhlich, Jürg; Alan D., Sokal (1992), Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory, Texts an Monographs in Physics, Berlin: Springer-Verlag, pp. xviii+444, ISBN 3-540-54358-9, MR 1219313, Zbl 0761.60061
• Graham, R.L.; Grötschel, M.; Lovász, L. (1995), Hand Book of Combinatorics (volume-2), MIT Press – North Holland, ISBN 9780262071710
• Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman&Hall/CRC, ISBN 9781584887430
• "Inclusion-and-exclusion principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Mazur, David R. (2010), Combinatorics A Guided Tour, The Mathematical Association of America, ISBN 9780883857625
• Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, ISBN 9781420099829
• Stanley, Richard P. (1986), Enumerative Combinatorics Volume I, Wadsworth & Brooks/Cole, ISBN 0534065465
• van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge University Press, ISBN 0521422604

This article incorporates material from principle of inclusion–exclusion on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.