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

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

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

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

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

$|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 เป็นเซตจำกัด แล้ว

$\begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\ & {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le 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{align}$

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

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

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

อ้างอิง

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