Header

  1. View current page

    수학이 알고싶은 중고대딩들을 위한 수학 노트

Springnote Home
Profile_image?t=1256009541&type=big
35 1273

All Pages

Updates

Add to Watch List

뫼비우스 반전공식

Edit
이 항목의 수학노트 원문주소

 

 

개요

 

 

 

뫼비우스 함수

  • 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=
  • 수학사연표

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

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

 

 

 

관련논문

 

 

관련도서

  • 도서내검색

    • http://books.google.com/books?q=
    • http://book.daum.net/search/contentSearch.do?query=

History

Last edited on 01/11/2012 08:31 by 피타고라스

Linked Page

Linked Pages: 5

Comments (0)

You must log in to leave a comment. Please sign in.