In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors.
[1] A large generalization of this formula applies to summation over an arbitrary locally finite partially ordered set, with Möbius' classical formula applying to the set of the natural numbers ordered by divisibility: see incidence algebra.
The formula is also correct if f and g are functions from the positive integers into some abelian group (viewed as a Z-module).
As an example the sequence starting with φ is: The generated sequences can perhaps be more easily understood by considering the corresponding Dirichlet series: each repeated application of the transform corresponds to multiplication by the Riemann zeta function.
A related inversion formula more useful in combinatorics is as follows: suppose F(x) and G(x) are complex-valued functions defined on the interval [1, ∞) such that then Here the sums extend over all positive integers n which are less than or equal to x.
If α(n) is an arithmetic function possessing a Dirichlet inverse α−1(n), then if one defines then The previous formula arises in the special case of the constant function α(n) = 1, whose Dirichlet inverse is α−1(n) = μ(n).
Another inversion formula is (where we assume that the series involved are absolutely convergent): As above, this generalises to the case where α(n) is an arithmetic function possessing a Dirichlet inverse α−1(n): For example, there is a well known proof relating the Riemann zeta function to the prime zeta function that uses the series-based form of Möbius inversion in the previous equation when
[2] A more general theory of Möbius inversion formulas partially cited in the next section on incidence algebras is constructed by Rota in.
This gives rise to the following notational variant of the inversion formula: The first generalization can be proved as follows.
We have the following: The proof in the more general case where α(n) replaces 1 is essentially identical, as is the second generalisation.
to mean that s is a divisor of t. The statement of the general Möbius inversion formula [for partially ordered sets] 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.
He noted the relation between such topics as inclusion-exclusion, classical number theoretic Möbius inversion, coloring problems and flows in networks.
Since then, under the strong influence of Rota, the theory of Möbius inversion and related topics has become an active area of combinatorics.