メビウスの反転公式
The statement of the general Möbius inversion formula was first given independently by Weisner (1935) and Philip Hall (1936); both authors were motivated by group theory problems. Neither author seems to have been aware of the combinatorial implications of his work and neither developed the theory of Möbius functions. In a fundamental paper on Möbius functions, Rota showed the importance of this theory in combinatorial mathematics and gave a deep treatment of it.
f ( n ) = ∑ 1 ≤ m ≤ n μ ( m ) g ( ⌊ n m ⌋ ) for all n ≥ 1 {\displaystyle f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ for all }}n\geq 1}
となる。
この公式を使う簡単な例は、既約分数 0 < a / b < 1 の個数を数えることである。ここで a と b は互いに素で b ≤ n である。f (n) をこの個数とすれば、g (n) は b ≤ n なる分数 0 < a / b < 1 の総数である。ここで a と b は互いに素である必要はない。(なぜならば、gcd (a, b) = d かつ b ≤ n なるすべての分数 a / b は b / d ≤ n / d なる分数 (a / d ) / (b / d ) に簡約でき、逆もまた然りであるからだ。)g (n) = n (n − 1) / 2 であることを確かめるのは容易だが、f (n) は計算が難しい。
別の反転公式は、