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

2012년 1월 2일 (월) 18:49 판

\(|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|\)
일반적으로 다음이 성립한다

\(\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><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>
+*  일반적으로 다음이 성립한다<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>
+(증명)
-자연수 n에 대하여,
-<math>\sum _{k=1}^n (-1)^{k-1} \binom{n}{k}=1</math> 이 성립한다.
+<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> 번 세어지게 된다. ■
@@ 47번째 줄: / 43번째 줄: @@
 <h5>관련된 항목들</h5>
+* [[뫼비우스 반전공식]]