뫼비우스 반전공식

수학노트
둘러보기로 이동 검색으로 이동

개요

뫼비우스 함수

  • 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>
  • Z행렬의 역행렬
  • 수론적 함수(산술함수, arithmetic function) 의 뫼비우스 함수는 자연수 집합에 약수 관계로 정의되는 poset에 대한 뫼비우스 함수이다




뫼비우스 반전공식

  • 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> 가 성립한다.




응용



포함과 배제의 원리

집합 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>



<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>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|</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|=|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>



역사



메모



관련된 항목들

수학용어번역



사전 형태의 자료



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

관련논문

메타데이터

위키데이터

Spacy 패턴 목록

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