포함배제의 원리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

포함-배제의 원리는 유한 측도 공간에서 가측 집합들의 합집합의 측도를 계산하는 데 사용되는 수학적 원리이다. 이 원리는 유한 집합의 원소 개수를 세거나, 사건들의 확률을 계산하는 데에도 적용될 수 있다.

포함-배제의 원리는 두 개 이상의 집합의 합집합의 크기를 계산할 때, 각 집합의 크기를 더하고, 두 집합의 교집합의 크기를 빼는 방식으로 진행된다. 이 과정을 반복하면서, 세 개 이상의 집합의 교집합을 더하고 빼는 과정을 거쳐 최종적으로 합집합의 크기를 계산한다.

이 원리는 다양한 분야에서 활용된다. 예를 들어, 조합론에서 완전 순열의 개수를 계산하거나, 그래프 색칠 문제, 이분 그래프의 완전 매칭 수 계산, 전사 함수의 개수, 금지된 위치가 있는 순열의 수, 제2종 스털링 수, 룩 다항식, 오일러 피 함수, 디리클레 쌍곡선 방법 등 다양한 문제에 적용된다. 또한, 확률론에서 사건들의 합집합의 확률을 계산하는 데에도 사용되며, 본페로니 부등식을 통해 근사적인 값을 구할 수도 있다.

포함배제의 원리

📚 더 읽어볼만한 페이지

수학 정리 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.
수학 정리 - 베이즈 정리
베이즈 정리는 조건부 확률을 계산하는 방법으로, 사건 A가 일어났을 때 사건 B가 일어날 확률과 사건 B가 일어났을 때 사건 A가 일어날 확률 사이의 관계를 나타내며 사전 확률과 가능도를 이용하여 사후 확률을 계산하고 다양한 분야에서 활용된다.
열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 <math>\{1,2,\ldots,n\}</math>의 순열에서 <math>a_i>a_{i+1}</math>인 <math>i</math>가 정확히 <math>m</math>개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

2. 정의

유한 측도 공간 $(X,\mathcal A,\mu)$ 가 주어졌을 때, 포함배제의 원리에 따르면, 임의의 유한 개의 가측 집합 $A_1,\dots,A_n\in\mathcal A$ 에 대하여 다음이 성립한다.
: $\mu(A_1\cup\cdots\cup A_n) = \sum_{i=1}^n\mu(A_i) - \sum_{1\le i$
특히, 2개의 가측 집합 $A,B\in\mathcal A$ 에 대한 포함배제의 원리는 다음과 같다.
: $\mu(A\cup B)=\mu(A)+\mu(B)-\mu(A\cap B)$
3개의 집합 $A,B,C\in\mathcal A$ 에 대한 포함배제의 원리는 다음과 같다.
: $\mu(A\cup B\cup C)=\mu(A)+\mu(B)+\mu(C)-\mu(A\cap B)-\mu(A\cap C)-\mu(B\cap C)+\mu(A\cap B\cap C)$
포함배제의 원리는 근접 대수에서의 뫼비우스 반전 공식의 특수한 경우이다. $n$ 개의 가측 집합 $A_1,\dots,A_n$ 이 있을 때, $n$ 개 원소 집합 $\{1,2,\dots,n\}$ 의 멱집합 $\mathcal P(\{1,2,\dots,n\})$ (포함 관계에 따라 부분 순서 집합을 이룬다) 위의 실수 계수 근접 대수를 생각하면, 포함배제의 원리는 그 위의 뫼비우스 반전 공식의 한 예이다.

숫자 $n$ 을 소인수 집합으로 본다면, 이는 제곱 인수가 없는 자연수에 대한 뫼비우스 반전 공식의 일반화이다. 따라서, A의 모든 부분집합의 부분 순서 집합의 사건 대수에 대한 뫼비우스 반전 공식으로 간주된다.

포함 배제의 원리를 증명하기 위해, X를 $A_1, \dots, A_n$ 의 상위 집합으로 한다. 공식은 먼저 항등식
: $1_{\bigcup A_i}=\sum_i 1_{A_i}-\sum_{i < j}1_{A_i \cap A_j}+ \cdots+ (-1)^{n - 1} 1_{\bigcap A_i}$
을 지시 함수의 변형으로 구하고, 모든 x ∈ X에 대해 더함으로써 증명된다.

이 원리는 때때로 다음과 같은 형태로 표현된다. 유한 집합 S의 멱집합 2^S 위에 정의된 함수 f, g가
: $g(A)=\sum_{B \subseteq A}f(B)$
를 만족한다면,
: $f(A)=\sum_{B\subseteq A}(-1)^{\left|A \setminus B\right|}g(B).$
이 형태는 반순서 집합 2^S의 인접 대수에서 뫼비우스 반전 공식이 된다.

포함-배제의 원리는 드 모르간의 법칙과 결합하여 공통 부분의 원소의 수를 계산하는데 사용될 수 있다.

2.1. 집합의 원소 개수의 경우

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

: $|A_1\cup\cdots\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\le i$

특히, 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$ 의 멱집합 $\mathcal P(X)$ 에 국한시켰을 때 유한 측도를 이루며, 이를 셈측도라고 한다. 집합의 원소 개수에 대한 포함배제의 원리는 셈측도 공간 $(X,\mathcal P(X),||)$ 위의 포함배제의 원리와 같다.

포함-배제의 원리의 일반적인 공식은 유한 집합 $A_1, \dots, A_n$ 에 대해 다음 등식이 성립한다는 것을 나타낸다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.$

thumb

이것은 다음과 같이 간결하게 작성할 수 있다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)$

