"포함과 배제의 원리"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
| 10번째 줄: | 10번째 줄: | ||
* <math>|A\cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|</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> | ||
* 일반적으로 집합 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> | * 일반적으로 집합 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> | ||
| + | |||
| + | * [[뫼비우스 반전공식]] 의 특별한 경우로 이해할 수 있다 | ||
| + | |||
| + | <h5>증명</h5> | ||
| + | |||
| + | * 집합 A의 부분집합 <math>A_i</math>에 대하여, 다음이 성립한다 | ||
| + | |||
| + | <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> | ||
(증명) | (증명) | ||
| 19번째 줄: | 27번째 줄: | ||
| − | + | <h5>응용</h5> | |
| − | |||
| − | |||
| − | |||
| − | <h5> | ||
* [[오일러의 totient 함수]] | * [[오일러의 totient 함수]] | ||
| + | * [[derangement]] | ||
2012년 1월 4일 (수) 15:57 판
이 항목의 수학노트 원문주소
개요
- \(|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\) 번 세어지게 된다. ■
응용
역사
메모
- Math Overflow http://mathoverflow.net/search?q=
관련된 항목들
수학용어번역
- 단어사전
- 발음사전 http://www.forvo.com/search/
- 대한수학회 수학 학술 용어집
- 한국통계학회 통계학 용어 온라인 대조표
- 남·북한수학용어비교
- 대한수학회 수학용어한글화 게시판
사전 형태의 자료
- 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
리뷰논문, 에세이, 강의노트
관련논문