หลักการเพิ่มเข้าและตัดออก

ใน คณิตศาสตร์เชิงการจัด หลักการเพิ่มเข้าและตัดออก (อังกฤษ: inclusion–exclusion principle) เป็นสมการแสดงความสัมพันธ์ของจำนวนสมาชิกของเซตจำกัดสองเซตที่นำมายูเนียนกัน โดยหากกำหนด A และ B เป็นเซตจำกัดแล้ว

แผนภาพหลักการเพิ่มเข้าและตัดออกสำหรับกรณี 3 เซต

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.\,}$

ความหมายของสมการนี้คือจำนวนสมาชิกของเซตจำกัดสองเซตที่นำมายูเนียนกัน มีค่าเท่ากับผลบวกของจำนวนสมาชิกของเซตทั้งสอง ลบกับจำนวนสมาชิกของอินเตอร์เซกชันของเซตทั้งสอง ในทำนองเดียวกัน สำหรับสามเซต A, B และ C

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.\,}$

สมการนี้สามารถเห็นได้โดยการนับพื้นที่ส่วนต่างๆตามแผนภาพเวนน์-ออยเลอร์ด้านขวา

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

สำหรับกรณีทั่วไปของหลักการนี้ ให้ A₁, ..., A_n เป็นเซตจำกัด แล้ว

${\displaystyle {\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|\end{aligned}}}$

โดย |A| บอกถึงจำนวนสมาชิกของเซต A ชื่อหลักการนี้มีมาจากการที่เพิ่มจำนวนสมาชิกของเซตเข้าไปเกินและตัดส่วนที่เกินทิ้ง

สูตรนี้คิดค้นโดย Abraham de Moivre แต่หนังสือบางเล่มมีการกล่าวถึง Daniel da Silva, เจมส์ โจเซฟ ซิลเวสเตอร์ (Joseph Sylvester) หรือ อ็องรี ปวงกาเร (Henri Poincaré) ในฐานะผู้ร่วมพัฒนาหลักการนี้ด้วย^{[ต้องการอ้างอิง]}

สำหรับกรณีสามเซต A, B, C หลักการเพิ่มเข้าและตัดออกสามารถแสดงโดยแผนภาพเวนน์-ออยเลอร์ตามภาพด้านขวา

อ้างอิง

principle of inclusion-exclusion จาก PlanetMath ภายใต้สัญญาอนุญาตครีเอทีฟคอมมอนส์