TOPICS
Search

Möbius Transform


The transformation of a sequence a_1, a_2, ... with

 a_n=sum_(d|n)b_d
(1)

into the sequence b_1, b_2, ... via the Möbius inversion formula,

 b_n=sum_(d|n)mu(n/d)a_d.
(2)

The transformation of b_n to a_n is sometimes called the sum-of-divisors transform. Two other equivalent formulations are given by

 sum_(n=1)^inftya_nx^n=sum_(n=1)^inftyb_n(x^n)/(1-x^n),
(3)

the right side of which is called a Lambert series, and

 sum_(n=1)^infty(a_n)/(n^s)=zeta(s)sum_(n=1)^infty(b_n)/(n^s),
(4)

where zeta(s) is the Riemann zeta function (Sloane and Plouffe 1995, p. 21).

Example Möbius transformations (Sloane and Plouffe 1995, p. 22) include b_n=1 for all n, giving the inverse transform as a_n=1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, ... (OEIS A000005), the divisor function sigma_0(n) of n. The Möbius transform of a_n=n gives b_n=1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, ... (OEIS A000010), the totient function of n. The inverse Möbius transform of the sequence b_(2n)=0 and b_(2n+1)=4(-1)^n gives a_n=4, 4, 0, 4, 8, 0, 0, 4, 4, ... (OEIS A004018), the number of ways r(n) of writing n as a sum of two squares. The inverse Möbius transform of b_n=1 for n prime and b_n=0 for n composite gives the sequence a_n=0, 1, 1, 1, 1, 2, 1, 1, 1, ... (OEIS A001221), the number of distinct prime factors of n.


See also

Binomial Transform, Dirichlet Generating Function, Divisor Function, Euler Transform, Lambert Series, Möbius Inversion Formula, Möbius Transformation, Stirling Transform

Explore with Wolfram|Alpha

References

Bender, E. A. and Goldman, J. R. "On the Applications of Möbius Inversion in Combinatorial Analysis." Amer. Math. Monthly 82, 789-803, 1975.Bernstein, M. and Sloane, N. J. A. "Some Canonical Sequences of Integers." Linear Algebra Appl. 226/228, 57-72, 1995.Gessel, I. and Rota, C.-G. (Eds.). Classic Papers in Combinatorics. Boston, MA: Birkhäuser, 1987.Hardy, G. H. and Wright, E. M. §17.10 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Rota, G.-C. "On the Foundations of Combinatorial Theory I. Theory of Möbius Functions." Z. für Wahrscheinlichkeitsth. 2, 340-368, 1964.Sloane, N. J. A. Sequences A000005/M0246, A000010/M0299, A001221/M0056, and A004018/M3218 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 259, 1999.

Referenced on Wolfram|Alpha

Möbius Transform

Cite this as:

Weisstein, Eric W. "Möbius Transform." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MoebiusTransform.html

Subject classifications