หลักการ Combinatorics / Inclusion-excusion

Question

ฉันมีปัญหานี้:

ขายเบเกอรี่ $4$ โดนัทหลากหลายชนิด แต่มีเพียง $6$ ช็อคโกแลตและ $7$ เคลือบ.

เราสามารถซื้อได้กี่วิธี $12$ โดนัทหากการเลือกต้องมีอย่างน้อย $3$ โดนัทเคลือบ (คำสั่งไม่เกี่ยวข้อง)?

ในความพยายามของฉันฉันลบ $3$ เราต้องรวมดาวและแท่งที่ใช้แล้วเพื่อค้นหาจำนวนวิธีที่สมมติว่าทุกอย่างไม่ จำกัด จำนวน: $12-3 = 9$ จุดเติมด้วย $4$ พันธุ์ $= {12\choose9} = 220$ วิธี

จากตรงนี้ฉันคิดว่าเราสามารถลบจำนวนวิธีที่รวมมากกว่าจำนวนที่เรามีได้เช่นวิธีที่มี $7$, $8$, หรือ $9$ ช็อคโกแลตโดนัทและวิธีการที่มี $5$, $6$, $7$, $8$, หรือ $9$ โดนัทเคลือบ

อย่างไรก็ตามฉันไม่แน่ใจว่าวิธีนี้เป็นวิธีที่ดีที่สุดหรือไม่? ฉันไม่เข้าใจจริงๆว่าหลักการรวมและการยกเว้นจะเกี่ยวข้องกับที่ใด

Answer 1

คำถามหมายความว่าอย่างน้อยก็มี $12$ โดนัทของแต่ละพันธุ์อื่น ๆ ที่มีอยู่

หากเราเลือกโดนัทเคลือบสามชิ้นเพื่อเริ่มต้นเราจะต้องเลือกโดนัทอีกเก้าชิ้นจากช็อคโกแลตหกชิ้นเคลือบสี่ชิ้นและไม่ จำกัด จำนวน (สำหรับวัตถุประสงค์ของเรา) จากอีกสองชนิดที่มีให้ จำนวนวิธีที่เราทำได้คือจำนวนคำตอบของสมการ$$a + b + c + g = 9 \tag{1}$$ ในจำนวนเต็มที่ไม่เป็นค่าลบภายใต้ข้อ จำกัด ที่ $c \leq 6$ และ $g \leq 4$.

คำตอบเฉพาะของสมการ 1 สอดคล้องกับตำแหน่งของ $4 - 1 = 3$สัญญาณเพิ่มเติมในแถวที่เก้า ตัวอย่างเช่น$$1 1 1 + 1 1 1 1 + 1 1 +$$ สอดคล้องกับการแก้ปัญหา $a = 3$, $b = 4$, $c = 2$, $g = 0$. จำนวนโซลูชันดังกล่าวคือ$$\binom{9 + 4 - 1}{4 - 1} = \binom{12}{3}$$ เนื่องจากเราต้องเลือกสิ่งที่ $4 - 1 = 3$ ของ $9 + 4 - 1 = 12$ ตำแหน่งที่จำเป็นสำหรับ $9$ คนและ $4 - 1 = 3$ สัญญาณเพิ่มเติมจะเต็มไปด้วยสัญญาณเพิ่มเติมตามที่คุณพบ

จากสิ่งเหล่านี้เราต้องลบจำนวนคำตอบที่ $c > 6$ หรือ $g > 4$. โปรดสังเกตว่าข้อ จำกัด เหล่านี้ไม่สามารถละเมิดได้พร้อมกันตั้งแต่นั้น$7 + 5 = 12 > 9$.

สมมติว่ามีข้อ จำกัด ว่า $c \leq 6$ถูกละเมิด จากนั้นต้องวางช็อกโกแลตโดนัทอย่างน้อยเจ็ดชิ้นลงในกล่อง ปล่อย$c' = c - 7$. แล้ว$c'$เป็นจำนวนเต็มไม่ติดลบ การแทนที่$c' + 7$ สำหรับ $c$ ในสมการที่ 1 ให้ผลตอบแทน \begin{align*} a + b + c' + 7 + g & = 9\\ a + b + c' + g & = 2 \tag{2} \end{align*} สมการ 2 คือสมการในจำนวนเต็มไม่ลบที่มี $$\binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$$ แนวทางแก้ไข

สมมติว่ามีข้อ จำกัด ว่า $g \leq 4$ถูกละเมิด จากนั้นต้องวางโดนัทเคลือบเพิ่มเติมอย่างน้อยห้าชิ้นลงในกล่อง ปล่อย$g' = g - 5$. แล้ว$g'$เป็นจำนวนเต็มไม่ติดลบ การแทนที่$g' + 5$ สำหรับ $g$ ในสมการที่ 1 ให้ผลตอบแทน \begin{align*} a + b + c + g' + 5 & = 9\\ a + b + c + g' & = 4 \tag{3} \end{align*} สมการ 3 คือสมการในจำนวนเต็มไม่ลบที่มี $$\binom{4 + 4 - 1}{4 - 1} = \binom{7}{3}$$ แนวทางแก้ไข

ดังนั้นจำนวนวิธีในการเลือก $12$ โดนัทซึ่งมีเคลือบอย่างน้อยสามชนิดจากสี่พันธุ์โดยมีข้อ จำกัด ว่ามีเพียงช็อกโกแลตหกชิ้นและโดนัทเคลือบเจ็ดชิ้นเท่านั้น $$\binom{12}{3} - \binom{5}{3} - \binom{7}{3}$$