위키득계정 ↗
과학

뫼비우스 반전 공식

뫼비우스 반전 공식과학
영어
Möbius inversion formula
출발 관계
g(n)=Σ₍d|n₎f(d)
복원식
f(n)=Σ₍d|n₎μ(d)g(n/d)
합의 범위
n의 양의 약수
정수론의 뫼비우스 반전 공식은 약수에 대해 합한 함수에서 원래 함수를 복원하는 공식이다. g(n)=Σ₍d|n₎f(d)이면 f(n)=Σ₍d|n₎μ(d)g(n/d)이며, μ는 뫼비우스 함수다. 두 합 모두 n의 양의 약수를 대상으로 한다.

보통의 누적 합과 차이

g(n)은 1부터 n까지 모든 값을 더한 것이 아니라 n을 나누는 위치의 함수값만 더한 것이다. 예를 들어 g(6)=f(1)+f(2)+f(3)+f(6)이다. 따라서 g(n)−g(n−1)을 계산하는 보통의 차분만으로 f(n)을 얻는 관계와 다르다.

여섯 번째 값 복원

6의 약수는 1, 2, 3, 6이고 뫼비우스 값은 차례로 1, −1, −1, 1이다. 따라서 f(6)=g(6)−g(3)−g(2)+g(1)이다. 각 g를 약수 합으로 풀면 f(1), f(2), f(3)에 해당하는 항이 상쇄되고 f(6)만 남는 것을 확인할 수 있다.

약수 개수의 예

모든 양의 정수 d에서 f(d)=1로 두면 g(n)은 n의 양의 약수 개수다. 반전 공식을 적용하면 약수 개수를 적절한 뫼비우스 가중치로 더해 다시 1을 얻는다. 함수가 특정한 다항식이거나 증가 함수여야만 하는 것은 아니며 출발하는 약수 합 관계를 만족하는지가 핵심이다.

공식 사용의 범위

약수를 d와 n/d로 서로 바꾸어 같은 공식을 다른 모양으로 쓸 수 있다. 다만 합의 범위가 약수인지 배수인지, 함수가 어떤 위치에서 평가되는지 확인해야 한다. 이 공식의 반전은 약수 관계에 따른 합을 되돌린다는 뜻이며 평면 기하학의 원에 대한 반전과는 다른 개념이다.

관련 문서

뫼비우스 함수 / 약수 / 약수의 개수 / 포함배제 원리 / 수열 / 반전 (기하학)