또는

: $\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.$

요약하면, 유한 집합의 유한 합집합에 있는 원소의 수를 세려면 먼저 개별 집합의 기수를 더한 다음, 최소 두 개의 집합에 나타나는 원소의 수를 빼고, 최소 세 개의 집합에 나타나는 원소의 수를 다시 더한 다음, 최소 네 개의 집합에 나타나는 원소의 수를 빼는 등과 같은 과정을 거친다. 이 과정은 항상 끝나는데, 합집합에 있는 집합의 수보다 많은 수의 집합에 나타나는 원소는 없기 때문이다. (예를 들어, $n = 4$ 이면, $4$ 개 이상의 집합에 나타나는 원소는 있을 수 없다. 즉, 최소 $5$ 개의 집합에 나타나는 원소는 있을 수 없다.)

2.2. 확률의 경우

확률 공간 $(\Omega,\mathcal F,\operatorname{Pr})$ 이 주어졌을 때, 임의의 유한 개의 사건 $A_1,\dots,A_n\in\mathcal F$ 에 대하여, 포함배제의 원리에 따라 다음이 성립한다.

: $\operatorname{Pr}(A_1\cup\cdots A_n)=\sum_{i=1}^n\operatorname{Pr}(A_i)-\sum_{1\le i$

두 개 또는 세 개의 사건이 있는 경우, 포함-배제 원리는 다음과 같다.

: $\operatorname{Pr}(A\cup B)=\operatorname{Pr}(A)+\operatorname{Pr}(B)-\operatorname{Pr}(A\cap B)$
: $\operatorname{Pr}(A\cup B\cup C)=\operatorname{Pr}(A)+\operatorname{Pr}(B)+\operatorname{Pr}(C)-\operatorname{Pr}(A\cap B)-\operatorname{Pr}(A\cap C)-\operatorname{Pr}(B\cap C)+\operatorname{Pr}(A\cap B\cap C)$

본페로니 부등식에 따르면, 위 공식에서 항의 개수를 제한하여 좌변에 대한 상한과 하한을 번갈아 구할 수 있다. 이는 전체 공식을 사용하기에 너무 복잡한 경우에 유용하다.

3. 공식

유한 측도 공간 $(X,\mathcal A,\mu)$ 가 주어졌다고 하자. 포함배제의 원리에 따르면, 임의의 유한 개의 가측 집합 $A_1,\dots,A_n\in\mathcal A$ 에 대하여, 다음이 성립한다.

: $\mu(A_1\cup\cdots\cup A_n) = \sum_{i=1}^n\mu(A_i) - \sum_{1\le i$

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

: $\mu(A\cup B)=\mu(A)+\mu(B)-\mu(A\cap B)$

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

: $\mu(A\cup B\cup C)=\mu(A)+\mu(B)+\mu(C)-\mu(A\cap B)-\mu(A\cap C)-\mu(B\cap C)+\mu(A\cap B\cap C)$

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

: $|A_1\cup\cdots\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\le i$

특히, 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|$

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

: $\operatorname{Pr}(A_1\cup\cdots A_n)=\sum_{i=1}^n\operatorname{Pr}(A_i)-\sum_{1\le i$

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

: $\operatorname{Pr}(A\cap B)=\operatorname{Pr}(A)+\operatorname{Pr}(B)-\operatorname{Pr}(A\cap B)$

: $\operatorname{Pr}(A\cap B\cap C)=\operatorname{Pr}(A)+\operatorname{Pr}(B)+\operatorname{Pr}(C)-\operatorname{Pr}(A\cap B)-\operatorname{Pr}(A\cap C)-\operatorname{Pr}(B\cap C)+\operatorname{Pr}(A\cap B\cap C)$

포함-배제의 원리의 일반적인 공식은 유한 집합 $A_1, \dots, A_n$ 에 대해 다음 등식이 성립한다는 것을 나타낸다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.$

이것은 다음과 같이 간결하게 작성할 수 있다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)$

또는

: $\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.$

포함 배제의 원리와 드 모르간의 법칙을 결합하여, 공통 부분의 원소 수를 계산할 수 있다. $A$ 를 전체 집합, 각 $i$ 에 대해 $A_i \subseteq A$ 로 하고, $\overline{A_i}$ 가 $A$ 에 관한 $A_i$ 의 여집합을 나타내는 것으로 한다. 이 때

: $\left \vert \bigcap_{i=1}^n A_i \right \vert = \overline{\left \vert \bigcup_{i=1}^n \overline{A_i} \right \vert}$

를 얻는다. 이렇게 하여, 공통 부분을 구하는 문제를 합집합을 구하는 문제로 귀착시킬 수 있다.

4. 따름정리

확률론에서, 확률 공간 $(\Omega,\mathcal{F},\mathbb{P})$ 내의 사건 A₁, ..., A_n에 대해, 포함-배제 원리는 다음과 같이 표현된다.

* n = 2일 때:

: $\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)$

* n = 3일 때:

: $\mathbb{P}(A_1\cup A_2\cup A_3)=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)$

