여러 조건 중 하나라도 만족하는 것의 개수를 셀 때, 겹친 부분을 더하고 빼며 정확히 한 번씩 세는 방법이다. ‘아무 조건도 만족하지 않는 것’을 셀 때 특히 유용하다.
핵심 정리
$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$$
일반적으로 $|A_1\cup\cdots\cup A_n|=\sum|A_i|-\sum|A_i\cap A_j|+\sum|A_i\cap A_j\cap A_k|-\cdots$
증명 보기
아이디어. 합집합에 속한 원소 $x$ 하나가 오른쪽에서 정확히 한 번 세어짐을 보인다.
$x$가 정확히 $k$개의 집합에 속한다고 하자 ($k\ge1$). 오른쪽의 첫 합 $\sum|A_i|$에서 $x$는 $k={}_kC_1$번 세어진다. 둘째 합(두 집합의 교집합)에서는 $x$가 속한 $k$개 중 둘을 고르는 ${}_kC_2$번 빠진다. 이런 식으로 전체 횟수는
$${}_kC_1-{}_kC_2+{}_kC_3-\cdots+(-1)^{k+1}{}_kC_k=1-\left({}_kC_0-{}_kC_1+\cdots+(-1)^k{}_kC_k\right)=1-0=1$$
이다. (이항정리에서 $(1-1)^k=0$) 합집합에 속하지 않는 원소는 어디에서도 세어지지 않는다. $\blacksquare$
교란순열
$n$명이 자기 모자를 맡겼다가 무작위로 돌려받을 때 아무도 자기 모자를 받지 못하는 경우의 수를 $D_n$이라 하면
$$D_n=n!\left(1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+\frac{(-1)^n}{n!}\right)$$
이다. $A_i$를 ‘$i$번째 사람이 자기 모자를 받는 배열’이라 하면 $|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)!$이고, 포함-배제로 $n!-{}_nC_1(n-1)!+{}_nC_2(n-2)!-\cdots$를 정리한 것이다. $n$이 커지면 그 확률 $\frac{D_n}{n!}$은 $e^{-1}\approx0.368$에 가까워진다.
예제
- $1$부터 $100$까지 $2,3,5$ 중 어느 것으로도 나누어떨어지지 않는 수: $100-(50+33+20)+(16+10+6)-3=26$
- $D_4=24\left(1-1+\frac12-\frac16+\frac1{24}\right)=9$
확인 문제
$1$부터 $1000$까지의 수 중 $3$, $5$, $7$의 어느 것으로도 나누어떨어지지 않는 수의 개수를 구하시오.
풀이 보기
$|A_3|=333$, $|A_5|=200$, $|A_7|=142$, $|A_{15}|=66$, $|A_{21}|=47$, $|A_{35}|=28$, $|A_{105}|=9$이다. 합집합은 $333+200+142-66-47-28+9=543$이므로 답은 $1000-543=457$이다.
정리
- 더하고 빼고 더하고…: 겹친 원소를 정확히 한 번씩
- 교란순열 $D_n\approx\frac{n!}{e}$
