포함배제의 원리

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

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

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

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

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

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

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

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

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

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

따름정리

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

예

완전 순열의 수 

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

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

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

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

이다.

참고 문헌

외부 링크 
 
 

집합론
열거조합론
수학 정리