Counting principle part 2 : Inclusion / Exclusion Principle

• Part 1
• Part 3

Inclusion / Exclusion Principle

กฏนี้บางครั้งถูกเรียก Subtract Principle การอธิบายหลักการในเรื่องนี้ด้วยวิธีการของเซตจะทำให้เข้าใจง่ายขึ้น พิจารณาแผนภาพในภาพที่ 1

ภาพที่ 1

พิจารณาที่เซต A (โดยไม่สนใจ B) มีจำนวนสมาชิกเป็น 4 แล้วมาพิจารณาที่เซต B (โดยไม่สนใจ A) มีจำนวนสมาชิกเป็น 3 หากให้สุ่มหยิบของในภาพมา 1 ชิ้น การคำนวณหาจำนวนทางเลือกที่ได้ของมาไม่ซ้ำกันด้วยหลักการ Addition Principle จะได้เป็น $4+3=7$ ดังภาพที่ 2

ภาพที่ 2

สิ่งที่ผิดปรกติในภาพที่ 2 คือ มีรายการซ้ำกัน ดังนั้นจำนวนสิ่งของ(ทางเลือก)ที่เป็นไปได้ทั้งหมดต้องหักที่ซ้ำออกไป 1 รายการ ทำให้ผลลัพธ์สุดท้ายเหลือเพียง 6 รายการ

ดังนั้นการคำนวณที่ถูกต้อง เรายังคงใช้หลักการตาม Addition Principle ได้อยู่ เพื่อให้ได้จำนวนทางเลือกรวมทั้งหมด (inclusion) แต่ต้องนำเอาจำนวนที่ซ้ำกันออก (exclusion / subtract) ไป นำไปสู่ข้อสรุปของ Inclusion/Exclusion Principle ดังนี้

ถ้ามีเหตุการณ์ A มีจำนวนทางเลือกที่จะเกิดขึ้นของแต่ละเหตุการณ์เป็น m และ เหตุการณ์ B มีจำนวนทางเลือกที่จะเกิดขึ้นของแต่ละเหตุการณ์เป็น n จำนวนทางเลือกของการเกิดขึ้นซ้ำกันของ A และ B เป็น p จำนวนทางเลือกที่เป็นไปได้ทั้งหมดของการเกิดของ เหตุการณ์ A หรือ เหตุการณ์ B คือ $m+n-p$

หรืออาจเขียนในรูปแบบที่อิงกับเรื่องเซต

ถ้า A และ B เป็นเซตที่สามารถนับจำนวนสมาชิกได้ (finite set) แล้ว $$|A\cup B|=|A|+|B|-|A\cap B|$$

Addition Principle ใช้การคำนวณเดียวกับ Exclusion/Inclusion Principle เพียงแต่ใช้ในกรณีที่ $|A\cap B|=0$

ตัวอย่าง

สมมุติในการสำรวจความสนใจต่อผลิตภัณฑ์ด้วยการกรอกแบบสอบถาม จำนวนหนึ่ง ผลิตภัณฑ์ที่นำมาทดสอบมี 3 รุ่น คือ A,B และ C หลังจากผู้เข้าร่วมได้ทดสอบตัวผลิตภัณฑ์แล้ว ให้แสดงความสนใจของตัวเองลงในแบบสอบภาม โดยใช้คำตอบเพียง "สนใจ" กับ "ไม่สนใจ" ในผลิตภัณฑ์แต่ละรุ่นและสามารถเลือกแสดงความเห็นได้มากกว่า 1 รุ่น ผลการสำรวจแสดงในตาราง

รุ่นของผลิตภัณฑ์	จำนวนผู้ให้ความสนใจ
A	12
B	5
C	8
A และ B	2
A และ C	6
B และ C	3
A และ B และ C	1

ให้คำนวณหาจำนวนผู้ที่สนใจผลิตภัณฑ์เพียงรุ่นเดียว และจำนวนคนที่ตอบแบบสอบถามทั้งหมด

การคำนวณหาคำตอบที่ต้องการจะนำเอาตัวเลขผู้ที่สนใจใน A,B,C คือ $12+5+8=25$ มาตอบทันทีไม่ได้ เพราะตัวเลขที่เห็นอาจรวมเอาตัวเลขของคนที่สนใจมากกว่า 1 รุ่นปนอยู่ การนำเอา Venn Diagram มาช่วยจะทำให้การคำนวณง่ายขึ้น เริ่มต้นด้วย

จากตารางบอกว่าคนที่สนใจทั้ง A,B และ C มี 1 คน ซึ่งคือพื้นที่ส่วนตรงกลางในแผนภาพ (กรอบสีชมพู)

B และ C มีคนสนใจรวม 3 คน แต่เป็นคนที่สนใจทั้ง A,B,C ไปแล้ว 1 ดังนั้นจะเหลือ 2 คนที่สนใจเพียง B และ C

A และ C มีคนใจรวม 6 คน แต่เป็นคนที่สนใจทั้ง A,B,C ไปแล้ว 1 ดังนั้นจะเหลือ 5 คนที่สนใจเพียง A และ C

A และ B มีคนใจรวม 2 คน แต่เป็นคนที่สนใจทั้ง A,B,C ไปแล้ว 1 ดังนั้นจะเหลือ 1 คนที่สนใจเพียง A และ B

สิ่งที่ได้คือจำนวนคนที่สนใจในผลิตภัณฑ์ทั้ง 3 รุ่นและคนที่สนใจ 2 รุ่นที่ชัดเจนกว่าที่แสดงในตาราง ขั้นตอนต่อไปคือการหาจำนวนคนที่สนใจในผลิตภัณฑ์เพียงรุ่นเดียว

ภาพสุดท้ายแสดงให้เห็นว่าจำนวนคนที่สนใน A อย่างเดียวมี 5 คน สนใจใน B อย่างเดียว 1 คน และไม่มีคนสนใจใน C อย่างเดียวเลย จำนวนคนที่ตอบแบบสอบถามทั้งหมดหาได้จาก $5+5+1+1+1+2=15\text{ คน }$

จากตัวอย่างนี้ นำไปสู่ข้อสรุป

ถ้า A,B และ C เป็นเซตที่สามารถนับจำนวนสมาชิกได้ (finite set) แล้ว $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

ตรวจสอบการคำนวณจากตัวอย่าง $|A\cup B\cup C|=12+5+8-2-6-3+1=15\text{ คน }$