포함배제 — 두 번 센 것을 도로 빼기

8강과 13강에서 이미 만난 식이 있습니다.

|A ∪ B| = |A| + |B| − |A ∩ B|

이제 집합이 세 개라면 어떻게 될까요? 그냥 다 더하면 두 개씩 겹친 부분을 두 번 세게 되니 빼 줍니다. 그런데 세 개가 모두 겹친 부분은 세 번 더했다가 세 번 빼서 0번이 되어 버려요. 그래서 다시 한 번 더해 줍니다.

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

이렇게 더하고 빼기를 번갈아 하는 것이 포함배제의 원리입니다.

🎮 겹치는 원을 움직여 보세요

각 영역의 개수를 바꿔 가며 더하고 빼는 과정을 단계별로 따라가 보세요. 어느 부분이 몇 번 세어졌는지 색으로 보여 줍니다.

완전순열 — 아무도 자기 것을 받지 못하는 경우

n명이 선물을 교환하는데 아무도 자기가 가져온 선물을 받지 않는 경우의 수를 완전순열(derangement)이라 하고 !n 으로 씁니다. "자기 것을 받는 사람이 있는 경우"를 포함배제로 빼면 구할 수 있어요.

!n = n! (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!)

놀라운 사실 — n이 커지면 !n / n! 이 1/e ≈ 0.368 로 수렴합니다. 사람이 5명이든 500명이든 아무도 자기 것을 안 받을 확률은 약 37%예요.

실전 — 로그에서 조건 여러 개 세기

서버 로그에서 "타임아웃 또는 5xx 또는 재시도"가 있었던 요청 수를 세려면 그냥 더하면 안 됩니다. 한 요청이 세 조건을 모두 만족할 수 있으니까요. SQL로 치면 COUNT(DISTINCT ...)를 써야 하는 이유가 바로 이것입니다.