포함-배제의 원리

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

조합론에서, 포함-배제의 원리(包含-排除의原理, 영어: inclusion–exclusion principle)는 유한집합들의 합집합의 원소를 세는 기법 중의 하나이다. 조합론에서 널리 쓰이는 근본적인 기법이며, 이에 대하여 조합론자 잔카를로 로타는 다음과 같이 평했다.

유명한 포함-배제의 원리는 이산 확률론과 조합론에서의 열거 문제에서 가장 유용한 기법 가운데 하나이다. 잘 적용하면, 이 원리를 사용하여 수많은 조합론적 문제를 해결할 수 있다.

One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem.

 
[1]

내용[편집]

집합이 두 개인 경우[편집]

|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}

이 성립한다.

응용[편집]

완전순열 개수의 일반항을 구하는 문제를 생각해 보자. 완전순열이란, 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을 위와 같이 계산할 수 있다.

참고 문헌[편집]

  1. (영어) Rota, Gian-Carlo (1964년). On the foundations of combinatorial theory I. Theory of Möbius functions. 《Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete》 2 (4): 340–368. doi:10.1007/BF00531932. Zbl 0121.02406. ISSN 0044-3719.

바깥 고리[편집]