คำถามเกี่ยวกับหลักการรวมและการยกเว้น
วันนี้ฉันได้พบกับหลักการรวมและการยกเว้นเป็นครั้งแรก ฉันเชื่อว่าฉันเข้าใจแล้วอย่างไรก็ตามเมื่อฉันลองไขข้อข้องใจกับคำถามนี้ฉันก็ติดขัดอย่างมาก ฉันไม่สามารถแก้ปัญหาใด ๆ ได้ คุณช่วยแนะนำคำถามเกี่ยวกับความยากที่เพิ่มขึ้นเพื่อที่ฉันจะเข้าใจหัวข้อนี้ได้ดี หนึ่งในคำถามคือคำถามนี้: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$.
ฉันได้พบวิธีแก้ปัญหาสำหรับคำถามทั้งสองนี้แล้วเหตุผลที่ฉันโพสต์ไว้เช่นกันคือเพื่อให้ผู้อ่านโพสต์มีความเข้าใจที่ดีขึ้น (ตามที่ระบุไว้ในความคิดเห็น) ว่าคำถามในการรวมอยู่ในระดับใด - หลักการกีดกันทำให้ฉันลำบาก
คำตอบ
คำถามที่สองแปลแล้วไม่จำเป็นต้องมีการรวม - ยกเว้นจริงๆ ทำได้ค่อนข้างง่ายโดยใช้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$$
พูดตามตรงฉันคิดว่าฉันมีปัญหาอย่างหนักในการแก้ปัญหานี้โดยใช้การยกเว้นการรวม ฉันสนใจที่จะดูว่ามีวิธีง่ายๆหรือไม่
นี่คือแนวทางการยกเว้นการรวมสำหรับปัญหาที่สองโดยที่ $k$ คือจำนวน $i\in\{1,2,3\}$ ด้วย $x_i \ge 41$: \ begin {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 {red} { 231} \ end {} จัด$$\binom{100-41k+3-1}{3-1}$$ ส่วนหนึ่งมาจากจำนวนดาวและแท่งของโซลูชันจำนวนเต็มที่ไม่เป็นค่าลบ $x_1+x_2+x_3=100$ ด้วย $x_i \ge 41$ สำหรับ $k$ ระบุ $i\in\{1,2,3\}$เช่นเดียวกับโซลูชันจำนวนเต็มที่ไม่เป็นค่าลบสำหรับ $y_1+y_2+y_3=100-41k$.