포함과 배제의 원리

개요

• \(|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의 부분집합 \(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\) 번 세어지게 된다. ■

 

\(|A-\underset{i\in {1,2,\cdots,n}}{\cup }A_i|=|A|-(\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|)\)

로 표현되기도 한다

 

응용

• 오일러의 totient 함수
• derangement

 

 

역사

 

• http://www.google.com/search?hl=en&tbs=tl:1&q=
• 수학사 연표

 

 

메모

 

• Math Overflow http://mathoverflow.net/search?q=

 

 

관련된 항목들

• 뫼비우스 반전공식

 

 

 

수학용어번역

• 단어사전
  
  • http://translate.google.com/#en%7Cko%7C
  • http://ko.wiktionary.org/wiki/
• 발음사전 http://www.forvo.com/search/
• 대한수학회 수학 학술 용어집
  
  • http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
• 한국통계학회 통계학 용어 온라인 대조표
• 남·북한수학용어비교
• 대한수학회 수학용어한글화 게시판

사전 형태의 자료

• http://ko.wikipedia.org/wiki/포함-배제의_원리
• http://en.wikipedia.org/wiki/Inclusion–exclusion_principle
• The Online Encyclopaedia of Mathematics
• NIST Digital Library of Mathematical Functions
• The World of Mathematical Equations