뫼비우스 반전 공식

위키백과 ― 우리 모두의 백과사전.

수론에서의 뫼비우스 반전 공식( ; Möbius inversion formula)은 다음과 같다. g(n) 과 f(n)이 수론적 함수이며,

g(n)=\sum_{d\mid n}f(d)\quad\mbox{for every integer }n\ge 1

을 만족하면,

f(n)=\sum_{d\mid n}g(d)\mu(n/d)\quad\mbox{for every integer }n\ge 1

이 성립한다. 여기서 μ는 뫼비우스 함수이고, 덧셈은 n의 양의 약수 d 전체에 대해 이루어진다.

fg가 자연수에서 어떤 가환군으로의 함수일 때에도 공식은 성립한다.

포갬(convolution)을 사용하여 공식을 써 보면 다음과 같다.

μ * 1 = ε.

조합론(combinatorics)에서 자주 쓰이는 동치의 진술은 다음과 같다.

F(x)와 G(x)가 구간 [1,∞)에서 복소수로의 함수이고,

G(x) = \sum_{1 \le n \le x}F(x/n)\quad\mbox{ for all }x\ge 1

을 만족하면,

F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)\quad\mbox{ for all }x\ge 1.

이 성립한다.

여기서 합은 x보다 작거나 같은 모든 양의 정수 n에 대해서 이루어진다.