포함-배제의 원리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
집합이 세 개일 때의 포함-배제의 원리를 벤 다이어그램으로 표현한 것

포함-배제의 원리(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을 위와 같이 계산할 수 있다.