Mobius Inversion on Posets

The Mobius function and the poset generalization of inclusion-exclusion.

The idea

Mobius inversion recovers the values of a function on a partially ordered set from its accumulated totals.

Fix a finite poset $P$ and a function $f$ on it, and set $g(x) = \sum_{y \le x} f(y)$, the total of $f$ over $x$ and everything below it. Such totals are often what a counting problem yields directly — the arrangements with at least some property, the sum of a weight over all divisors of $n$ — while the individual values $f(y)$ are what we want. The theorem is that $f$ can always be recovered from $g$ by a fixed set of signed coefficients that depend on the order alone and not on $f$.

Those coefficients form the Mobius function of the poset.

Definition (Mobius function).

The Mobius function $\mu(x, y)$ of $P$ is defined for $x \le y$ by $\mu(x, x) = 1$ together with $\sum_{x \le z \le y} \mu(x, z) = 0 \quad \text{whenever } x < y.$

The recursion determines every value by working upward from the bottom of each interval.

Theorem (Mobius inversion).

Let $P$ be a finite poset and let $g(x) = \sum_{y \le x} f(y)$ for every $x \in P$. Then for every $y \in P$, $f(y) = \sum_{x \le y} \mu(x, y)\, g(x).$

Two familiar counting principles are this one theorem specialized to a particular poset: one to the subsets of a set ordered by inclusion, the other to the positive integers ordered by divisibility.

Ways to work on it

• Walkthrough. Build the Mobius function and see inversion generalize inclusion-exclusion.
• Practice. Compute a Mobius value on a small poset.
• Hardest. Recover a function from its partial sums by full Mobius inversion.

Not sure where to start? Take the ten-question placement test.