* 일반적인 경우:

: $\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i$

이를 닫힌 형식으로 작성하면 다음과 같다.

: $\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{k=1}^n \left((-1)^{k-1}\sum_{I\subseteq\{1,\ldots,n\}\atop |I|=k} \mathbb{P}(A_I)\right)$

여기서 마지막 합은 정확히 k개의 원소를 포함하는 지수 1, ..., n의 모든 부분 집합 I에 대해 계산되며, $A_I:=\bigcap_{i\in I} A_i$ 는 I에 있는 지수를 가진 모든 A_i의 교집합을 나타낸다.

만약 포함-배제의 원리의 확률적 버전에서 교집합 A_I의 확률이 I의 기수(cardinality)에만 의존한다면, 즉 {1, ..., n}의 모든 k에 대해

: $a_k=\mathbb{P}(A_I) \text{ 모든 } I\subset\{1,\ldots,n\} \text{ 에 대해 } |I|=k$

이러한 조건을 만족하는 a_k가 존재한다면, 위 공식은 다음과 같이 단순화된다.

: $\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) =\sum_{k=1}^n (-1)^{k-1}\binom n k a_k$

이는 이항 계수 $\binom nk$ 의 조합론적 해석 때문이다. 예를 들어, 사건 $A_i$ 가 독립적이고 동일하게 분포되어 있다면 모든 i에 대해 $A_i$ = p이고, $a_k = p^k$ 이므로 위의 식은 다음과 같이 단순화된다.

: $\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = 1 - (1-p)^n$

(이 결과는 사건 $A_i$ 의 여집합의 교집합을 고려하여 더 간단하게 유도할 수도 있다.)

일반적인 측도 공간 $(S, \Sigma, \mu)$ 와 유한 측도를 갖는 가측 부분 집합 $A_1, \dots, A_n$ 의 경우에도 유사한 단순화가 가능하다.

점 과정에서 사용되는 또 다른 공식은 다음과 같다. $S$ 를 유한 집합으로 하고, $P$ 를 $S$ 의 임의의 부분 집합이라고 하자. $A$ 가 $S$ 의 임의의 부분 집합일 때,

: $\begin{aligned}\mathbb{P}(P = A) &= \mathbb{P}(P \supset A) - \sum_{j_1 \in S \setminus A} \mathbb{P}(P \supset A \cup {j_1}) \\&+ \sum_{j_1, j_2 \in S \setminus A \ j_1 \ne j_2} \mathbb{P}(P \supset A \cup {j_1, j_2}) + \dots \\&+ (-1)^$

👆

좌우로 밀어서 보기

\mathbb{P}(P \supset S) \\&= \sum_{A \subset J \subset S} (-1)^

👆

좌우로 밀어서 보기

\mathbb{P}(P \supset J)\end{aligned}

이 원리는 때때로 다음과 같은 형태로 표현된다. 유한 집합 S의 멱집합 2^S 위에 정의된 함수 f, g가

:

