Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
The classical Möbius inversion formula is a principle originating in number theory, which says that if $f$ and $g$ are two (say, complex-valued) functions on the positive natural numbers, then
if and only if
where the sums run over the divisors of $n$, and where $\mu$ is the Möbius function:
Gian-Carlo Rota(1964) described a vast generalization of the Möbius inversion formula, which was at the same time a generalization of the classical inclusion-exclusion principle in combinatorics. Rota’s formulation of Möbius inversion applies to functions defined over partially ordered sets, while further category-theoretic generalizations have also been proposed.
The incidence algebra of a poset $P$ (relative to a commutative ring $R$) is an associative unital algebra defined as follows. Its elements are functions $f : P \times P\to R$ such that $x \nleq y$ implies $f(x,y) = 0$. Pointwise addition $f+g$ and scalar multiplication $r\cdot f$ are defined straightforwardly ($(f+g)(x,y) = f(x,y) + g(x,y)$, $(r\cdot f)(x,y) = r\cdot f(x,y)$), while the convolution product $f*g$ is defined as follows:
Note that the unit of the convolution product is the Kronecker delta:
We write $I(P)$ for the incidence algebra of $P$. A special and important element of $I(P)$ is given by
referred to as the zeta function of $P$.
A Möbius function of $P$ is defined as an inverse to the zeta function with respect to the convolution product. Such an inverse always exists if the poset is locally finite, that is, if every interval $[x,y] = \{z \mid x \le z\le y\}$ is finite.
(Rota 1964): If $P$ is a locally finite poset, then there exists a function $\mu$ such that $\zeta * \mu = \mu * \zeta = \delta$.
$\mu(x,y)$ can be computed by induction on the number of elements in the interval $[x,y]$. In the base case we set $\mu(x,x) = 1$. Otherwise in the case that $x \ne y$, we assume by induction that $\mu(x,z)$ has already been defined for all $z$ in the half-open interval $[x,y)$, and set
From this definition, it is immediate that if
is a chain of length $n$ in $P$, where each $x_{i+1}$ covers $x_i$, then for all $i \leq j$,
It follows that both of the sums $\sum_{x \le z \le y} \mu(x,z)$ and $\sum_{x \le z \le y} \mu(z,y)$ add to zero unless $x = y$, hence that $\zeta*\mu = \mu*\zeta = \delta$.
We are now ready to state the Möbius inversion formula(s) for posets.
(Rota 1964): Let $f$ and $g$ be functions defined over a locally finite poset $P$. Then
Dually, we also have that
An easy way of proving the Möbius inversion formulas (Kung et al.) is to view $\zeta$ and $\mu$ as matrices acting on the column vectors $f$ and $g$ by multiplication. Then the first proposition simply says that $f = g * \zeta$ iff $f * \mu = g$, while the dual formulation says that $f = \zeta * g$ iff $\mu * f = g$.
The opposite poset $P^{op}$ has the same Möbius function as $P$ except with the arguments exchanged:
The Möbius function of the cartesian product $P \times Q$ of two posets $P$ and $Q$ is the product of their Möbius functions:
for all $x,x' \in P$ and $y,y' \in Q$.
Suppose $P$ and $Q$ are related by an adjunction (i.e., covariant Galois connection) $f \dashv g : Q \to P$. Then for all $x \in P$, $y \in Q$, the following equation holds:
(This result essentially goes back to Rota (1964) but in a slightly different formulation; for the above formulation, see Greene (1981), Aguiar and Ferrer Santos (2000), Kung et al. (2009).)
Let $\mathcal{P}X$ be the lattice of subsets of a finite set $X$. $\mathcal{P}X$ is isomorphic to the cartesian product of $|X|$ many copies of $\mathbf{2} = \{ 0 \lt 1 \}$, and so by the product rule for the Möbius function, we have
for any pair of subsets $I,J \subseteq X$ such that $I \subseteq J$. The Möbius inversion formula then says that for any functions $f$ and $g$ defined on $\mathcal{P}X$, we have
or dually that
This is called the inclusion-exclusion principle.
As a textbook example of the inclusion-exclusion principle in action, suppose we want to compute $g(I)$ = the number of permutations of $X$ fixing exactly the elements in $I$. Well, it is easy to compute the number of permutations of $X$ fixing at least the elements in $I$,
but then we can compute $g$ in terms of $f$ via Möbius inversion. As a special case, when $|X| = n$ and $I = \emptyset$, we recover the classical formula for the number of derangements of $n$ elements:
where a derangement is defined as a permutation fixing no elements.
Exercise: Prove that $n! = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^n$.
The classical Möbius inversion formula is recovered by considering the set of positive natural numbers ordered by divisibility.
The classical reference on Möbius inversion for posets is:
and a more modern reference is:
Möbius inversion for categories is discussed in:
Tom Leinster, Notions of Möbius inversion, Bulletin of the Belgian Mathematical Society 19 (2012) 911-935, arXiv:1201.0413v3
$n$Cafe: Möbius inversion for categories
Other references include:
Joachim Kock, Incidence Hopf algebras, pdf
Imma Gálvez-Carrillo, Joachim Kock, Andrew Tonks, Decomposition spaces, incidence algebras and Möbius inversion, arxiv/1404.3202
Metropolis, N.; Rota, Gian-Carlo, Witt vectors and the algebra of necklaces, Advances in Mathematics 50 (2): 95–125 (1983) doi
Marcelo Aguiar and Walter Ferrer Santos, Galois connections for incidence Hopf algebras of partially ordered sets, Adv. Math. 151 (2000), 71-100.
wikipedia Möbius function, necklace polynomial
Last revised on June 15, 2023 at 16:42:04. See the history of this page for a list of all contributions to it.