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

Question

आज मैं पहली बार समावेश-अपवर्जन सिद्धांत पर आया हूं। मेरा मानना ​​है कि मैं इसे समझ गया हूं, हालांकि जब मैंने इस पर कुछ सवाल हल करने की कोशिश की, तो मैं बुरी तरह से फंस गया। मैं उनमें से किसी को भी हल नहीं कर सका। क्या आप कृपया कठिनाई बढ़ाने के कुछ प्रश्नों का सुझाव दे सकते हैं, ताकि मुझे विषय पर एक अच्छी समझ मिल सके? प्रश्नों में से एक यह है:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , यह एक ग्रीक प्रतियोगिता-गणित पुस्तक में था और मैंने इसे इस साइट पर भी पाया।

दूसरा सवाल जो मुझे इंटरनेट पर नहीं मिला, इसलिए मैं इसका अनुवाद करूंगा:

समीकरण के समाधान की संख्या ज्ञात कीजिए $x_1+x_2+x_3=100$, अगर हर के लिए $3\ge i\ge1$, xi एक गैर नकारात्मक पूर्णांक है $40\ge x_i$।

मैंने इन दोनों प्रश्नों के समाधान ढूंढ लिए हैं, जिस कारण मैं उन्हें पोस्ट कर रहा हूं, वह है पोस्ट के पाठक को बेहतर समझ देना (जैसा कि टिप्पणियों में बताया गया है), समावेश में किस स्तर के प्रश्न- बहिष्करण सिद्धांत मुझे कठिनाई दे रहा है

Answer 1

दूसरा, अनुवादित, प्रश्न वास्तव में समावेश-बहिष्करण की आवश्यकता नहीं है; यह काफी आसानी से उपयोग किया जाता हैhttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), जो एक और तकनीक अच्छी तरह से सीखने लायक है (यदि आपने पहले से ऐसा नहीं किया है):

चलो लिखते है $u_i=40-x_i$, ताकि प्रतिबंध है $u_i\ge0$, और फिर के रूप में हल करने के लिए समीकरण को फिर से लिखना

$$u_1+u_2+u_3=20$$

(इससे आता है $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, और फिर सामान को इधर-उधर घुमाते हुए।) सितारे और बार अब कहते हैं कि गैर-नकारात्मक त्रिगुणों की संख्या $20$ है

$${22\choose2}={22\cdot21\over2}=231$$

ईमानदार होने के लिए, मुझे लगता है कि मेरे पास समावेश-बहिष्करण का उपयोग करके इस समस्या को हल करने का एक कठिन समय होगा; अगर ऐसा करने का कोई आसान तरीका है तो मैं खुद को देखने में दिलचस्पी लूंगा।

Answer 2

यहाँ दूसरी समस्या के लिए समावेशन-बहिष्करण दृष्टिकोण है, जहाँ $k$ की संख्या है $i\in\{1,2,3\}$ साथ में $x_i \ge 41$: \ start {align} \ sum_ {k = 0} ^ 2 (-1) ^ k \ binom {3} {k} \ binom {100-41k + 3-1} {3-1} & = \ binom { 102} {2} -3 \ binom {61} {2} +3 \ binom {20} {2} \\ & = 5151-3 \ cdot 1830 + 3 \ cdot 190 \\ & = \ color {लाल} {। 231}। \ अंत {align}$$\binom{100-41k+3-1}{3-1}$$ भाग नॉन-नेटिव पूर्णांक समाधानों के सितारों और बार काउंट से आता है $x_1+x_2+x_3=100$ साथ में $x_i \ge 41$ के लिये $k$ निर्दिष्ट $i\in\{1,2,3\}$, समकक्ष, nonnegative पूर्णांक समाधान करने के लिए $y_1+y_2+y_3=100-41k$।