포함배제의 원리

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

정의

유한 측도 공간 $(X, 𝒜, μ)$ 가 주어졌다고 하자. 포함배제의 원리에 따르면, 임의의 유한 개의 가측 집합 $A_{1}, \dots, A_{n} \in 𝒜$ 에 대하여, 다음이 성립한다.

μ (A_{1} \cup \dots \cup A_{n}) = \sum_{i = 1}^{n} μ (A_{i}) - \sum_{1 \leq i < j \leq n} μ (A_{i} \cap A_{j}) + \sum_{1 \leq i < j < k \leq n} μ (A_{i} \cap A_{j} \cap A_{k}) - \dots + (- 1)^{n - 1} μ (A_{1} \cap \dots \cap A_{n})

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

μ (A \cup B) = μ (A) + μ (B) - μ (A \cap B)

또한, 3개의 집합 $A, B, C \in 𝒜$ 에 대한 포함배제의 원리는 다음과 같다.

μ (A \cup B \cup C) = μ (A) + μ (B) + μ (C) - μ (A \cap B) - μ (A \cap C) - μ (B \cap C) + μ (A \cap B \cap C)

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

집합의 원소 개수의 경우

유한 집합 $A$ 의 원소 개수는 $| A |$ 로 표기한다. 포함배제의 원리에 따르면, 임의의 유한 개의 유한 집합 $A_{1}, \dots, A_{n}$ 에 대하여, 다음이 성립한다.

| A_{1} \cup \dots \cup A_{n} | = \sum_{i = 1}^{n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} |

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

| A \cup B | = | A | + | B | - | A \cap B |

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

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

확률의 경우

확률 공간은 유한 측도 공간이므로, 포함배제의 원리는 유한 개의 사건들의 확률에 대해서도 성립한다. 확률 공간 $(Ω, ℱ, \Pr)$ 이 주어졌다고 하자. 포함배제의 원리에 따르면, 임의의 유한 개의 사건 $A_{1}, \dots, A_{n} \in ℱ$ 에 대하여, 다음이 성립한다.

\Pr (A_{1} \cup \dots A_{n}) = \sum_{i = 1}^{n} \Pr (A_{i}) - \sum_{1 \leq i < j \leq n} \Pr (A_{i} \cap A_{j}) + \sum_{1 \leq i < j < k \leq n} \Pr (A_{i} \cap A_{j} \cap A_{k}) - \dots + (- 1)^{n - 1} \Pr (A_{1} \cap \dots A_{n})

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

\Pr (A \cap B) = \Pr (A) + \Pr (B) - \Pr (A \cap B)

\Pr (A \cap B \cap C) = \Pr (A) + \Pr (B) + \Pr (C) - \Pr (A \cap B) - \Pr (A \cap C) - \Pr (B \cap C) + \Pr (A \cap B \cap C)

따름정리

부등식

확률 공간 $(Ω, ℱ, \Pr)$ 이 주어졌다고 하자. 그렇다면, 임의의 두 사건 $A, B \in ℱ$ 에 대하여, 다음과 같은 부등식이 성립한다.

\Pr (A \cap B) \geq \Pr (A) + \Pr (B) - 1

예

완전 순열의 수

틀:본문 $n$ 개의 원소 ${1, \dots, n}$ 의 완전 순열의 개수를 구하는 문제를 생각해 보자. ${1, \dots, n}$ 의 완전 순열은 임의의 $i \in {1, \dots, n}$ 에 대하여, $σ (i) \neq i$ 인 순열 $σ \in S_{n}$ 을 뜻한다. 완전 순열의 집합을 $D_{n}$ 이라고 하고, 각 $i \in {1, \dots, n}$ 에 대하여,

A_{i} = {σ \in S_{n} : σ (i) = i}

가 $i$ 의 위치를 변경하지 않는 순열들의 집합이라고 하자. 그렇다면, 완전 순열의 정의에 따라 $D_{n} = S_{n} ∖ (A_{1} \cup \dots \cup A_{n})$ 이다. 서로 다른 $A_{i_{1}}, \dots, A_{i_{k}}$ 의 교집합은 $i_{1}, \dots, i_{k}$ 를 제외한 $n - k$ 개의 원소들의 순열의 집합과 일대일 대응하므로,

| A_{i_{1}} \cap \dots \cap A_{i_{k}} | = (n - k)!

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

| A_{1} \cup \dots \cup A_{n} | = \sum_{k = 1}^{n} ((- 1)^{k - 1} \sum_{1 \leq i_{1} < \dots < i_{k} \leq n} | A_{i_{1}} \cap \dots \cap A_{i_{k}} |) = \sum_{k = 1}^{n} (\binom{n}{k}) (n - k)! = n! \sum_{k = 1}^{n} \frac{(- 1)^{k - 1}}{k!}

이다. 모든 순열의 개수는 $| S_{n} | = n!$ 이므로, 모든 완전 순열의 개수는

| D_{n} | = | S_{n} | - | A_{1} \cup \dots \cup A_{n} | = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}

이다.

각주

틀:각주

틀:서적 인용

외부 링크

포함배제의 원리

목차

정의

집합의 원소 개수의 경우

확률의 경우

따름정리

부등식

예

완전 순열의 수

각주

외부 링크

둘러보기 메뉴

포함배제의 원리

정의

집합의 원소 개수의 경우

확률의 경우

따름정리

부등식

예

완전 순열의 수

각주

외부 링크

둘러보기 메뉴

검색