g(A)=\sum_{B \subseteq A}f(B)

를 만족한다면,

:

f(A)=\sum_{B\subseteq A}(-1)^{\left|A \setminus B\right|}g(B)

이다. 이 형태는 반순서 집합 2^S의 인접 대수에서 뫼비우스 반전 공식이 된다.

본페로니 부등식에 따르면, 포함배제의 원리 공식의 처음 k항의 합은 좌변의 상계와 하계를 교대로 취한다.

:

\begin{align}\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right), \\\Pr\left(\bigcup_i A_i\right) &\ge \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right), \\\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right) + \sum_{i < j

이것은 공식 전체를 다루기 어려울 때 이용된다.

4.1. 부등식

확률공간 $(\Omega,\mathcal F,\operatorname{Pr})$ 에서 임의의 두 사건 $A,B\in\mathcal F$ 에 대하여 다음 부등식이 성립한다.

: $\operatorname{Pr}(A\cap B)\ge\operatorname{Pr}(A)+\operatorname{Pr}(B)-1$

5. 증명

다음과 같은 형식을 사용하여 원리를 표현할 수 있다.

: $g(A)=\sum_{S \subseteq A}f(S)$ 이면, : $f(A)=\sum_{S \subseteq A}(-1)^$

👆

좌우로 밀어서 보기

g(S) 이다.

포함-배제의 원리의 조합론적 버전과 확률론적 버전은 이 식의 예시이다.

\underline{m} = \{1,2,\ldots,m\}

f(\underline{m}) = 0

라고 가정하고, 모든 집합

S

에 대해

S \subsetneq \underline{m}

로 정의하면 다음을 얻는다.

:

f(S)=\left|\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right| \text{ and } f(S) = \mathbb{P} \left(\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right)

g(A)=\left|\bigcap_{i \in \underline{m} \smallsetminus A} A_i\right|, \quad g(\underline{m}) = \left|\bigcup_{i \in \underline{m}} A_i \right| \text{ and } g(A) = \mathbb{P} \left( \bigcap_{i \in \underline{m} \smallsetminus A} A_i \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup_{i \in \underline{m}} A_i\right)

이는

\cap_{i \in \underline{m} \smallsetminus A} A_i

의 원소

a

가 다른

A_i

(

i \in A

인

A_i

)에도 포함될 수 있기 때문이다.

f(\underline{m}) = 0

이므로,

A = \underline{m}

으로 다음을 얻는다.

:

\sum_{\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{|T|-1} g(\underline{m} \smallsetminus T) = \sum_{\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-|S|-1} g(S) = g(\underline{m})

양변을 교환함으로써 포함-배제의 원리의 조합론적 버전과 확률론적 버전을 얻는다.

만약 숫자

n

을 소인수의 집합으로 본다면, 이는 제곱 인수가 없는 자연수에 대한 뫼비우스 반전 공식의 일반화이다. 따라서, A의 모든 부분집합의 부분 순서 집합의 사건 대수에 대한 뫼비우스 반전 공식으로 간주된다.

뫼비우스 반전 공식의 전체 버전의 일반화를 위해 멀티집합으로 일반화되어야 한다. 집합 대신 멀티집합의 경우, 다음과 같이 된다.

:

f(A) = \sum_{S\subseteq A}\mu(A - S) g(S)

여기서

A - S

는

(A - S) \uplus S = A

인 멀티집합이고,

* μ(S) = S가 짝수 기수의 집합(즉, 중복 원소가 없는 멀티집합)인 경우 1.
* μ(S) = S가 홀수 기수의 집합(즉, 중복 원소가 없는 멀티집합)인 경우 −1.
* μ(S) = S가 고유한 멀티집합(즉, S가 중복 원소를 가짐)인 경우 0.

\mu(A - S)

는

A - S

가 집합인 경우에

(-1)^

👆

좌우로 밀어서 보기

와 같다.

집합들의 합집합에 포함된 원소를 하나 선택하고,

A_1, A_2, \dots, A_t

를 그 원소를 포함하는 개별 집합이라고 하자. (t > 0) 이 원소는 식의 좌변에서 정확히 한 번 계산되므로, 우변에서도 정확히 한 번 계산됨을 보여야 한다. 우변에서 0이 아닌 기여는 특정 항의 모든 부분 집합이 선택된 원소를 포함할 때 발생한다. 즉, 모든 부분 집합이

A_1, A_2, \dots, A_t

에서 선택된다. 이 집합 각각에 대해 기여는 1(항에 따라 부호가 바뀜)이므로, 항에 사용된 이러한 부분 집합의 (부호가 있는) 수이다. 그러면 다음을 얻는다.

:

\begin{align}|\{A_i \mid 1 \leqslant i \leqslant t\}| &- |\{A_i \cap A_j \mid 1 \leqslant i < j \leqslant t\}| + \cdots + (-1)^{t+1}|\{A_1 \cap A_2 \cap \cdots \cap A_t\}|  = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t}.\end{align}

이항 정리에 의해,

:

0 = (1-1)^t= \binom{t}{0} - \binom{t}{1} + \binom{t}{2} - \cdots + (-1)^t\binom{t}{t}.

\binom{t}{0} = 1

임을 사용하여 항을 재배열하면,

:

1 = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t},

