포함배제의 원리

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

조합론에서, 포함배제의 원리(包含排除의原理, 영어: 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]

내용[편집]

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

를 집합 크기라고 하자. 두 유한 집합 의 합집합의 크기와 각각의 집합의 크기 사이에는 다음의 관계가 성립한다.

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

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

집합이 두 개인 경우와 마찬가지로 세 개인 경우 세 집합 의 합집합의 크기는 다음과 같이 표현할 수 있다.

마찬가지로 직관적으로 자연스럽게 계산할 수 있다. 4개인 경우도 마찬가지이다. 일반화된 포함과 배제의 원리를 보자.

일반적인 경우[편집]

일반적으로 개의 집합 이 있을 때, 그 합집합의 크기는 다음과 같다.

이 성립한다.

포함배제의 원리는 근접 대수에서의 뫼비우스 반전 공식의 특수한 경우이다. 구체적으로, 개의 집합 이 있을 때, 개의 원소의 집합의 멱집합 (이는 포함 관계에 따라 부분 순서 집합을 이룬다) 위의 근접 대수를 생각한다면, 포함배제의 원리는 그 위의 뫼비우스 반전 공식이다.

응용[편집]

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

집합 가 있을 때 에서 그 자신으로 가는 일대일 대응을 생각해보자. 집합 의 원소 중에서 가 자신에게 가는 일대일 대응의 집합을 라고 하면, 모든 일대일 대응의 개수인 에서 의 개수를 빼면 된다. 포함배제의 원리에 의해 다음이 성립한다.

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

참고 문헌[편집]

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

바깥 고리[편집]