[조합론] 포함-배제의 원리(Inclusion-Exclusion Principle)

포함-배제의 원리란?

포함-배제의 원리(Inclusion-Exclusion Principle)란 여러 집합들의 합집합의 크기를 구하는 데 사용하는 공식이다.
포함-배제의 원리는 교집합의 크기로 합집합의 크기를 구하거나, 혹은 그 반대의 경우에 적용할 수 있다.

 

살펴보기

두 집합의 합집합의 크기는 아래와 같은 공식으로 쉽게 구할 수 있다.
$$ | A \cup B | = | A | + | B | - | A \cap B | $$

 

집합의 개수를 하나만 더 늘려보자. 세 집합의 합집합의 크기는 어떻게 구할까?

집합이 세 개일 때의 벤 다이어그램

그림에서 볼 수 있듯이, $ | A | + | B | + | C | $를 하면 교집합 부분이 중복으로 더해진다.
따라서 $ - | A \cap B | - | B \cap C | - | A \cap C | $를 해주어야 하는데, 이렇게 되면 $ | A \cap B \cap C | $가 중복으로 빼진다.

 

위 내용을 토대로 집합이 세 개일 때의 포함-배제 공식을 구해보면 아래와 같다.
$$ | A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | B \cap C | - | A \cap C | +| A \cap B \cap C |$$

 

일반화하기

집합이 $N$개일 때의 포함-배제 공식을 구해보자.

 

집합이 세 개일 때의 식을 말로 풀어보면 아래와 같다.
(집합 1개의 원소의 개수 합) - (집합 2개의 교집합의 원소의 개수 합) + (집합 3개의 교집합의 원소의 개수 합)

 

집합이 $N$개일 때도 크게 다르지 않다.
가능한 교집합들을 모두 살펴보면서 교집합을 이루는 집합의 수가 홀수이면 더해주고, 짝수이면 빼주면 된다.

 

식으로 일반화하면 아래와 같다.

$$ \Bigg| \bigcup_{i=1}^{n}A_i \Bigg| = \sum_{I \subset U}(-1)^{|I|+1} \Bigg| \bigcap_{i \in I}A_i \Bigg| $$

 

놀랍게도 합집합들을 이용해 교집합을 구할 때도 아주 유사한 형태의 공식이 성립한다.

$$ \Bigg| \bigcap_{i=1}^{n}A_i \Bigg| = \sum_{I \subset U}(-1)^{|I|+1} \Bigg| \bigcup_{i \in I}A_i \Bigg| $$

 

구현해보기 (Python/C++)

백준 17436번 소수의 배수 문제를 직접 풀어보자.

 

파이썬에는 itertools 라이브러리의 combinations를 사용해 쉽고 직관적으로 해결할 수 있다.

import math
from itertools import combinations

N, M = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0

for i in range(1, N + 1):
    # arr 중 i개를 뽑는 경우를 모두 순회
    for comb in combinations(arr, i):
        # 교집합 = 수들의 곱으로 나눠 떨어지는 수의 개수
        mul = math.prod(comb)
        result = M // mul
    
        # 홀수개 교집합이면 더하고, 짝수개 교집합이면 빼기
        if i & 1:
            answer += result
        else:
            answer -= result
    
print(answer)

 

C++에서는 비트 마스킹을 이용해 교집합을 만드는 조합을 구할 수 있다.
각 비트에 번호를 부여하고, 해당 비트가 1이면 그 집합을 포함, 0이면 포함하지 않는 방식으로 부분 집합을 구하면 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ll N, M, answer = 0;
    ll i, j;
    cin >> N >> M;
    
    vector<ll> primes(N, 0);
    for(i = 0; i < N; ++i) {
        cin >> primes[i];
    }

    // 모든 교집합 경우 구하기
    for(i = 1; i < (1 << N); ++i) {
        // 교집합 = 수들의 곱으로 나눠 떨어지는 수의 개수
        ll target = 1;
        int count = 0;
        
        for(j = 0; j < N; ++j) {
            if(i & (1 << j)) {
                target *= primes[j];
                count++;
            }
        }

        // 홀수개 교집합이면 더하고, 짝수개 교집합이면 빼기
        if(count & 1) {
            answer += M / target;
        } else {
            answer -= M / target;
        }
    }
    
    cout << answer;
    return 0;
}

 

위 코드들은 교집합이 되는 조합을 구하는 방식만 다를 뿐 기본 로직(포함-배제 원리)은 동일하게 적용된다.

 

간혹 조합을 구할 때 부분 집합이 아닌 순열을 구하는 방식을 사용하는 경우가 있는데, 이 경우 시간 복잡도가$O(2^N)$에서 $O(N!)$으로 급증함에 유의하자.

 

관련 문제 (BOJ)

포함-배제의 원리는 다른 정수론이나 조합론의 이론을 함께 적용해야 문제를 해결할 수 있는 경우가 많다.

이곳에 관련 문제들이 있으니, 문제를 확인해보며 풀 수 있는 문제를 풀어보자.