따라서, 선택된 원소는 식의 우변에서 단 한 번만 계산된다.

5.1. 지시 함수를 이용한 증명

지시 함수(특성 함수)를 사용하여 대수적 증명을 할 수 있다. 집합 X의 부분 집합 S의 지시 함수는 다음과 같다.

: $\begin{align}&\mathbf{1}_S: X \to \{0,1\} \\&\mathbf{1}_S(x) = \begin{cases} 1 & x \in S\\ 0 & x \notin S \end{cases}\end{align}$

$A$ 와 $B$ 가 $X$ 의 두 부분 집합이면 다음이 성립한다.

: $\mathbf{1}_A \cdot\mathbf{1}_B = \mathbf{1}_{A\cap B}.$

A를 집합 A₁, ..., A_n의 합집합 $\bigcup_{i=1}^n A_i$ 로 나타낼 때, 포함-배제 원리를 일반적인 경우에 증명하기 위해 먼저 다음 항등식을 확인한다.

: $\mathbf{1}_A =\sum_{k=1}^n (-1)^{k-1} \sum_{I\subset\{1,\ldots,n\} \atop|I| = k} \mathbf{1}_{A_I}$

여기서 지시 함수에 대해 다음이 성립한다.

: $A_I = \bigcap_{i\in I} A_i.$

다음 함수는 항등적으로 0이다.

: $\left (\mathbf{1}_A-\mathbf{1}_{A_1} \right )\left (\mathbf{1}_A-\mathbf{1}_{A_2} \right )\cdots \left (\mathbf{1}_A-\mathbf{1}_{A_n} \right )=0,$

만약 x가 A에 속하지 않으면, 모든 인수는 0−0 = 0이 된다. 그렇지 않고, x가 어떤 A_m에 속한다면, 해당 m^번째 인수는 1−1=0이 된다. 좌변의 곱을 전개하면 위 식이 도출된다.

집합의 기수를 위한 포함-배제 원리를 증명하기 위해, A₁, ..., A_n의 합집합에 있는 모든 x에 대해 위 식을 합산한다. 확률에서 사용되는 버전을 도출하기 위해, 위 식의 기댓값을 구한다. 일반적으로, μ에 대해 위 식을 르베그 적분한다. 이러한 유도에서는 항상 선형성을 사용한다.

포함-배제의 원리를 일반적으로 증명하기 위해, X를 A₁, ..., A_n의 상위 집합으로 한다. 공식은 먼저 다음 항등식을 지시 함수의 변형으로 구하고,

: $1_{\bigcup A_i}=\sum_i 1_{A_i}-\sum_{i < j}1_{A_i \cap A_j}+ \cdots+ (-1)^{n - 1} 1_{\bigcap A_i}$

모든 x ∈ X에 대해 더함으로써 증명된다.

6. 응용

포함-배제의 원리는 조합론, 정수론, 확률론 등 다양한 분야에서 활용되는 유용한 도구이다. 다음은 그 예시들이다.

* [[교란순열]] (완전 순열): 고정점을 갖지 않는 전단사 함수인 교란순열의 개수를 셀 때 사용된다.
* [[그래프 색칠 문제]]: NP-난해 그래프 분할 문제에 대한 알고리즘의 기반을 형성하고, 그래프의 색상 다항식 구성에 응용된다.
* [[이분 그래프]]의 [[완전 매칭]]: 이분 그래프에서 완전 매칭의 수를 계산하는 데 사용된다.
* [[전사 함수]]의 개수: 전사 함수의 개수를 계산하는 데 사용된다.
* 금지된 위치가 있는 순열: 특정 위치에 특정 원소가 올 수 없는 제약 조건이 있는 순열의 수를 계산하는 데 사용된다.
* [[제2종 스털링 수]]: 집합 분할의 경우의 수를 나타내는 제2종 스털링 수의 명시적 공식을 유도하는 데 사용된다.
* [[룩 다항식]]: 룩을 서로 공격할 수 없도록 체스판에 배치하는 방법의 수를 나타내는 룩 다항식을 계산하는 데 사용된다.
* [[오일러 피 함수]]: 주어진 수와 서로소인 수의 개수를 나타내는 오일러 피 함수의 공식을 유도하는 데 사용된다.
* [[디리클레 쌍곡선 방법]]: 곱셈 함수의 합을 다시 표현하는 데 사용된다.

