조합론(combinatorics), 수학(mathematics)의 한 가지에서, 포함–제외 원리(inclusion–exclusion principle)는 두 유한 집합(finite set)의 합집합(union)에서 원소의 숫자를 얻는 익숙한 방법을 일반화하는 세는 기법입니다; 기호적으로 다음처럼 표현됩니다:
\(\quad\)\(|A \cup B| = |A| + |B| - |A \cap B|,\)
여기서 A와 B는 두 유한 집합이고 |S|는 집합 S의 카디널리티(cardinality)를 가리킵니다 (카디널리티는, 만약 집합이 유한(finite)이면, 집합의 원소의 숫자로 여겨질 수 있습니다). 그 공식은 일부 원소가 두 번 세어질 수 있기 때문에 두 집합의 크기의 합이 너무 클 수 있다는 사실을 표현합니다. 두번-세어진 원소는 두 집합의 교집합에 있는 것들이고 그 셈은 교집합(intersection)의 크기를 뺌으로써 수정됩니다.
그 원리는 세 집합의 경우에서 보다 분명하게 보여지며, 집합 A, B 및 C에 대해 다음에 의해 제공됩니다:
\(\quad\)\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.\)
이 공식은 벤 다이어그램(Venn diagram) 그림에서 각 영역이 공식의 오른쪽 변에 포함된 횟수를 셈으로써 검증될 수 있습니다. 이 경우에서, 초과-세어진 원소의 기여를 제거할 때, 세 집합의 서로 교집합에 있는 원소의 숫자가 너무 자주 빼지게 되므로, 정확한 총합을 얻기 위해 다시 더해져야 합니다.
이들 예제의 결과를 일반화하는 것은 포함–제외의 원리를 제공합니다. n 집합의 합집합의 카디널리티를 구하기 위해:
- 집합의 카디널리티를 포함하십시오.
- 쌍별 교집합의 카디널리티를 제외하십시오.
- 세쌍-별 교집합의 카디널리티를 포함하십시오.
- 네쌍-별 교집합의 카디널리티를 제외하십시오.
- 다섯쌍-별 교집합의 카디널리티를 포함하십시오.
- (만약 n이 짝수이면) n-튜플-별 교집합이 포함 또는 (만약 n이 홀수이면) 제외될 때까지, 계속하십시오.
그 이름은 원리가 초과-관대한 포함, 뒤따른 배제로 보상하는 것에 기반을 두고 있다는 아이디어에서 비롯된 것입니다. 이 개념은 아브라암 드 무아브르(Abraham de Moivre) (1718)에 기인한 것으로 공인됩니다; 그러나 그것은 다니엘 다 실바(Daniel da Silva) (1854)의 논문에 처음 나타나고, 나중에 조지프 실베스터(J.J. Sylvester) (1883)의 논문에 나타납니다. 때때로 그 원리는 이들 출판에 기인하여 다 실바 또는 실베스터의 공식으로 참조됩니다. 그 원리는 숫자 이론(number theory)에서 광범위하게 사용되는 체 방법(sieve method)의 예제이고, 비록 르장드르는 이미 1808년에 체 문맥에서 유사한 장치를 사용했을지라도 때때로 체 공식(sieve formula)이라고 참조됩니다.
유한 확률은 확률 공간(probability space)의 카디널리티에 상대적인 셈으로 계산되므로, 포함-제외의 원리의 공식은 집합의 카디널리티가 유한 확률로 대체될 때 유효합니다. 보다 일반적으로, 두 가지 버전의 원리는 측정 이론(measure theory)의 공통 우산 아래에 놓일 수 있습니다.
매우 추상적인 설정에서, 포함–제외의 원리는 특정 행렬의 역의 계산으로 표현될 수 있습니다. 이 역은 특수한 구조를 가지며, 그 원리를 조합론과 관련된 수학 분야에서 극단적으로 가치 있는 기술로 만듭니다. 잔-카를로 로타(Gian-Carlo Rota)가 그것을 말로 옮겼습니다:
- "이산 확률과 조합론적 이론에서 가장 유용한 열거 원리 중 하나는 포함–제외의 유명한 원리입니다. 능숙하게 적용될 때, 이 원리는 많은 조합론적 문제에 대한 해결책을 산출해 왔습니다."
Statement
일반적인 형식에서, 포함–제외의 원리는 유한 집합 \(A_1, \cdots, A_n\)에 대해, 우리는 다음 항등식을 가짐을 말합니다:
\(\quad\)\(\displaystyle \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|.\)\(\quad\)(1)
이것은 다음과 같이 간결하게 쓰여질 수 있습니다:
\(\quad\)\(\displaystyle \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)\)
또는
\(\quad\)\(\displaystyle \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\) 집합에 나타나는 원소는 있을 수 없습니다.)
응용에서, 보완적인 형식에서 표현된 원리를 보는 것이 공통적입니다. 즉, \(S\)를 \(A_i\)의 모두를 포함하는 유한 전체 집합(universal set)으로 놓고 \(\bar{A_i}\)를 \(S\)에서 \(A_i\)의 여집합을 나타내는 것으로 놓으면, 드 모르간의 법칙(De Morgan's laws)에 의해 우리는 다음을 가집니다:
\(\quad\)\(\displaystyle \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|.\)
명제의 또 다른 변형으로서, \(P_1,\cdots, P_n\)을 집합 \(S\)의 원소가 가질 수도 있고 가지지 않을 수도 있는 속성 목록이라고 놓으며, 그런-다음 포함–제외의 원리는 어떤 속성을 가지지 않는 \(S\)의 원소의 숫자를 계산하는 방법을 제공합니다. 단지 \(A_i\)를 \(P_i\) 속성을 가지고 그것의 보완적인 형식에서 그 원리를 사용하는 \(S\)의 원소의 부분집합으로 놓습니다. 이 변형은 제임스 실베스터(James Sylvester)에 기인합니다.
만약 여러분이 (원리의 일반적인 형식에서) 오른쪽에 대한 먼저 \(m<n\) 합을 오직 고려하면, 여러분은 만약 \(m\)이 홀수이면 과대평가를 얻을 것이고 만약 \(m\)이 짝수이면 과소평가될 것임을 주의하십시오.
Examples
Counting integers
포함–제외의 원리의 사용의 간단한 예로서, 다음 질문을 생각해 보십시오:
\(\quad\){1, ..., 100}에서 2, 3 또는 5로 나뉠 수 없는 정수는 몇 개입니까?
S = {1,...,100} 및 2로 나뉘어질 수 있는 \(P_1\) 속성, 3으로 나뉠 수 있는 \(P_2\) 속성과 5로 나뉠 수 있는 \(P_3\) 속성으로 놓습니다. \(A_i\)를 그것의 원소가 속성 \(P_i\)를 가지는 \(S\)의 부분집합으로 놓으면, 우리는 기본 셈에 의해 다음을 가집니다: \(|A_1|=50\), \(|A_2|=33\), 및 \(|A_3|=20\). 6으로 나뉠 수 있는 이들 정수 16, 10으로 나뉘어질 수 있는 10, 15로 나뉘어질 수 있는 6이 있습니다. 마지막으로, 30으로 나뉘어질 수 있는 정수는 단지 3이므로, 2, 3 또는 5의 임의의 것으로 나뉘어질 수 없는 정수의 개수는 다음에 의해 제공됩니다:
\(\quad\)100 − (50 + 33 + 20) + (16 + 10 + 6) - 3 = 26.
Counting derangements
보다 복잡한 예제는 다음입니다.
1에서 n까지 번호-매겨진 n 카드의 한 덱이 있다고 가정합니다. m 번호-매겨진 한 카드가 만약 그것이 덱에서 m번째 카드이면 올바른 위치에 있다고 가정합니다. 적어도 1 카드가 올바른 위치를 갖도록 카드를 섞을 수 있는 몇 가지 방법, W가 있습니까?
올바른 m번째 카드를 갖는 카드의 순서화의 모두인 집합 \(A_m\)을 정의함으로써 시작합니다. 그런-다음 적어도 하나의 카드가 올바른 위치, m을 갖는 순서의 숫자, W는 다음입니다:
\(\quad\)\(\displaystyle W = \left|\bigcup_{m=1}^n A_m\right|.\)
포함–제외의 원리를 적용합니다:
\(\quad\)\(\displaystyle W = \sum_{m_1=1}^n |A_{m_1}| - \sum_{1 \leqslant m_1 < m_2 \leqslant n} |A_{m_1} \cap A_{m_2}| +\cdots + (-1)^{p-1} \sum_{1 \leqslant m_1 < \cdots < m_p \leqslant n} | A_{m_1} \cap \cdots \cap A_{m_p}| + \cdots\)
각 값 \(A_{m_1} \cap \cdots \cap A_{m_p}\)는 올바른 위치에 적어도 p 값 \(m_1,\cdots,m_p\)에서 가지는 섞임의 집합을 나타냅니다. 적어도 p 값에서 올바른 것을 갖는 섞임의 숫자는 \(m\)의 특정 값이 아니라 오직 p에 의존함에 주목하십시오. 예를 들어 올바른 위치에 첫 번째, 세 번째, 열입곱 번째 카드를 가지는 섞임의 숫자는 올바른 위치에 두 번째, 다섯 번째, 열세 번째 카드를 가지는 섞임의 숫자와 같습니다. 그것은 n 카드 중, 3개가 올바른 위치에 있도록 선택된 것이 중요합니다. 따라서, p번째 합계에서 \(\displaystyle {n \choose p}\) 같은 항이 있습니다 (조합(combination)을 참조하십시오).
\(\quad\)\(\displaystyle W = {n \choose 1} |A_1| - {n \choose 2} |A_1 \cap A_2| + \cdots + (-1)^{p-1} {n \choose p} |A_1 \cap \cdots \cap A_p| + \cdots
\)
\(|A_1 \cap \cdots \cap A_p|\)는 정확한 위치에 p 원소를 가지는 순서화의 숫자이며, 이것은 남아있는 n − p 원소의 순서화의 방법의 숫자, 또는 (n − p)!와 같습니다. 따라서 우리는 마침내 다음을 얻습니다:
\(\quad\)\(\begin{align}
W &= {n \choose 1} (n-1)! - {n \choose 2} (n-2)! + \cdots + (-1)^{p-1} {n \choose p} (n-p)! + \cdots\\
&= \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!(n-p)!} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}
\end{align}\)
올바른 위치에 카드가 없는 순열은 교란(derangement)이라고 불립니다. n!을 순열의 총 수로 취하면, 무작위 섞임이 교란을 생성하는 확률 Q는 다음에 의해 제공됩니다:
\(\quad\)\(\displaystyle Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!}, \)
\(e^{-1}\)의 테일러 전개(Taylor expansion)의 n + 1 항에서 자름. 따라서 카드의 섞인 덱에 대해 순서를 추측하고 모든 각 카드에 대한 잘못된 것일 확률은 근사적으로 \(e^{-1}\) 또는 37%입니다.
A special case
위의 교란 예제에서 나타나는 상황은 특별한 주의를 기울일 만큼 자주 발생합니다. 즉, 포함–제외의 원리에 대해 공식에 나타나는 교집합의 크기는 교집합에서 집합의 숫자에 오직 의존하고 어떤 집합이 나타나는지에 의존하지 않습니다. 보다 공식적으로, 만약 다음 교집합이
\(\quad\)\(\displaystyle A_J:=\bigcap_{j\in J} A_j\)
같은 카디널리티, 말하자면 {1, ..., n}의 모든 각 k-원소 부분집합에 대해 \(\alpha_k=|A_j|\)를 가지면, 다음입니다:
\(\quad\)\(\displaystyle \left |\bigcup_{i=1}^n A_i\right| =\sum_{k=1}^n (-1)^{k-1}\binom nk \alpha_k.\)
또는, 보완적 형식에서, 여기서 전체 집합 S는 카디널리티 \(\alpha_0\)를 가지며,
\(\quad\)\(\displaystyle \left |S \setminus \bigcup_{i=1}^n A_i\right| =\sum_{k=0}^n (-1)^{k}\binom nk \alpha_k.\)
A generalization
전체 집합 S의 부분집합 \(A_1,A_2,\cdots,A_n\)의 (반복을 허용하는) 가족이 주어지면, 포함–제외의 원리는 이들 부분집합 중 어떤 것도 없는 S의 원소의 숫자를 계산합니다. 이 개념의 일반화는 이들 세트 중 정확히 일부 고정된 m에 나타나는 S의 원소의 숫자를 계산합니다.
N = [n] = {1,2,...,n}라고 놓습니다. 만약 우리가 \(A_{\emptyset} = S\)를 정의하면, 포함–제외의 원리는 이전 섹션의 표기법을 사용하여 다음과 같이 쓰일 수 있습니다; Ai의 어떤 것도 포함하지 않는 S의 원소의 숫자는 다음입니다:
\(\quad\)\(\displaystyle \sum_{J \subseteq [n]} (-1)^{|J|} |A_J|.\)
만약 I가 인덱스 집합 N의 고정된 부분집합이면, I에서 모든 i에 대해 및 다른 값이 없는 것에 대해 Ai에 속하는 원소의 숫자는 다음입니다:
\(\quad\)\(\displaystyle \sum_{I \subseteq J} (-1)^{|J| - |I|} |A_J|.\)
다음 집합을 정의하십시오:
\(\quad\)\(\displaystyle B_k = A_{I \cup \{ k \}} \text{ for } k \in N \setminus I.\)
우리는 \(B_k\)의 어떤 것에도 없는 원소의 숫자를 찾으며, 이것은, (\(B_\emptyset = A_I\)와 함께) 포함–제외의 원리를 사용하여, 다음입니다:
\(\quad\)\(\displaystyle \sum_{K \subseteq N \setminus I} (-1)^{|K|}|B_K|.\)
\(N \setminus I\)의 부분집합과 \(I\)를 포함하는 \(N\)의 부분집합 사이의 대응 \(K \leftrightarrow J = I \cup K\)는 전단사이고 만약 \(J\)와 \(K\)가 이 맵 아래에서 대응하면 \(B_k = A_j\)이며, 그 결과가 유효함을 나타냅니다.
In probability
확률론(probability)에서, 확률 공간(probability space) \(\scriptstyle(\Omega,\mathcal{F},\mathbb{P})\)에서 사건 \(A_1,\cdots, A_n\)에 대해, 포함–제외 원리는 n = 2에 대해 다음이 됩니다:
\(\quad\)\(\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),\)
n = 3에 대해 다음이 됩니다:
\(\quad\)\(\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)\)
및 일반적으로
\(\quad\)\(\displaystyle \mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i<j}\mathbb{P}(A_i\cap A_j)+\sum_{i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k) + \cdots +(-1)^{n-1} \sum_{i<...<n}\mathbb{P}\left(\bigcap_{i=1}^n A_i\right),\)
이것은 다음처럼 닫힌 형식에서 쓰일 수 있습니다:
\(\quad\)\(\displaystyle \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에 실행되고, 다음은
\(\quad\)\(\displaystyle A_I:=\bigcap_{i\in I} A_i\)
I에서 인덱스를 갖는 모든 그들 \(A_i\)의 교집합을 나타냅니다.
본페르니 부등식(Bonferroni inequalities)에 따르면, 공식에서 첫 번째 항의 합은 교대로 LHS에 대해 위쪽 경계와 아래쪽 경계입니다. 이것은 완전한 공식이 너무 번거로운 경우에서 사용될 수 있습니다.
일반적인 측정 공간(measure space) (S,Σ,μ) 및 유한 집합의 측정-가능(measurable) 부분집합 \(A_1,\cdots, A_n\)에 대해, 위의 항등식은 역시 확률 측정 \(\mathbb{P}\)가 측정 μ에 의해 대체될 때 유지됩니다.
Special case
만약, 포함–제외 원리의 확률론적 버전에서, 교집합 AI의 확률이 I의 카디널리티에 오직 의존하며, {1, ..., n}에서 모든 각 k에 대해 다음을 만족하는 \(a_k\)가 있음을 의미하면,
\(\quad\)\(a_k=\mathbb{P}(A_I) \text{ for every } I\subset\{1,\ldots,n\} \text{ with } |I|=k,\)
위의 공식은 이항 계수(binomial coefficient) \(\scriptstyle\binom nk\)의 조합론적 해석에 기인하여 다음으로 단순화됩니다:
\(\quad\)\(\displaystyle \mathbb{P}\left(\bigcup_{i=1}^n A_i\right) =\sum_{k=1}^n (-1)^{k-1}\binom n k a_k \)
예를 들어, 만약 사건 \(A_i\)가 독립적이고 동일하게 분포(independent and identically distributed)되면, 모든 i에 대해 \(\mathbb{P}(A_i) = p\)이고, 우리는 \(a_k = p^k\)를 가지며, 이 경우에서 위의 표현은 다음으로 단순화됩니다:
\(\quad\)\(\displaystyle \mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = 1 - (1-p)^n. \)
(이 결과는 사건 \(A_i\)의 여의 교집합을 고려함으로써 보다 간단하게 유도될 수 있습니다.)
비슷한 단순화는 일반적인 측정 공간 (S,Σ,μ) 및 유한 측정의 측정-가능 부분집합 \(A_1, \cdots, A_n\)의 경우에서 가능합니다.
Other forms
그 원리는 만약 다음이면
\(\quad\)\(\displaystyle g(A)=\sum_{S \subseteq A}f(S)\)
다음이라고 말하는 형식에서 때때로 명시됩니다:
\(\quad\)\(\displaystyle f(A)=\sum_{S \subseteq A}(-1)^{|A|-|S|}g(S) \qquad (**)\)
조합론적 및 확률론적 버전의 포함–제외 원리는 (**)의 예제입니다.
Proof:
\(S \subsetneq \underline{m}\)를 갖는 모든 집합(sets) \(S\)에 대해, 각각, \(\underline{m} = \{1,2,\ldots,m\}\), \(f(\underline{m}) = 0\), 및 다음을 취하십시오:
\(\quad\)\(\displaystyle f(S)=\left|\bigcap_{i \in \underline{m} \setminus S} A_i \setminus \bigcup_{i \in S} A_i\right| \text{ and } f(S) = \mathbb{P} \left(\bigcap_{i \in \underline{m} \setminus S} A_i \setminus \bigcup_{i \in S} A_i\right)\)
그런-다음 우리는 \(A \subsetneq \underline{m}\)을 갖는 모든 집합 \(A\)에 대해 각각 다음을 얻습니다:
\(\quad\)\(\displaystyle g(A)=\left|\bigcap_{i \in \underline{m} \setminus 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} \setminus A} A_i \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup_{i \in \underline{m}} A_i\right)\)
이것은 \(\cap_{i \in \underline{m} \setminus A} A_i\)의 원소(elements) \(a\)가 마찬가지로 다른 \(A_i\) (\(i \in A\)를 갖는 \(A_i\)) 안에 포함(contained)될 수 있고, \(\cap \setminus \cup\!\text{-}\)공식은 다른 \(A_i\)를 갖는 집합 \(\{A_i \mid i \in \underline{m} \setminus A\}\)의 모든 가능한 확장을 통해 정화하게 실행하며, 만약 \(S\)가 (\(g(A)\)의 정의에서 처럼) \(A\)의 모든 부분집합(subset)을 통해 실행하면, \(a\)의 구성원 동작과 일치하는 집합에 대해 오직 \(a\)를 세기 때문입니다.
\(f(\underline{m}) = 0\)이므로, 우리는 다음과 변을 서로 교환함으로써 \(A = \underline{m}\)를 갖는 (**)로부터 얻습니다:
\(\quad\)\(\displaystyle \sum_{\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{|T|-1} g(\underline{m} \setminus T) = \sum_{\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-|S|-1} g(S) = g(\underline{m})\)
이것으로부터 조합론적 및 확률론적 버전의 포함–제외의 원리가 따릅니다. \(\square\)
만약 우리가 숫자 \(n\)을 그것의 소수 인수의 집합으로 생각하면, (**)는 제곱-없는(square-free) 자연수(natural number)에 대해 뫼비우스 역 공식(Möbius inversion formula)의 일반화입니다. 그러므로, (**)는 A의 모든 부분집합의 부분적으로 순서화 집합의 투사 대수(incidence algebra)에 대해 뫼비우스 역 공식으로 보일 수 있습니다.
뫼비우스 역 공식의 완전한 버전의 일반화에 대해, (**)는 중복집합(multiset)으로 일반화되어야 합니다. 집합 대신에 중복집합에 대해, (**)는 다음이 됩니다:
\(\quad\)\(\displaystyle f(A)=\sum_{S\subseteq A}\mu(A - S)g(S)\qquad(***)\)
여기서 \(A - S\)는 \((A - S) \uplus S = A\)인 것에 대해 중복집합이고, 다음입니다:
- 만약 S가 짝수(even) 카디널리티(cardinality)의 집합 (즉, 이중 원소 없이 중복집합)이면 μ(S) = 1입니다.
- 만약 S가 홀수 카디널리티의 집합 (즉, 이중 원소없이 중복집합)이면 μ(S) = −1입니다.
- 만약 S가 적절한 중복집합이면 (즉, S는 이중 원소를 가지면) μ(S) = 0입니다.
\(\mu(A - S)\)가 \(A - S\)가 집합인 경우에서 (**)의 단지 \((-1)^{|A|-|S|}\)임을 주의하십시오. \(\square\)
Proof of (***):
(***)의 오른쪽 변을 다음으로 대체하십시오:
\(\quad\)\(\displaystyle g(S)=\sum_{T\subseteq S}f(T)\)
\(f(A)\)가 (***)의 양쪽 변에 한번 나타남을 주의하십시오. 따라서 우리는 \(T\subsetneq A\)를 갖는 모든 \(T\)에 대해, 항 \(f(T)\)가 (***)의 오른쪽 변에서 취소됨을 보여야 합니다. 그런 목적으로, \(T\subsetneq A\)를 만족하는 고정된 \(T\)를 취하고 \(a \not\in T\)를 만족하는 임의의 고정된 \(a \in A\)를 취하십시오.
\(A - S\)는 \(T \subseteq S \subseteq A\)를 만족하는 중복집합 \(S\)을 통해 얻어지는 (***)의 오른쪽 변에 대한 \(f(T)\)의 각각 양의(positive) 또는 음의(negative) 출현에 대해 집합이어야 함을 주목하십시오. 이제 \(A - S\)를 만족하는 \(S\)를 통해 얻어지는 (***)의 오른쪽 변에 대한 \(f(T)\)의 각 출현은 \(A - S\)가 \(a\)를 포함하지 않는 것을 만족하는 해당하는 \(S\)를 통해 얻어지는 그것들과 함께 취소되는 \(a\)를 포함하는 집합입니다. 이것은 원하는 결과를 제공합니다.
Applications
포함–제외 원리는 널리 사용되고 그것의 응용의 오직 일부가 여기서 언급될 수 있습니다.
Counting derangements
포함–제외 원리의 잘-알려진 응용은 유한 집합의 모든 교란(derangement)을 세는 조합론적 문제에 대한 것입니다. 집합 A의 교란은 A에서 고정된 점을 가지지 않는 자체로의 전단사(bijection)입니다. 포함–제외 원리를 통해, 우리는 만약 A의 카디널리티가 n이면 교란의 숫자는 [n! / e]이며 여기서 [x]는 x에 가장-가까운 정수(nearest integer)를 나타냅니다; 자세한 증명은 여기에서 볼 수 있고 위의 예제 섹션을 역시 참조하십시오.
교란의 숫자를 세는 문제의 첫 번째 출현은 우연의 게임에 대한 초기 책에 있습니다: 피에르 레몽 드 몽모르(Pierre Raymond de Montmort) (1678 – 1719)에 의한 Essai d'analyse sur les jeux de hazard 및 "Montmort's problem" 또는 그가 "problème des rencontres"라는 이름을 붙였던 문제로 알려져 있습니다. 그 문제는 모자검사 문제라고 역시 알려져 있습니다.
교란의 숫자는 n의 서브팩토리얼(subfactorial)이라고 역시 알려져 있으며, !n로 쓰입니다. 그것은 만약 모든 전단사가 같은 확률로 할당되면 무작위 전단사가 교란일 확률이 n이 증가할 때 빠르게 1/e에 가까워짐을 따릅니다.
Counting intersections
드 모르간의 법칙(De Morgan's law)과 결합된, 포함–제외의 원리는 마찬가지로 집합의 교집합의 카디널리티를 세기 위해 사용될 수 있습니다. \(\overline{A_k}\)가 각 k에 대해 \(A_k \subseteq A\)를 만족하는 어떤 전체 집합 A에 관한 Ak의 여집합을 나타내는 것으로 놓습니다. 그런-다음 우리는 다음을 가집니다:
\(\quad\)\(\displaystyle \bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A_i}}\)
그것에 의하여 교집합을 찾는 문제를 합집합을 찾는 문제로 전환합니다.
Graph coloring
포함–제외 원리는 그래프 색상화와 같은 여러 NP-어려운 그래프 분할 문제에 대한 알고리듬의 기초를 형성합니다.
그 원리의 잘 알려진 응용은 그래프의 색칠 다항식(chromatic polynomial)의 구성입니다.
Bipartite graph perfect matchings
이분 그래프(bipartite graph)의 완벽 일치(perfect matching)의 숫자는 그 원리를 사용하여 계산될 수 있습니다.
Number of onto functions
유한 집합 A와 B가 주어지면, A에서 B로의 몇 개의 전사 함수(surjective function) (위로의 함수)가 있습니까? 임의의 일반성의 손실 없이(Without any loss of generality) 우리는 A = {1, ..., k} 및 B = {1, ..., n}을 취할 수 있는데, 왜냐하면 오직 집합의 카디널리티가 중요하기 때문입니다. S를 A에서 B로의 모든 함수(functions)의 집합으로 사용하고, B에서 각 i에 대해 속성 Pi를 "함수가 B에서 원소 i를 놓치는 것" (i가 함수의 이미지(image) 안에 없음)으로 정의함으로써, 포함–제외의 원리는 A와 B 사이의 위로의 함수의 숫자를 다음과 같이 제공합니다:
\(\quad\)\(\displaystyle \sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.\)
Permutations with forbidden positions
S의 각 원소가 특정 위치에 있지 않도록 제한되는 곳에서 집합 S = {1, ..., n}의 순열(permutation)은 (여기서 순열은 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를 Ai에서 위치에 넣는 속성이라고 놓음으로써, 포함–제외의 원리는 모든 제한을 만족시키는 순열의 숫자를 세기 위해 사용될 수 있습니다.
주어진 예제에서, 속성 \(P_1\)을 갖는 12 = 2(3!) 순열, 속성 \(P_2\)를 갖는 6 = 3! 순열이 있고 속성 \(P_3\) 또는 \(P_4\)를 갖는 순열은 없는데 왜냐하면 이들 두 원소에 대해 제한이 없기 때문입니다. 제한을 만족시키는 순열의 숫자는 따라서 다음입니다:
\(\quad\)4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.
이 계산에서 마지막 4는 속성 \(P_1\)과 \(P_2\) 둘 다를 가지는 순열의 숫자입니다. 공식에 대한 다른 비-영 기여는 없습니다.
Stirling numbers of the second kind
두 번째 종류의 스털링 숫자(Stirling numbers of the second kind), S(n,k)는 n 원소의 집합을 k 비-빈 부분집합 (구분할 수 없는 상자)으로 분할(partitions)의 숫자를 셉니다. 그것들에 대해 명시적인 공식은 매우 밀접하게 관련된 문제, 즉, n-집합을 k 비-빈이지만 구별되는 상자 (순서화된(ordered) 비-빈 부분집합)로의 분할의 숫자에 대한 포함–제외의 원리를 적용함으로써 얻어질 수 있습니다. n-집합을 k (빈 것이 가능한) 구별-가능한 상자, \(A_1,A_2, \cdots, A_k\)로의 모든 분할, 및 분할이 빈 상자 \(A_i\)를 가짐을 의미하는 속성 \(P_i\)로 구성되는 전체 집합을 사용하여, 포함–제외의 원리는 관련된 결과에 대해 답을 제공합니다. 인위적인 순서를 제거하기 위해 k!로 나누면 두 번째 종류의 스털링 숫자를 제공됩니다:
\(\quad\)\(\displaystyle S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.\)
Rook polynomials
루크 다항식은 체스판(checkerboard)의 정사각형의 부분집합처럼 보이는 보드 B에 비-공격하는 루크(rooks)를 배치하는 방법의 숫자의 생성하는 함수(generating function)입니다; 즉, 두 루크가 같은 행 또는 열에 있을 수 없습니다. 보드 B는 n 행과 m 열을 가진 직사각형 보드의 정사각형의 임의의 부분집합입니다; 우리는 그것을 루크를 넣을 수 있는 정사각형이라고 생각합니다. 루크 다항식 \(R_B(x)\)에서 \(x_k\)의 계수(coefficient), \(r_k(B)\)는 k 루크가, 그것들의 어떤 것도 다른 것을 공격하지 않는, B의 정사각형에서 배열될 수 있는 방법의 숫자입니다. 임의의 보드 B에 대해, B에 있지 않는 직사각형 모드의 정사각형으로 구성하는 보완적인 보드 \(B'\)이 있습니다. 이 보완적인 보드는 역시 계수 \(r_k(B')\)을 갖는 루크 다항식 \(R_{B'}(x)\)를 가집니다.
보완적인 보드의 루크 다항식의 계수의 관점에서 루크 다항식의 가장 큰 계수를 계산할 수 있는 것이 때때로 편리합니다. 일반성의 손실 없이, 우리는 n ≤ m이라고 가정할 수 있으므로, 이 계수는 \(r_n(B)\)입니다. 완전한 n × m "체스판" (보드 B의 정사각형에서 루크가 배치되었는지 여부에 관계없이)에 대한 n 비-공격하는 루크를 배치하는 방법의 숫자는 떨어지는 팩토리얼(falling factorial)에 의해 제공됩니다:
\(\quad\)\((m)_n = m(m-1)(m-2) \cdots (m-n+1).\)
Pi를 완전한 보드에 대한 n 비-공격하는 루크의 할당이 보드 B의 정사각형 안에 있지 않는 열 i에 루크를 갖는 속성으로 놓습니다. 그런-다음 포함–제외 원리에 의해, 우리는 다음을 가집니다:
\(\quad\)\(\displaystyle r_n(B) = \sum_{t=0}^n (-1)^t (m-t)_{n-t} r_t(B'). \)
Euler's phi function
오일러의 토션트 또는 피 함수, φ(n)은 n에 상대적으로 소수(relatively prime)인 n보다 작거나 같은 양의 정수의 숫자를 세는 산술 함수(arithmetic function)입니다. 즉, 만약 n이 양의 정수(positive integer)이면, φ(n)은 1이 아닌 n을 갖는 공통 인수를 가지지 않는 범위 1 ≤ k ≤ n에 있는 정수 k의 숫자입니다. 포함–제외의 원리는 φ(n)에 대해 공식을 얻기 위해 사용됩니다. S를 집합 {1, ..., n}으로 놓고 속성 \(P_i\)를 다음의 소수 인수분해(prime factorization)인, 1 ≤ i ≤ r에 대해, S에서 숫자가 소수 \(p_i\)로 나뉠 수 있는 것으로 정의합니다:
\(\quad\)\(n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.\)
그런-다음,
\(\quad\)\(\displaystyle \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 ).\)
Diluted inclusion–exclusion principle
그 원리가 정확한 공식을 제공할 수 있는 많은 경우 (특히, 에라토스테네스의 체(sieve of Eratosthenes)를 사용하여 소수(prime number)를 세는 것)에서, 발생하는 공식은 유용한 내용을 제공하지 않는데 왜냐하면 그것 안에 있는 항의 숫자가 너무 많기 때문입니다. 만약 개별적으로 각 항이 정확하게 추정될 수 있으면, 오차의 누적은 포함–제외 공식이 직접 적용될 수 없음을 의미할 수 있습니다. 숫자 이론(number theory)에서, 이 어려움은 비고 브룬(Viggo Brun)에 의해 해결되었습니다. 천천히 시작한 후, 그의 아이디어는 다른 사람들과 다양한 개발된 체 방법(sieve methods)에 의해 채택되었습니다. 이것들은, 예를 들어, 정확한 공식이 아닌 "체로-친" 집합에 대해 위쪽 경계를 찾으려고 시도할 수 있습니다.
\(A_1,\cdots,A_n\)를 임의의 집합으로 놓고 \(p_1,\cdots, p_n\)을 닫힌 단위 구간 [0,1]에서 실수로 놓습니다. 그런-다음, {0, ..., n}에서 모든 각 짝수 k에 대해, 지시 함수(indicator function)는 다음 부등식을 만족시킵니다:
\(\quad\)\(\displaystyle 1_{A_1\cup\cdots\cup A_n} \ge \sum_{j=1}^k (-1)^{j-1}\sum_{1\le i_1<\cdots<i_j\le n} p_{i_1} \dots p_{i_j} \, 1_{A_{i_1} \cap \cdots \cap A_{i_j}}.\)
Proof of main statement
모든 집합의 합집합에 포함된 한 원소를 선택하고 \(A_1, A_2, \dots, A_t\)를 그것을 포함하는 개별적인 집합으로 놓습니다. (t > 0임을 주목하십시오.) 그 원소는 방정식 (1)의 왼쪽 변에 의해 정확히 한 번 세어지기 때문에, 우리는 오른쪽 변에 의해 정확히 한 번 세어진다는 것을 보여줄 필요가 있습니다. 오른쪽 변에서, 오직 비-영 기여가 특정 항에서 모든 부분집합이 선택된 원소를 포함할 때, 즉, 모든 부분집합이 \(A_1, A_2, \dots, A_t\)로부터 선택될 때 발생합니다. 그 기여는 이들 각 집합에 대해 일 (항에 따라 더하기 또는 빼기)이고 따라서 항에서 사용된 이들 부분집합의 단지 (부호화된) 숫자입니다. 우리는 그런-다음 다음을 가집니다:
\(\quad\)\(\displaystyle \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}\)
\(\quad\)\(\displaystyle 0 = (1-1)^t= \binom{t}{0} - \binom{t}{1} + \binom{t}{2} - \cdots + (-1)^t\binom{t}{t}.\)
\(\displaystyle \binom{t}{0} = 1\)이라는 사실을 사용하고 항을 다시-정렬하여, 우리는 다음을 가집니다:
\(\quad\)\(\displaystyle 1 = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t},\)
그리고 따라서, 선택된 원소는 방정식 (1)의 오른쪽 변에 의해 오직 한 번 셉니다.
Algebraic proof
대수적 증명은 지시 함수(indicator function) (역시 특성 함수라고 알려져 있음)를 사용하여 얻어질 수 있습니다. 집합 X의 부분집합 S의 지시 함수는 다음 함수입니다:
\(\quad\)\(\begin{cases}\mathbf{1}_S: X \to \{0,1\} \\ \mathbf{1}_S(x) = \begin{cases} 1 & x \in S\\ 0 & x \notin S \end{cases}\end{cases}\)
만약 \(A\)와 \(B\)가 \(X\)의 두 부분집합이면, 다음입니다:
\(\quad\)\(\mathbf{1}_A \cdot\mathbf{1}_B = \mathbf{1}_{A\cap B}.\)
A가 집합 \(A_1,\cdots, A_n\)의 합집합 \(\bigcup_{i=1}^n A_i\)를 나타낸다고 놓습니다. 일반적으로 포함–제외 원리를 입증하기 위해, 우리는 지시 함수에 대해 다음 항등식을 검증합니다:
\(\quad\)\(\displaystyle \mathbf{1}_A =\sum_{k=1}^n (-1)^{k-1} \sum_{I\subset\{1,\ldots,n\} \atop|I| = k} \mathbf{1}_{A_I}\)
여기서:
\(\quad\)\(\displaystyle A_I = \bigcap_{i\in I} A_i.\)
다음 함수는
\(\quad\)\(\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 ),\)
동일하게 영인데 왜냐하면: 만약 x가 A 안에 있지 않으면, 모든 인수는 0 − 0 = 0입니다; 그리고 그렇지 않으면, 만약 x가 어떤 \(A_m\)에 속하면, 해당하는 m번째 인수는 1 − 1 = 0입니다. 왼쪽 변에 대한 곱을 전개함으로써, 방정식 (∗)이 따릅니다.
집합의 카디너리티에 대해 포함–제외 원리를 입증하기 위해, \(A_1,\cdots,A_n\)의 합집합에서 모든 x에 걸쳐 방정식 (∗)을 더하십시오. 확률에서 사용된 버전을 유도하기 위해, (∗)에서 기대(expectation)를 취하십시오. 일반적으로, μ에 관한 방정식 (∗)를 적분(integrate)하십시오. 항상 이들 유도에서 선형성을 사용하십시오.
