포함배제원리 (Inclusion-Exclusion Principle)

한 줄 정의: 여러 집합의 원소 개수를 더할 때 중복되는 부분을 빼고 다시 더해서 정확한 합집합의 크기를 구하는 원리입니다.

쉽게 풀면

반 학생 중 수학을 좋아하는 학생이 20명, 과학을 좋아하는 학생이 15명이라고 해봅시다. 그렇다고 "수학 또는 과학을 좋아하는 학생"이 35명이라고 단순히 더하면 틀립니다. 둘 다 좋아하는 학생이 있다면 그 학생은 두 번 세어졌기 때문입니다. 그래서 겹치는 인원(교집합)을 한 번 빼줘야 정확한 인원이 나옵니다. 집합이 세 개, 네 개로 늘어나면 이야기가 더 복잡해집니다. 두 개씩 겹치는 부분을 빼다 보면 세 개가 동시에 겹치는 부분이 너무 많이 빠지게 되어, 그 부분을 다시 더해줘야 합니다. 이렇게 "더하고 빼고 다시 더하고"를 번갈아 반복하며 정확한 값을 맞춰가는 방법이 포함배제원리입니다.

왜 중요한가

포함배제원리는 조합론과 확률론에서 여러 사건이나 집합이 겹치는 복잡한 상황을 정확히 세기 위한 가장 기본적인 도구 중 하나이기 때문에, 이산수학 전반에서 다른 정리를 유도하는 출발점으로 자주 쓰입니다. 특히 알고리즘 분석에서는 여러 조건을 만족하는 경우의 수를 세는 문제(예: 정수 분할, 오일러 파이 함수 계산)에 응용되며, 통계학에서는 여러 사건의 합사건 확률을 정확히 구하는 데 필수적입니다. 이 원리를 정확히 이해하지 못하면 중복 계산으로 인한 오류가 후속 계산 전체에 영향을 미칠 수 있습니다.

논문에서는 이렇게 쓰입니다

"세 사건 중 적어도 하나가 발생할 확률은 포함배제원리에 따라 각 사건의 확률을 더한 뒤 쌍별 교집합의 확률을 빼고 세 사건의 교집합의 확률을 다시 더하여 계산하였다."

이 문장은 여러 사건이나 조건이 겹칠 수 있는 상황에서, 단순 합산이 아니라 중복을 정확히 보정한 값을 계산했다는 뜻입니다. 확률론, 조합론, 알고리즘 복잡도 분석 등에서 여러 경우의 수나 확률을 정확히 세기 위한 기초 원리로 인용됩니다.

"그래프 색칠 문제에서 특정 색상 조합을 배제한 경우의 수를 포함배제원리를 이용해 유도하였다."

조합론적 알고리즘 설계에서 제약 조건이 있는 경우의 수를 세는 데 원리를 적용한 사례입니다.

"여러 위험 요인 중 적어도 하나에 노출된 대상자의 비율을 포함배제원리를 통해 정확히 산출하였다."

역학 통계에서 중복 노출을 보정해 위험집단의 크기를 계산하는 데 원리를 응용한 사례입니다.

조금 더 깊게 보면

일반적인 n개 집합에 대한 포함배제원리는 홀수 개씩 겹치는 교집합은 더하고 짝수 개씩 겹치는 교집합은 빼는 형태의 교대합(alternating sum)으로 표현됩니다. 이 원리는 뫼비우스 함수와 관련된 뫼비우스 반전공식으로 일반화될 수 있으며, 정수론에서 오일러 파이 함수를 구하거나 조합론에서 완전순열(교란순열) 개수를 구하는 문제 등 다양한 영역에서 변형된 형태로 다시 등장합니다.

주의할 점

포함배제원리는 집합이 두 개일 때는 "합 빼기 교집합"으로 간단하지만, 집합이 세 개 이상이 되면 짝수 번 겹치는 부분은 빼고 홀수 번 겹치는 부분은 더하는 규칙을 정확히 지켜야 합니다. 이 원리로 셈하는 대상이 결국 순열과 조합에서 다루는 경우의 수라는 점을 함께 이해하면 왜 이런 보정이 필요한지 더 명확해집니다.