포함배제의 원리

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

1. 개요

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

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

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

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''에 대해 더함으로써 증명된다.

이 원리는 때때로 다음과 같은 형태로 표현된다.^[9] 유한 집합 ''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)^

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)

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

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)^$

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. 증명

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

: $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-난해 그래프 분할 문제에 대한 알고리즘의 기반을 형성하고, 그래프의 색상 다항식 구성에 응용된다.^[11]^[12]
이분 그래프의 완전 매칭: 이분 그래프에서 완전 매칭의 수를 계산하는 데 사용된다.^[13]
전사 함수의 개수: 전사 함수의 개수를 계산하는 데 사용된다.^[14]
금지된 위치가 있는 순열: 특정 위치에 특정 원소가 올 수 없는 제약 조건이 있는 순열의 수를 계산하는 데 사용된다.^[15]
제2종 스털링 수: 집합 분할의 경우의 수를 나타내는 제2종 스털링 수의 명시적 공식을 유도하는 데 사용된다.^[16]
룩 다항식: 룩을 서로 공격할 수 없도록 체스판에 배치하는 방법의 수를 나타내는 룩 다항식을 계산하는 데 사용된다.^[17]
오일러 피 함수: 주어진 수와 서로소인 수의 개수를 나타내는 오일러 피 함수의 공식을 유도하는 데 사용된다.^[18]
디리클레 쌍곡선 방법: 곱셈 함수의 합을 다시 표현하는 데 사용된다.

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-난해 그래프 분할 문제에 대한 알고리즘의 기반을 형성한다.^[11]

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

6. 3. 이분 그래프 완전 매칭

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

6. 4. 전사 함수의 개수

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

:

\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''의 위치에 놓는 속성이라고 하면, 포함배제의 원리를 사용하여 모든 제약 조건을 만족하는 순열의 수를 계산할 수 있다.^[15]

주어진 예에서, 속성 ''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.

^[16]

여기서 ''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라고 하면, 포함배제의 원리에 의해 다음이 성립한다.^[17]

:

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''를 정의하면, 다음은 소인수 분해이다.^[18]

:

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

그러면,^[18]

:

\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)^$

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

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

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

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

참조

_[1] 문헌
_[2] 문헌
_[3] 문헌
_[4] 문헌
_[5] 문헌
_[6] 논문 On the foundations of combinatorial theory I. Theory of Möbius functions
_[7] 문헌
_[8] 문헌
_[9] 문헌
_[10] 문헌
_[11] 문헌
_[12] 문헌
_[13] 문헌
_[14] 문헌
_[15] 문헌
_[16] 문헌
_[17] 문헌
_[18] 문헌
_[19] 문헌
_[20] 저널 On the foundations of combinatorial theory I. Theory of Möbius functions http://www.maths.ed.[...] 1964

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com