6.1. 완전 순열의 수 (교란)

$n$ 개의 원소 $\{1,\dots,n\}$ 의 완전 순열의 개수를 구하는 문제를 생각해 보자. $\{1,\dots,n\}$ 의 완전 순열은 임의의 $i\in\{1,\dots,n\}$ 에 대하여, $\sigma(i)\ne i$ 인 순열 $\sigma\in S_n$ 을 뜻한다. 완전 순열의 집합을 $D_n$ 이라고 하고, 각 $i\in\{1,\dots,n\}$ 에 대하여, $i$ 의 위치를 변경하지 않는 순열들의 집합을 다음과 같이 정의한다.

: $A_i=\{\sigma\in S_n\colon \sigma(i)=i\}$

완전 순열의 정의에 따라 $D_n=S_n\setminus(A_1\cup\cdots\cup A_n)$ 이다. 서로 다른 $A_{i_1},\dots,A_{i_k}$ 의 교집합은 $i_1,\dots,i_k$ 를 제외한 $n-k$ 개의 원소들의 순열의 집합과 일대일 대응하므로, 다음이 성립한다.

: $|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)!$

포함배제의 원리에 따라 다음을 얻는다.

: $|A_1\cup\cdots\cup A_n|=\sum_{k=1}^n\left((-1)^{k-1}\sum_{1\le i_1<\cdots$

모든 순열의 개수는 $|S_n|=n!$ 이므로, 모든 완전 순열의 개수는 다음과 같다.

: $|D_n|=|S_n|-|A_1\cup\cdots\cup A_n|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$

이는 n의 서브팩토리얼로도 알려져 있으며, !n으로 표기한다.

예를 들어 1부터 n까지 번호가 매겨진 n장의 카드가 있을 때, m번 카드가 m번째 위치에 있으면 올바른 위치에 있다고 가정한다. 적어도 한 장의 카드가 올바른 위치에 있도록 카드를 섞는 방법의 수 W는 포함-배제의 원리를 통해 다음과 같이 구할 수 있다.

: $W = \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)! = \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}$

올바른 위치에 있는 카드가 없는 순열, 즉 교란의 확률 Q는 다음과 같다.

: $Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!},$

이는 e⁻¹의 테일러 급수 전개의 n + 1 항까지의 절단이다. 따라서 섞인 카드 덱에서 무작위로 순서를 추측할 때 모든 카드의 위치를 틀릴 확률은 약 e⁻¹, 즉 37%이다.

6.2. 그래프 색칠 문제

포함-배제의 원리는 NP-난해 그래프 분할 문제에 대한 알고리즘의 기반을 형성한다.

이 원리는 그래프의 색상 다항식 구성에 응용된다.

6.3. 이분 그래프 완전 매칭

포함-배제 원리를 사용하여 이분 그래프의 완전 매칭 수를 계산할 수 있다.

6.4. 전사 함수의 개수

일반성을 잃지 않고, 집합의 기수(cardinality)만 중요하므로, A = {1, ..., k}이고 B = {1, ..., n}이라고 할 수 있다. S를 A에서 B로 가는 모든 함수의 집합으로 사용하고, B의 각 i에 대해 "함수가 B의 원소 i를 놓친다"(i가 함수의 치역에 없다)는 성질 P_i를 정의하면, 포함-배제의 원리에 의해 A와 B 사이의 전사 함수의 개수는 다음과 같다.

: $\sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.$

6.5. 금지된 위치가 있는 순열

집합 S = {1, ..., n}의 순열에서 S의 각 원소가 특정 위치에 있지 않도록 제한된 경우를 금지된 위치가 있는 순열이라고 한다. 예를 들어, S = {1, 2, 3, 4}일 때, 원소 1은 1 또는 3 위치에 있을 수 없고, 원소 2는 4 위치에 있을 수 없다는 제약 조건이 있는 순열은 다음과 같다: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 및 4321. A_i를 원소 i가 있을 수 없는 위치의 집합으로 두고, 속성 P_i를 순열이 원소 i를 A_i의 위치에 놓는 속성이라고 하면, 포함배제의 원리를 사용하여 모든 제약 조건을 만족하는 순열의 수를 계산할 수 있다.

