|A∪B∪C|
집합론 · 개념 허브

포함-배제 원리

Inclusion-Exclusion Principle

AD 185419세기 영국 (실베스터)

개념

|A∪B| = |A| + |B| − |A∩B|의 일반화. 여러 집합의 합집합 크기를 겹침을 빼고 더하는 교대 합으로 계산. 조합론의 기본 도구.

한 호흡으로 이해하기

"두 번 센 것을 한 번 빼라." 영어·수학·과학 클럽 가입자 수에서 복수 가입을 정확히 한 번씩만 세는 법. 흩어짐(derangement, 모든 사람이 자기 것 아닌 선물 받기)의 확률이 1/e ≈ 36.8%인 것이 이 원리의 결과.

한눈에 보기

k 사람의 난수 선물 교환

아무도 자기 것이 아닐 확률

n = 2

1/2 = 0.5

n = 3

2/6 ≈ 0.333

n = 4

9/24 = 0.375

n = 5

44/120 ≈ 0.367

n = 10

1334961/10! ≈ 0.3679

n → ∞

1/e ≈ 0.36788

포함-배제 원리가 교대 합 ∑(−1)ᵏ/k!를 만들고 — 이게 e의 테일러 전개 부분이라 1/e로 수렴. 단순한 원리가 e를 부른다.

핵심 식

∣⋃iAi∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+⋯\Big|\bigcup_{i} A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \cdots

|∪Aᵢ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − ⋯

오늘날의 응용

확률·기대값 계산, 데이터베이스 SQL UNION, 멸치성 정리.

MathVoyage 너머로

불러오는 중…