포함배제 원리(Inclusion–exclusion principle)

합집합의 크기를 셀 때 각 집합의 크기⁠(cardinality)⁠를 그냥 더하면 겹친 부분을 여러 번 세게 됩니다. 두 번 센 것은 한 번 빼고, 그러다 너무 많이 뺀 세 겹 부분은 다시 더합니다. 원소⁠(element)⁠ 하나가 정확히 한 번씩 세어지도록 부호를 번갈아 붙이는 것입니다.

예로, 1부터 $N =$ 까지의 수 중 어느 것으로도 나누어떨어지지 않는 수를 세어 봅시다.

오른쪽 그림은 수를 한 줄에 고른 소수⁠(prime number)⁠들의 곱만큼(2와 3이면 6개, 2, 3, 5면 $2\cdot3\cdot5 = 30$개) 늘어놓습니다. 그러면 살아남는 수가 세로줄로 나타납니다. 나누어떨어지는지는 그 곱으로 나눈 나머지⁠(remainder)⁠로만 정해지니, 한 줄마다 같은 무늬가 반복되기 때문입니다(모듈러 연산⁠(modular arithmetic)⁠). 30과 서로소⁠(coprime)⁠인(1 말고는 공약수가 없는) 나머지는 1, 7, 11, 13, 17, 19, 23, 29의 8개이고, 비율은 $(1-\tfrac12)(1-\tfrac13)(1-\tfrac15) = \tfrac{8}{30}$입니다. 이 곱셈 공식이 오일러 피 함수⁠(Euler's totient function)⁠의 공식입니다.

같은 셈을 확률⁠(probability)⁠로 바꿔 볼 수 있습니다. 다만 "모든 정수⁠(integer)⁠ 가운데 고르게 하나"를 뽑는 방법은 없으니, 1부터 $N$까지에서 고르게 뽑고 $N$을 키웁니다. 그러면 소수 $p$로 나누어떨어질 확률은 $1/p$에 다가갑니다. 같은 방식으로 두 수를 뽑을 때 서로소일 확률은 $6/\pi^2 \approx 0.608$에 다가갑니다. 모든 소수 $p$에 대해 "둘 다 $p$의 배수⁠(multiple)⁠"인 경우(확률 $1/p^2$)를 포함배제로 끝까지 빼면 곱 $\prod_p (1 - 1/p^2)$이 나오고, 이 곱이 $1/(1 + \tfrac14 + \tfrac19 + \cdots) = 6/\pi^2$이기 때문입니다(바젤 문제⁠, Basel problem⁠). 무한히 많은 소수로 넘어가는 극한⁠(limit)⁠ 단계는 따로 정당화해야 하지만, 결과는 옳습니다.

|A∪B| = |A| + |B| − |A∩B|를 알면 두 집합의 닮은 정도를 재는 자카드 지수⁠(Jaccard index)⁠ J와 다이스 계수⁠(Dice coefficient)⁠ D를 서로 바꿔 계산할 수 있습니다. 식으로는 $J = D/(2 - D)$입니다.

가장 유명한 응용은 교란순열⁠(derangement)⁠입니다. n개를 늘어놓을 때 아무것도 제자리에 있지 않은 순서의 수는 'i번이 제자리에 있다'는 사건⁠(event)⁠들에 포함배제를 쓰면 $n!\,(1 - \tfrac{1}{1!} + \tfrac{1}{2!} - \cdots \pm \tfrac{1}{n!})$이고, 전체에 대한 비율은 $1/e$로 다가갑니다.