주어진 예에서, 속성 P₁을 갖는 순열은 12 = 2(3!)개이고, 속성 P₂를 갖는 순열은 6 = 3!개이며, 이 두 원소에 대한 제한이 없으므로 속성 P₃ 또는 P₄를 갖는 순열은 없다. 따라서 제약 조건을 만족하는 순열의 수는 다음과 같다.

:4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.

이 계산에서 마지막 4는 속성 P₁과 P₂를 모두 갖는 순열의 수이다. 이 공식에 대한 다른 비영 기여는 없다.

6.6. 제2종 스털링 수

제2종 스털링 수 S(n,k)는 n개의 원소를 k개의 비어있지 않은 부분집합으로 분할하는 경우의 수를 나타낸다. 제2종 스털링 수에 대한 명시적인 공식은 포함-배제의 원리를 응용하여 얻을 수 있다. 우선 n개의 집합을 k개의 비어있지 않지만 구별 가능한 상자(순서가 있는 비어있지 않은 부분집합)로 분할하는 경우의 수를 센다.

전체 집합을 n-집합을 k개의 (비어 있을 수 있는) 구별 가능한 상자 A₁, A₂, ..., A_k로 분할하는 경우로 두고, 분할 시 상자 A_i를 비어있게 하는 속성을 P_i라고 정의한다. 그러면 포함-배제의 원리에 의해, 다음 공식을 얻는다.

: $S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.$

여기서 k!로 나누는 이유는 k개의 상자가 구별 가능하다는 인위적인 순서를 제거하기 위해서이다.

6.7. 룩 다항식

룩 다항식은 생성함수로, 룩이 서로 공격하지 않도록 체스판 B 위에 놓는 방법의 수를 나타낸다. 체스판 B는 n개의 행과 m개의 열로 이루어진 직사각형 체스판의 칸들의 부분집합이며, 룩을 놓을 수 있는 칸이라고 생각할 수 있다. 룩 다항식 R_B(x)에서 x^k의 계수, r_k(B)는 서로 공격하지 않는 k개의 룩을 체스판 B의 칸에 배치할 수 있는 방법의 수이다.

보완 체스판의 룩 다항식 계수를 사용하여 룩 다항식의 가장 높은 계수를 계산하는 것이 편리할 때가 있다. 일반성을 잃지 않고 n ≤ m이라고 가정할 수 있으므로, 이 계수는 r_n(B)이다. 완전한 n × m 체스판에 서로 공격하지 않는 n개의 룩을 놓는 방법의 수는 폴링 팩토리얼이다.

: $(m)_n = m(m-1)(m-2) \cdots (m-n+1).$

완전한 체스판에 서로 공격하지 않는 n개의 룩을 배치하는 경우에, 체스판 B의 칸에 없는 열 i에 룩이 있는 속성을 P_i라고 하면, 포함배제의 원리에 의해 다음이 성립한다.

