"뫼비우스 반전공식"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
이 항목의 수학노트 원문주소==
Pythagoras0 (토론 | 기여) 잔글 (찾아 바꾸기 – “<h5>” 문자열을 “==” 문자열로) |
Pythagoras0 (토론 | 기여) 잔글 (찾아 바꾸기 – “</h5>” 문자열을 “==” 문자열로) |
||
| 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 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%;">이 항목의 수학노트 원문주소== |
* [[뫼비우스 반전공식]] | * [[뫼비우스 반전공식]] | ||
| 7번째 줄: | 7번째 줄: | ||
| − | ==개요 | + | ==개요== |
| 15번째 줄: | 15번째 줄: | ||
| − | ==뫼비우스 함수 | + | ==뫼비우스 함수== |
* poset <math>V</math>에 대하여 다음 세 조건을 만족시키는 함수 <math>\mu : V\times V \to R</math> (R은 commutative ring with unity) 를 poset의 뫼비우스 함수라 부른다<br><math>\mu(x,x)=1</math><br><math>x<z</math> 일 때, <math>\sum_{x\leq y \leq z} \mu(x,y)=0</math> (또는 <math>\mu(x,z)=-\sum_{x\leq y < z} \mu(x,y)</math><br> 이외의 경우에는 <math>\mu(x,y) = 0</math><br> | * poset <math>V</math>에 대하여 다음 세 조건을 만족시키는 함수 <math>\mu : V\times V \to R</math> (R은 commutative ring with unity) 를 poset의 뫼비우스 함수라 부른다<br><math>\mu(x,x)=1</math><br><math>x<z</math> 일 때, <math>\sum_{x\leq y \leq z} \mu(x,y)=0</math> (또는 <math>\mu(x,z)=-\sum_{x\leq y < z} \mu(x,y)</math><br> 이외의 경우에는 <math>\mu(x,y) = 0</math><br> | ||
| 27번째 줄: | 27번째 줄: | ||
| − | ==뫼비우스 반전공식 | + | ==뫼비우스 반전공식== |
* poset <math>V</math>에 정의된 함수 <math>f : V \to R, g : V \to R</math> 를 생각하자.<br><math>g(x)=\sum_{z \leq x} f(z)</math> 이면 <math>f(x)=\sum_{z \leq x} \mu(z,x)g(z)</math> 가 성립한다.<br> | * poset <math>V</math>에 정의된 함수 <math>f : V \to R, g : V \to R</math> 를 생각하자.<br><math>g(x)=\sum_{z \leq x} f(z)</math> 이면 <math>f(x)=\sum_{z \leq x} \mu(z,x)g(z)</math> 가 성립한다.<br> | ||
| 38번째 줄: | 38번째 줄: | ||
| − | ==응용 | + | ==응용== |
* [[이항계수의 반전공식]] | * [[이항계수의 반전공식]] | ||
| 46번째 줄: | 46번째 줄: | ||
| − | ==포함과 배제의 원리 | + | ==포함과 배제의 원리== |
* [[포함과 배제의 원리]] | * [[포함과 배제의 원리]] | ||
| 80번째 줄: | 80번째 줄: | ||
| − | ==역사 | + | ==역사== |
* M¨obius Inversion Theorem or MIT, Weisner (1935)) | * M¨obius Inversion Theorem or MIT, Weisner (1935)) | ||
| 90번째 줄: | 90번째 줄: | ||
| − | ==메모 | + | ==메모== |
* [http://www.haverford.edu/math/cgreene/posets.html A Mathematica Package for Studying Posets]<br> | * [http://www.haverford.edu/math/cgreene/posets.html A Mathematica Package for Studying Posets]<br> | ||
| 102번째 줄: | 102번째 줄: | ||
| − | ==관련된 항목들 | + | ==관련된 항목들== |
| 108번째 줄: | 108번째 줄: | ||
| − | <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 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%;">수학용어번역== |
* 단어사전<br> | * 단어사전<br> | ||
| 124번째 줄: | 124번째 줄: | ||
| − | ==사전 형태의 자료 | + | ==사전 형태의 자료== |
* http://ko.wikipedia.org/wiki/ | * http://ko.wikipedia.org/wiki/ | ||
| 136번째 줄: | 136번째 줄: | ||
| − | ==리뷰논문, 에세이, 강의노트 | + | ==리뷰논문, 에세이, 강의노트== |
| 144번째 줄: | 144번째 줄: | ||
| − | ==관련논문 | + | ==관련논문== |
* E. A. Bender and J. R. Goldman On the Applications of Mobius Inversion in Combinatorial Analysis www.jstor.org/stable/2319793 | * E. A. Bender and J. R. Goldman On the Applications of Mobius Inversion in Combinatorial Analysis www.jstor.org/stable/2319793 | ||
| 156번째 줄: | 156번째 줄: | ||
| − | ==관련도서 | + | ==관련도서== |
* 도서내검색<br> | * 도서내검색<br> | ||
** http://books.google.com/books?q= | ** http://books.google.com/books?q= | ||
** http://book.daum.net/search/contentSearch.do?query= | ** http://book.daum.net/search/contentSearch.do?query= | ||
2012년 11월 1일 (목) 12:49 판
이 항목의 수학노트 원문주소==
개요
뫼비우스 함수
- poset \(V\)에 대하여 다음 세 조건을 만족시키는 함수 \(\mu : V\times V \to R\) (R은 commutative ring with unity) 를 poset의 뫼비우스 함수라 부른다
\(\mu(x,x)=1\)
\(x<z\) 일 때, \(\sum_{x\leq y \leq z} \mu(x,y)=0\) (또는 \(\mu(x,z)=-\sum_{x\leq y < z} \mu(x,y)\)
이외의 경우에는 \(\mu(x,y) = 0\)
- Z행렬의 역행렬
- 수론적 함수(산술함수, arithmetic function) 의 뫼비우스 함수는 자연수 집합에 약수 관계로 정의되는 poset에 대한 뫼비우스 함수이다
뫼비우스 반전공식
- poset \(V\)에 정의된 함수 \(f : V \to R, g : V \to R\) 를 생각하자.
\(g(x)=\sum_{z \leq x} f(z)\) 이면 \(f(x)=\sum_{z \leq x} \mu(z,x)g(z)\) 가 성립한다.
- 쌍대 공식
\(g(x)=\sum_{z \geq x} f(z)\) 이면 \(f(x)=\sum_{z \geq x} \mu(z,x)g(z)\) 가 성립한다.
응용
포함과 배제의 원리
집합 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|\)
\(\{1,2,\cdots,n\}\) 의 부분집합과 포함관계에 대한 poset 을 생각하자. 뫼비우스 함수는 \(\mu(S,T)=(-1)^{\left|T\setminus S\right|}\) 로 주어진다.
\(f(V)=|\underset{i\in V}{\cap }A_i|\)
\(g(V)=\left|\left\{a\in A \left| a\in A_i\forall i\in V\right.; a\notin A_j\forall j\notin V\right\}\right|\)
\(f(V)=\sum _{V\subseteq T} g(T)\) 이 성립한다.
뫼비우스 반전공식(쌍대)을 적용하면, 다음을 얻는다.
\(|A-\underset{i\in {1,2,\cdots,n}}{\cup }A_i|=g(\emptyset)=\sum _{\emptyset\subseteq T}\mu(\emptyset,T)f(T)=\sum _{T}(-1)^{|T|} f(T)\)
즉
\(|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|)\)
역사
- M¨obius Inversion Theorem or MIT, Weisner (1935))
- http://www.google.com/search?hl=en&tbs=tl:1&q=
- 수학사연표
메모
- A Mathematica Package for Studying Posets
- AN INTRODUCTION TO THE MOEBIUS FUNCTION http://quoll.uwaterloo.ca/mine/Notes/moebius.pdf
- http://www.plu.edu/~edgartj/posetMobius.pdf
- http://www.mth.msu.edu/~sagan/Slides/mfp2.pdf
- Math Overflow http://mathoverflow.net/search?q=
관련된 항목들
수학용어번역==
- 단어사전
- 발음사전 http://www.forvo.com/search/
- 대한수학회 수학 학술 용어집
- 한국통계학회 통계학 용어 온라인 대조표
- 남·북한수학용어비교
- 대한수학회 수학용어한글화 게시판
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/Incidence_algebra
- The Online Encyclopaedia of Mathematics
- NIST Digital Library of Mathematical Functions
- The World of Mathematical Equations
리뷰논문, 에세이, 강의노트
관련논문
- E. A. Bender and J. R. Goldman On the Applications of Mobius Inversion in Combinatorial Analysis www.jstor.org/stable/2319793
- http://www-math.mit.edu/~rstan/pubs/pubfiles/28.pdf
- http://www.jstor.org/action/doBasicSearch?Query=
- http://www.ams.org/mathscinet
- http://dx.doi.org/
관련도서
\(\mu(x,x)=1\)
\(x<z\) 일 때, \(\sum_{x\leq y \leq z} \mu(x,y)=0\) (또는 \(\mu(x,z)=-\sum_{x\leq y < z} \mu(x,y)\)
이외의 경우에는 \(\mu(x,y) = 0\)
\(g(x)=\sum_{z \leq x} f(z)\) 이면 \(f(x)=\sum_{z \leq x} \mu(z,x)g(z)\) 가 성립한다.
\(g(x)=\sum_{z \geq x} f(z)\) 이면 \(f(x)=\sum_{z \geq x} \mu(z,x)g(z)\) 가 성립한다.
- 단어사전
- 발음사전 http://www.forvo.com/search/
- 대한수학회 수학 학술 용어집
- 한국통계학회 통계학 용어 온라인 대조표
- 남·북한수학용어비교
- 대한수학회 수학용어한글화 게시판
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/Incidence_algebra
- The Online Encyclopaedia of Mathematics
- NIST Digital Library of Mathematical Functions
- The World of Mathematical Equations
리뷰논문, 에세이, 강의노트
관련논문
- E. A. Bender and J. R. Goldman On the Applications of Mobius Inversion in Combinatorial Analysis www.jstor.org/stable/2319793
- http://www-math.mit.edu/~rstan/pubs/pubfiles/28.pdf
- http://www.jstor.org/action/doBasicSearch?Query=
- http://www.ams.org/mathscinet
- http://dx.doi.org/