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

수학노트
둘러보기로 가기 검색하러 가기
 
(사용자 2명의 중간 판 13개는 보이지 않습니다)
1번째 줄: 1번째 줄:
−
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">이 항목의 수학노트 원문주소</h5>
+
==개요==
  
−
 
+
* <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>
 +
*  일반적으로 집합 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>
 +
* [[뫼비우스 반전공식]] 의 특별한 경우로 이해할 수 있다
 +
 
 +
 +
 
 +
==증명==
 +
 
 +
* 집합 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>
  
−
 
+
(증명)
  
−
<h5>개요</h5>
+
<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> 번 세어지게 된다. ■
  
−
* <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>
 
  
−
 
+
<math>|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|)</math>
  
−
 
+
로 표현되기도 한다
  
−
자연수 n에 대하여,
+
  
−
<math>\sum _{k=1}^n (-1)^{k-1} \binom{n}{k}=1</math> 이 성립한다.
+
==응용==
  
−
 
+
* [[오일러의 totient 함수]]
 +
* [[derangement]]
  
−
 
+
  
−
 
+
  
−
<h5>역사</h5>
+
==역사==
  
−
 
+
  
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
−
* [[수학사연표 (역사)|수학사연표]]
+
* [[수학사 연표]]
  
−
 
+
  
−
 
+
 +
==메모==
  
−
<h5>메모</h5>
+
  
−
 
+
* Math Overflow http://mathoverflow.net/search?q=
  
−
* Math Overflow http://mathoverflow.net/search?q=
+
 +
 
 +
  
−
 
+
==관련된 항목들==
  
−
 
+
* [[뫼비우스 반전공식]]
  
−
<h5>관련된 항목들</h5>
+
  
−
 
+
  
−
 
+
  
−
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">수학용어번역</h5>
+
==수학용어번역==
  
−
*  단어사전<br>
+
*  단어사전
 
** http://translate.google.com/#en|ko|
 
** http://translate.google.com/#en|ko|
 
** http://ko.wiktionary.org/wiki/
 
** http://ko.wiktionary.org/wiki/
−
* 발음사전 http://www.forvo.com/search/
+
* 발음사전 http://www.forvo.com/search/
−
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
+
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 
* [http://www.kss.or.kr/pds/sec/dic.aspx 한국통계학회 통계학 용어 온라인 대조표]
 
* [http://www.kss.or.kr/pds/sec/dic.aspx 한국통계학회 통계학 용어 온라인 대조표]
 
* [http://www.nktech.net/science/term/term_l.jsp?l_mode=cate&s_code_cd=MA 남·북한수학용어비교]
 
* [http://www.nktech.net/science/term/term_l.jsp?l_mode=cate&s_code_cd=MA 남·북한수학용어비교]
−
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
+
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
  
−
 
 
  
−
 
 
  
−
 
+
==사전 형태의 자료==
−
 
 
−
<h5>사전 형태의 자료</h5>
 
  
 
* [http://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8-%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC http://ko.wikipedia.org/wiki/포함-배제의_원리]
 
* [http://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8-%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC http://ko.wikipedia.org/wiki/포함-배제의_원리]
78번째 줄: 86번째 줄:
 
* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
 
* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
  
−
 
+
−
 
 
−
 
 
−
 
 
−
<h5>리뷰논문, 에세이, 강의노트</h5>
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
<h5>관련논문</h5>
 
−
 
 
−
* http://www.jstor.org/action/doBasicSearch?Query=
 
−
* http://www.ams.org/mathscinet
 
−
* http://dx.doi.org/
 
−
 
 
−
 
 
  
−
 
+
  
−
<h5>관련도서</h5>
+
=리뷰논문, 에세이, 강의노트==
  
−
*  도서내검색<br>
+
==메타데이터==
−
** http://books.google.com/books?q=
+
===위키데이터===
−
** http://book.daum.net/search/contentSearch.do?query=
+
* ID : [https://www.wikidata.org/wiki/Q849335 Q849335]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'inclusion'}, {'OP': '*'}, {'LOWER': 'exclusion'}, {'LEMMA': 'principle'}]
 +
* [{'LOWER': 'inclusion'}, {'OP': '*'}, {'LOWER': 'exclusion'}, {'LEMMA': 'principle'}]

2021년 2월 17일 (수) 05:06 기준 최신판

개요

  • \(|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|)\)

로 표현되기도 한다


응용



역사



메모



관련된 항목들




수학용어번역


사전 형태의 자료



리뷰논문, 에세이, 강의노트=

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'inclusion'}, {'OP': '*'}, {'LOWER': 'exclusion'}, {'LEMMA': 'principle'}]
  • [{'LOWER': 'inclusion'}, {'OP': '*'}, {'LOWER': 'exclusion'}, {'LEMMA': 'principle'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=포함과_배제의_원리&oldid=52540"