: $r_n(B) = \sum_{t=0}^n (-1)^t (m-t)_{n-t} r_t(B').$

6.8. 오일러 피 함수

Euler^영어의 토션트 함수 또는 피 함수 φ(n)는 n과 서로소인 n보다 작거나 같은 양의 정수의 개수를 세는 산술 함수이다. 즉, n이 양의 정수이면, φ(n)은 1 ≤ k ≤ n 범위 내에서 n과 1 이외의 공약수를 가지지 않는 정수 k의 개수이다. 포함배제의 원리는 φ(n)에 대한 공식을 얻는 데 사용된다. S를 {1, ..., n} 집합으로 정의하고, 1 ≤ i ≤ r에 대해 S의 숫자가 소수 p_i로 나누어지는 속성 P_i를 정의하면, 다음은 소인수 분해이다.

: $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.$

그러면,

: $\varphi(n) = n - \sum_{i=1}^r \frac{n}{p_i} + \sum_{1 \leqslant i < j \leqslant r} \frac{n}{p_i p_j} - \cdots = n \prod_{i=1}^r \left (1 - \frac{1}{p_i} \right ).$

6.9. 디리클레 쌍곡선 방법

디리클레 쌍곡선 방법은 적절한 디리클레 컨벌루션

f = g \ast h

를 선택하여 곱셈 함수

f(n)

의 합을 다시 표현하는 방법이다. 다음 합을 고려해 보자.

:

F(n) = \sum_{k=1}^n f(k) = \sum_{k=1}^n \sum_{xy=k}^{} g(x) h(y)

이 합은

x \geq 1

y \geq 1

xy \leq n

에 의해 경계가 정해지는 영역 내의 격자점에 대한 합으로 다시 쓸 수 있다. 이 영역을 두 개의 겹치는 하위 영역으로 나누고, 마지막으로 포함-배제 원리를 사용하여 다음 결과를 얻을 수 있다.

:

F(n) = \sum_{k=1}^n f(k)= \sum_{k=1}^n \sum_{xy=k}^{} g(x)h(y)= \sum_{x=1}^a \sum_{y=1}^{n/x} g(x)h(y) + \sum_{y=1}^b \sum_{x=1}^{n/y} g(x)h(y) - \sum_{x=1}^a \sum_{y=1}^b g(x)h(y).

7. 기타 공식

유한 측도 공간 $(X,\mathcal A,\mu)$ 에서, 임의의 유한 개의 가측 집합 $A_1,\dots,A_n\in\mathcal A$ 에 대해 포함배제의 원리는 다음과 같이 표현된다.

: $\mu(A_1\cup\cdots\cup A_n) = \sum_{i=1}^n\mu(A_i) - \sum_{1\le i$

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

: $\mu(A\cup B)=\mu(A)+\mu(B)-\mu(A\cap B)$

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

: $\mu(A\cup B\cup C)=\mu(A)+\mu(B)+\mu(C)-\mu(A\cap B)-\mu(A\cap C)-\mu(B\cap C)+\mu(A\cap B\cap C)$

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

유한 집합 $A$ 의 원소 개수를 $|A|$ 로 표기할 때, 임의의 유한 개의 유한 집합 $A_1,\dots,A_n$ 에 대한 포함배제의 원리는 다음과 같다.

: $|A_1\cup\cdots\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\le i$

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$ 의 멱집합 $\mathcal P(X)$ 에 국한시켰을 때 유한 측도를 이루며, 이를 셈측도라고 한다. 집합의 원소 개수에 대한 포함배제의 원리는 셈측도 공간 $(X,\mathcal P(X),||)$ 위의 포함배제의 원리와 같다.

포함-배제의 원리의 일반적인 공식은 유한 집합에 대해 다음 등식이 성립함을 나타낸다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.$

이는 다음과 같이 간결하게 작성할 수 있다.

: $\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)$

또는

: $\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.$

thumb

드 모르간의 법칙에 의해, $A_i$ 를 모두 포함하는 유한 전체 집합을 $S$ 라고 하고, $\bar{A_i}$ 를 $S$ 에서 $A_i$ 의 여집합이라고 하면, 다음을 얻는다.

: $\left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S - \bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| - \cdots + (-1)^n |A_1\cap\cdots\cap A_n|.$

포함-배제의 원리는 확률에서도 다음과 같이 사용된다.

: $\Pr\left(\bigcup_i A_i\right)=\sum_i \Pr\left(A_i\right)- \sum_{i < j} \Pr\left(A_i\cap A_j\right)+ \cdots+ (-1)^{n - 1} \Pr\left(\bigcap_i A_i\right)$

본페로니 부등식에 따르면, 이 공식의 처음 k항의 합은 좌변의 상계와 하계를 교대로 취한다.

: $\begin{align}\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right), \\\Pr\left(\bigcup_i A_i\right) &\ge \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right), \\\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right) + \sum_{i < j$

8. 희석된 포함-배제 원리

A₁, ..., A_n을 임의의 집합이라 하고, p₁, ..., p_n을 0과 1 사이의 실수라고 하자. 그러면 {0, ..., n}의 모든 짝수 k에 대해, 지시 함수는 다음 부등식을 만족한다:

: $1_{A_1\cup\cdots\cup A_n} \ge \sum_{j=1}^k (-1)^{j-1}\sum_{1\le i_1<\cdots$

이는 본페로니 부등식의 한 형태로, 포함-배제의 원리에서 항의 개수가 많아 계산이 어려울 때 유용하게 사용될 수 있다.

확률에서도 포함-배제의 원리를 사용할 때 비슷한 부등식을 얻을 수 있다. 본페로니 부등식에 따르면, 포함-배제의 원리 공식의 처음 k항의 합은 좌변의 상계와 하계를 교대로 취한다.

: $\begin{align}\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right), \\\Pr\left(\bigcup_i A_i\right) &\ge \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right), \\\Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right) + \sum_{i < j$

이 부등식은 공식 전체를 계산하기 어려울 때 유용하다.