"뫼비우스 반전공식"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
 
(사용자 2명의 중간 판 22개는 보이지 않습니다)
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>
+
==개요==
  
−
* [[뫼비우스 반전공식]]
+
  
−
 
+
  
−
 
+
  
−
<h5>개요</h5>
+
==뫼비우스 함수==
  
−
 
+
*  poset <math>V</math>에 대하여 다음 세 조건을 만족시키는 함수 <math>\mu : V\times V \to R</math> (R은 commutative ring with unity) 를 poset의 뫼비우스 함수라 부른다:<math>\mu(x,x)=1</math>:<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> 이외의 경우에는 <math>\mu(x,y) = 0</math>
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
<h5>뫼비우스 함수</h5>
 
−
 
 
−
*  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>
 
 
* Z행렬의 역행렬
 
* Z행렬의 역행렬
 
* [[수론적 함수(산술함수, arithmetic function)]] 의 뫼비우스 함수는 자연수 집합에 약수 관계로 정의되는 poset에 대한 뫼비우스 함수이다
 
* [[수론적 함수(산술함수, arithmetic function)]] 의 뫼비우스 함수는 자연수 집합에 약수 관계로 정의되는 poset에 대한 뫼비우스 함수이다
  
−
 
+
  
−
 
+
  
−
 
+
  
−
<h5>뫼비우스 반전공식</h5>
+
==뫼비우스 반전공식==
  
−
*  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> 를 생각하자.:<math>g(x)=\sum_{z \leq x} f(z)</math> 이면 <math>f(x)=\sum_{z \leq x} \mu(z,x)g(z)</math> 가 성립한다.
 +
* 쌍대 공식:<math>g(x)=\sum_{z \geq x} f(z)</math> 이면 <math>f(x)=\sum_{z \geq x} \mu(z,x)g(z)</math> 가 성립한다.
  
−
 
+
  
−
 
+
  
−
<h5>응용</h5>
+
 +
 
 +
==응용==
  
 
* [[이항계수의 반전공식]]
 
* [[이항계수의 반전공식]]
  
−
 
+
  
−
 
+
  
−
<h5>포함과 배제의 원리</h5>
+
==포함과 배제의 원리==
  
 
* [[포함과 배제의 원리]]
 
* [[포함과 배제의 원리]]
51번째 줄: 46번째 줄:
 
<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>
 
<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>
  
−
 
+
  
−
 
+
  
 
<math>\{1,2,\cdots,n\}</math> 의 부분집합과 포함관계에 대한 poset 을 생각하자. 뫼비우스 함수는 <math>\mu(S,T)=(-1)^{\left|T\setminus S\right|}</math> 로 주어진다.
 
<math>\{1,2,\cdots,n\}</math> 의 부분집합과 포함관계에 대한 poset 을 생각하자. 뫼비우스 함수는 <math>\mu(S,T)=(-1)^{\left|T\setminus S\right|}</math> 로 주어진다.
  
−
 
+
  
 
<math>f(V)=|\underset{i\in V}{\cap }A_i|</math>
 
<math>f(V)=|\underset{i\in V}{\cap }A_i|</math>
65번째 줄: 60번째 줄:
 
<math>f(V)=\sum _{V\subseteq T} g(T)</math> 이 성립한다.
 
<math>f(V)=\sum _{V\subseteq T} g(T)</math> 이 성립한다.
  
−
뫼비우스 반전공식을 적용하면, 다음을 얻는다.
+
뫼비우스 반전공식(쌍대)을 적용하면, 다음을 얻는다.
  
−
<math>|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)</math>
+
<math>|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)</math>
  
−
특별히, <math>A=\underset{i\in {1,2,\cdots,n}}{\cup }A_i</math> 인 경우,
+
즉
  
−
 
+
<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>
  
−
 
+
  
−
<h5>역사</h5>
+
 +
 
 +
==역사==
  
 
* M¨obius Inversion Theorem or MIT, Weisner (1935))
 
* M¨obius Inversion Theorem or MIT, Weisner (1935))
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
−
* [[수학사연표 (역사)|수학사연표]]
+
* [[수학사 연표]]
  
−
 
+
  
−
 
+
  
−
<h5>메모</h5>
+
==메모==
  
 +
* [http://www.haverford.edu/math/cgreene/posets.html A Mathematica Package for Studying Posets]
 
* AN INTRODUCTION TO THE MOEBIUS FUNCTION http://quoll.uwaterloo.ca/mine/Notes/moebius.pdf
 
* AN INTRODUCTION TO THE MOEBIUS FUNCTION http://quoll.uwaterloo.ca/mine/Notes/moebius.pdf
 
* [http://www.plu.edu/%7Eedgartj/posetMobius.pdf http://www.plu.edu/~edgartj/posetMobius.pdf]
 
* [http://www.plu.edu/%7Eedgartj/posetMobius.pdf http://www.plu.edu/~edgartj/posetMobius.pdf]
92번째 줄: 90번째 줄:
 
* 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/
 
* http://ko.wikipedia.org/wiki/
126번째 줄: 124번째 줄:
 
* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
 
* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
  
−
 
+
  
−
 
+
  
−
<h5>리뷰논문, 에세이, 강의노트</h5>
+
==리뷰논문, 에세이, 강의노트==
  
−
 
+
  
−
 
+
  
−
 
+
  
−
<h5>관련논문</h5>
+
==관련논문==
  
 
* 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
146번째 줄: 144번째 줄:
 
* http://dx.doi.org/
 
* 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/Q371133 Q371133]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'incidence'}, {'LEMMA': 'algebra'}]

2021년 2월 17일 (수) 04:43 기준 최신판

개요

뫼비우스 함수

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



역사



메모



관련된 항목들

수학용어번역



사전 형태의 자료



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

관련논문

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'incidence'}, {'LEMMA': 'algebra'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=뫼비우스_반전공식&oldid=52288"