inclusion–exclusion principle

포함 배제의 원리

집합에서 합의 공식을 n개짜리 합집합으로 일반화한 것이다.

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣

일반적으로 n개의 유한 집합 A1,A2,…,An이 있다고 하자. 그 합집합의 크기는 아래와 같다. (An는 n번째 유한 집합)

부분집합의 개수가 홀수개면 부분 집합에서 교집합을 통해 만들어진 원소의 갯수들에게 +부호를 붙이고 짝수라면 −부호를 붙인다.

|A1∪A2∪A3∪ ... ∪An| =
+ sigma(i: 1 ~ N)Ai
- sigma(i,j:1 <= i <= j <= N)|Ai∩Aj|
+ sigma(i,j,k:1 <= i <= j <= k <= N)|Ai∩Aj∩Ak|
- ...
// ...