포함-배제의 원리

집합이 세 개일 때의 포함-배제의 원리를 벤 다이어그램으로 표현한 것

포함-배제의 원리(Inclusion-exclusion principle)는 유한집합들의 합집합의 원소를 세는 기법 중의 하나이다.

내용

집합이 두 개인 경우

$|A|$를 집합 $A$의 원소의 개수라고 하면, 두 유한집합 $A, B$의 합집합의 원소의 개수와 각각의 집합의 원소의 개수에는 다음의 관계가 성립한다.

$|A\cup B| = |A| + |B| - |A \cap B|$

이 등식은 각각을 따로 센 후 두 번 센 것들의 수를 빼주는 것이다.

집합이 세 개인 경우

집합이 두 개인 경우와 마찬가지로 세 개인 경우 세 집합 $A, B, C$의 합집합의 원소의 개수는 다음과 같이 표현할 수 있다.

$|A\cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$

마찬가지로 직관적으로 자연스럽게 계산할 수 있다.

일반적인 경우

일반적으로 $n$개의 집합 $A_1, ... , A_n$이 있을 때, 그 합집합의 원소의 개수는 다음과 같다.

$\begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\ & {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right| \end{align}$

이 성립한다.

응용

완전순열(derangement) 개수의 일반항을 구하는 문제를 생각해 보자. 완전순열이란, $k$번째 자리에 $k$가 오지 않도록 1 부터 $n$까지의 수를 나열하는 순열이다. 난순열의 개수를 $D_n$이라고 하자. 예를 들어 $n = 3$일 때, (2,3,1), (3,1,2) 두 경우가 있으므로 $D_3 = 2$이다.

집합 $A = \{1,2, ... \}$가 있을 때 $A$에서 그 자신으로 가는 일대일 대응을 생각해보자. 집합 $A$의 원소 중에서 $k$가 자신에게 가는 일대일 대응의 집합을 $P_k$라고 하면, 모든 일대일 대응의 개수인 $n!$에서 $P_1 \cup \cdots \cup P_n$ 의 개수를 빼면 된다. 포함-배제의 원리에 의해 다음이 성립한다.

$D_n = \sum_{k=0}^{n}(-1)^k {{n}\choose{k}}(n-k)! = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}$

따라서 $D_n$을 위와 같이 계산할 수 있다.