This site is supported by donations to The OEIS Foundation.

Möbius transform

From OeisWiki
(Redirected from Möbius inversion formula)
Jump to: navigation, search


This article page is a stub, please help by expanding it.


Not to be confused with the Möbius transformation (linear fractional transformation).


The Möbius transform (or Möbius inversion) is a bijection from the set of integer sequences to the set of integer sequences.

The Möbius transform of an integer sequence is the integer sequence defined (via the so-called Möbius inversion formula) as

where means divides and is the Möbius function.

Inverse Möbius transform

The inverse Möbius transform, sometimes referred to as the sum-of-divisors transform, giving from , is

where means divides .

Examples

For example, the Möbius transform of the Fibonacci numbers

= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...}

is

= {1, 0, 1, 2, 4, 6, 12, 18, 32, 50, 88, 134, ...} (A007436)

since we have, for

= 1: = (1 / 1) * = 1 * 1 = 1;
= 2: = (2 / 1) * + (2 / 2) * = (−1) * 1 + 1 * 1 = 0;
= 3: = (3 / 1) * + (3 / 3) * = (−1) * 1 + 1 * 2 = 1;
= 4: = (4 / 1) * + (4 / 2) * + (4 / 4) * = 0 * 1 + (−1) * 1 + 1 * 3 = 2;
= 5: = (5 / 1) * + (5 / 5) * = (−1) * 1 + 1 * 5 = 4;
= 6: = (6 / 1) * + (6 / 2) * + (6 / 3) * + (6 / 6) * = 1 * 1 + (−1) * 1 + (−1) * 2 + 1 * 8 = 6;
= 7: = (7 / 1) * + (7 / 7) * = (−1) * 1 + 1 * 13 = 12;

Conversely, the inverse Möbius transform of the Möbius transform of the Fibonacci numbers gives back the Fibonacci numbers, e.g.

= 1: = = 1;
= 2: = + = 1 + 0 = 1;
= 3: = + = 1 + 1 = 2;
= 4: = + + = 1 + 0 + 2 = 3;
= 5: = + = 1 + 4 = 5;
= 6: = + + + = 1 + 0 + 1 + 6 = 8;
= 7: = + = 1 + 12 = 13;

Matrix representation of the Möbius transform

The Möbius transform of a finite sequence of integers into a finite sequence of integers may be represented by a matrix (here shown as a right-side operator, so that we can conveniently represent the sequences as row vectors; if the sequences are represented as column vectors, we use the transpose as a left-side operator instead)

where . (This matrix has trace and determinant 1.)

For the inverse Möbius transform, we thus have

where is the inverse matrix of , with . (This matrix also has trace and determinant 1.)

Starting with (for which we have to know about the divisors, for each integer from 1 to ), one may then generate as (where the top row now tells us which numbers from 1 to are squarefree, and whether they have an odd or even number of distinct prime factors!).

For the Möbius transform of finite sequences of integers, e.g. of the first 8 terms of the Fibonacci sequence, we have the 8 8 matrix

and for the inverse Möbius transform, we have

For the Möbius transform of infinite sequences of integers, e.g. of the Fibonacci sequence, we have the infinite square matrix

For the inverse Möbius transform of infinite sequences of integers, we obviously shall not attempt to invert the above infinite matrix!

Eigensequences of the Möbius transform

The eigensequences of the Möbius transform are... ?

Sequences

Sequences (Moebius transform)

A?????? Moebius transform applied once to sequence 1,0,0,0,....
A007427 Moebius transform applied twice to sequence 1,0,0,0,....
A007428 Moebius transform applied thrice to sequence 1,0,0,0,....


A?????? (Moebius transform applied once to natural numbers.)
A007431 Sum_{d|n} phi(d)*mu(n/d). (Moebius transform of Euler's totient function (A000010).) (Moebius transform applied twice to natural numbers.)
A007432 Moebius transform applied thrice to natural numbers.


A007438 Moebius transform of triangular numbers.
A007434 Jordan function J_2(n) (a generalization of phi(n)). (Moebius transform of squares.)


A007444 Moebius transform of primes.


A007436 Moebius transform of Fibonacci numbers.

Sequences (inverse Moebius transform)

A?????? d_2(n), or tau_2(n), the number of ordered 2-factorizations of n as n = r s. (Inverse Moebius transform applied once to all 1's sequence.)
A007425 d_3(n), or tau_3(n), the number of ordered 3-factorizations of n as n = r s t. (Inverse Moebius transform applied twice to all 1's sequence.)
A007426 d_4(n), or tau_4(n), the number of ordered 4-factorizations of n as n = r s t u. (Inverse Moebius transform applied thrice to all 1's sequence; or, Dirichlet convolution of d(n) [ A000005 ].)
A061200 d_5(n), or tau_5(n), the number of ordered 5-factorizations of n as n = r s t u v. (Inverse Moebius transform applied 4 times to all 1's sequence.)


A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. (Inverse Moebius transform of ...)


A000203 sigma(n) = sum of divisors of n. Also called sigma_1(n). (Inverse Moebius transform of the natural numbers.)
A007429 Inverse Moebius transform applied twice to natural numbers.
A007430 Inverse Moebius transform applied thrice to natural numbers.


A007437 Inverse Moebius transform of triangular numbers.
A007433 Inverse Moebius transform applied twice to squares.


A046951 Number of squares dividing n. (Inverse Moebius transform of characteristic function of squares (A010052).)
A061704 Number of cubes dividing n. (Inverse Moebius transform of characteristic function of cubes (A010057).)
A069088 Sum(d|n, core(d) ) where d are the divisors of n and where core(d) is the squarefree part of d: the smallest number such that d*core(d) is a square. (Inverse Moebius transform of squarefree part of n (A007913).)


A007445 Inverse Moebius transform of primes.


A001221 Number of distinct primes dividing n (also called omega(n)). (Inverse Moebius transform of characteristic function of primes (A010051).)
A?????? Number of distinct "2-almost primes" (A??????) which are factors of n. (Inverse Moebius transform of characteristic function of "2-almost primes" (A??????).)
A101606 Number of distinct "3-almost primes" (A014612) which are factors of n. (Inverse Moebius transform of characteristic function of "3-almost primes" (A101605).)
A101638 Number of distinct "4-almost primes" (A014613) which are factors of n. (Inverse Moebius transform of characteristic function of "4-almost primes" (A101637).)
A?????? Number of distinct "5-almost primes" (A??????) which are factors of n. (Inverse Moebius transform of characteristic function of "5-almost primes" (A??????).)


A?????? Number of distinct Sophie Germain primes dividing n. (Inverse Moebius transform of characteristic function of Sophie Germain primes (A156660).)(Verify.)[1]


A007435 Inverse Moebius transform of Fibonacci numbers.


A057660 Sum_{k=1..n} n/GCD(n,k). (Inverse Moebius transform of phi(n^2).)

Notes

  1. Needs verification.

External links