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

समावेशन-बहिष्करण सिद्धांत उनके प्रतिच्छेदन के आकारों को बारी-बारी से जोड़कर और घटाकर समुच्चयों के संघ के आकार की गणना करता है।

Definition

एक गणना पहचान जो बताती है कि परिमित समुच्चयों के संघ की प्रमुखता उनके सभी प्रतिच्छेदनों की प्रमुखताओं के वैकल्पिक योग के बराबर होती है, जो प्रत्येक गैर-रिक्त उपसंग्रह पर ली जाती है।

Scope

यह विषय समावेशन-बहिष्करण सूत्र और निषिद्ध गुणों की सूची से बचने वाली वस्तुओं की गणना के लिए इसके अनुप्रयोगों को प्रस्तुत करता है: अव्यवस्थाएँ (derangements), अध्यारोपण (surjections), यूलर का टोटिएंट (Euler's totient), और किसी दी गई संख्या के सहअभाज्य पूर्णांकों की संख्या। यह छलनी दृष्टिकोण (sieve viewpoint) और आंशिक रूप से क्रमबद्ध समुच्चयों पर मोबियस-फंक्शन सामान्यीकरण (Mobius-function generalization) का परिचय देता है, जो सिद्धांत को एक व्यापक बीजगणितीय सेटिंग में रखता है।

Core questions

• कितने तत्व कई अतिव्यापी शर्तों में से कम से कम एक को संतुष्ट करते हैं?
• कोई निषिद्ध गुणों के एक सेट से बचने वाली वस्तुओं की गणना कैसे कर सकता है?
• अव्यवस्थाएँ (derangements) और अध्यारोपण (surjection) गणनाएँ सिद्धांत से कैसे प्राप्त होती हैं?
• एक पोसेट (poset) पर मोबियस फ़ंक्शन समावेशन-बहिष्करण को कैसे सामान्यीकृत करता है?

Key concepts

• अतिव्यापी समुच्चयों का संघ
• छलनी विधि
• समावेशन-बहिष्करण के माध्यम से अव्यवस्थाएँ (derangements)
• अध्यारोपण (surjections) की गणना
• यूलर का टोटिएंट फ़ंक्शन
• पोसेट्स (posets) पर मोबियस फ़ंक्शन

Key theories

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

समुच्चय A_1 से A_n के संघ की प्रमुखता एकल-समुच्चय आकारों के योग के बराबर होती है, जिसमें युग्मित प्रतिच्छेदन घटाए जाते हैं, फिर त्रिक प्रतिच्छेदन जोड़े जाते हैं, और इसी तरह, साझा तत्वों की अधिक गणना के लिए व्यवस्थित रूप से सुधार किया जाता है।

पोसेट्स पर मोबियस व्युत्क्रमण

स्टेनली का पोसेट-सैद्धांतिक सामान्यीकरण समावेशन-बहिष्करण के वैकल्पिक चिह्नों को आंशिक रूप से क्रमबद्ध समुच्चय के मोबियस फ़ंक्शन से बदल देता है, जो सिद्धांत को संख्या-सैद्धांतिक और जालक-सैद्धांतिक व्युत्क्रमण सूत्रों के साथ एकीकृत करता है।

Clinical relevance

छलनी का विचार संख्या सिद्धांत (इराटोस्थनीज की छलनी और विश्लेषणात्मक छलनी), संभाव्यता (बोनफेरोनी असमानताएँ जो संघ की संभावनाओं को सीमित करती हैं), और अतिव्यापी विफलता मोड वाले प्रणालियों के विश्वसनीयता विश्लेषण तक सामान्यीकृत होता है।

History

डी मोइव्रे और सिल्वेस्टर द्वारा संक्षेप में वर्णित, इस सिद्धांत को 1964 में रोटा द्वारा आंशिक रूप से क्रमबद्ध समुच्चयों पर मोबियस कार्यों के एक सामान्य सिद्धांत के भीतर रखा गया था, जो आधुनिक संयोजकता का एक मील का पत्थर था।

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

चिह्न वैकल्पिक क्यों होते हैं?

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

मोबियस फ़ंक्शन से क्या संबंध है?

समावेशन-बहिष्करण उपसमुच्चयों के बूलियन जालक पर मोबियस व्युत्क्रमण का विशेष मामला है, जहाँ मोबियस फ़ंक्शन प्लस या माइनस एक मान लेता है।