포함배제의 원리

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

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

정의[편집]

유한 측도 공간 가 주어졌다고 하자. 포함배제의 원리에 따르면, 임의의 유한 개의 가측 집합 에 대하여, 다음이 성립한다.

특히, 2개의 가측 집합 에 대한 포함배제의 원리는 다음과 같다.

또한, 3개의 집합 에 대한 포함배제의 원리는 다음과 같다.

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

집합의 원소 개수의 경우[편집]

유한 집합 의 원소 개수는 로 표기한다. 포함배제의 원리에 따르면, 임의의 유한 개의 유한 집합 에 대하여, 다음이 성립한다.

특히, 2개의 집합 또는 3개의 집합의 경우는 각각 다음과 같다.

집합의 원소 개수는 어떤 유한 집합 멱집합 에 국한시켰을 때 유한 측도를 이루며, 이를 셈측도라고 한다. 집합의 원소 개수에 대한 포함배제의 원리는 셈측도 공간 위의 포함배제의 원리와 같다.

확률의 경우[편집]

확률 공간유한 측도 공간이므로, 포함배제의 원리는 유한 개의 사건들의 확률에 대해서도 성립한다. 확률 공간 이 주어졌다고 하자. 포함배제의 원리에 따르면, 임의의 유한 개의 사건 에 대하여, 다음이 성립한다.

2개 또는 3개의 사건의 경우 다음과 같다.

따름정리[편집]

부등식[편집]

확률 공간 이 주어졌다고 하자. 그렇다면, 임의의 두 사건 에 대하여, 다음과 같은 부등식이 성립한다.

[편집]

완전 순열의 수[편집]

개의 원소 완전 순열의 개수를 구하는 문제를 생각해 보자. 완전 순열은 임의의 에 대하여, 순열 을 뜻한다. 완전 순열의 집합을 이라고 하고, 각 에 대하여,

의 위치를 변경하지 않는 순열들의 집합이라고 하자. 그렇다면, 완전 순열의 정의에 따라 이다. 서로 다른 교집합를 제외한 개의 원소들의 순열의 집합과 일대일 대응하므로,

이다. 포함배제의 원리에 따라

이다. 모든 순열의 개수는 이므로, 모든 완전 순열의 개수는

이다.

참고 문헌[편집]

  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. 

외부 링크[편집]