"포함과 배제의 원리"의 두 판 사이의 차이

2012년 1월 4일 (수) 09:14 판

\(|A\cup B| = |A| + |B| - |A \cap B|\)
\(|A\cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|\)
일반적으로 집합 A의 부분집합 \(A_i\)에 대하여, 다음이 성립한다.
\(\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|\)

(증명)

\(a\in \bigcup_{i=1}^n A_i\) 가 \(A_i\) 들 중 k 개의 집합에 속해 있으면, a 는 우변을 통하여 \(\sum _{l=1}^k (-1)^{l-1} \binom{k}{l}=1\) 번 세어지게 된다. ■

@@ 9번째 줄: / 9번째 줄: @@
 * <math>|A\cup B| = |A| + |B| - |A \cap B|</math>
 * <math>|A\cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|</math>
-*  일반적으로 다음이 성립한다<br>  <br><math>\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|</math><br>
+*  일반적으로 집합 A의 부분집합 <math>A_i</math>에 대하여, 다음이 성립한다.<br><math>\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|</math><br>
@@ 16번째 줄: / 16번째 줄: @@
 <math>a\in \bigcup_{i=1}^n A_i</math> 가 <math>A_i</math> 들 중 k 개의 집합에 속해 있으면, a 는 우변을 통하여 <math>\sum _{l=1}^k (-1)^{l-1} \binom{k}{l}=1</math> 번 세어지게 된다. ■
+<h5>오일러</h5>
+* [[오일러의 totient 함수]]