Understanding a detail in the inclusion-exclusion Möbius Inversion proof in Introductory Combinatorics

276 Views Asked by At

In Introductory Combinatorics, by Brualdi, we have an explication on the Möbius Inversion. There's a line that I'm having a hard time believing, and would appreciate some explanation:

Let $n$ be a positive integer, and consider $(P(X_n), \subseteq)$ of all subsets of $X_n$, partially ordered by containment. We let $F: P(X_n) \rightarrow \mathbb{R}$ be a real-valued function.

We then define $G: P(X_n) \rightarrow \mathbb{R},$ where $$G(K) = \Sigma_{L\subseteq K}F(L)$$ where $K \subseteq X_N$ and the summation runs through all subsets of $K.$

Here is the claim that I'd like an explanation of: "Möbius inversion allows one to invert this equation and to recover $F$ from $G$, specifically, we have

$$F(K) = \Sigma_{L\subseteq K} (-1)^{|K|-|L|}G(L), (K \subseteq X_N)$$

1

There are 1 best solutions below

0
On

Maybe this will help. Starting from the RHS we have

$$\sum_{L\subseteq K} (-1)^{|K|-|L|} G(L) = \sum_{L\subseteq K} (-1)^{|K|-|L|} \sum_{Q\subseteq L} F(Q)$$

Reversing the order of summation,

$$\begin{align*} & (-1)^{|K|} \sum_{Q\subseteq K} F(Q) \sum_{Q\subseteq L \subseteq K} (-1)^{|L|} \\ & = F(K) + (-1)^{|K|} \sum_{Q\subset K} F(Q) \sum_{Q\subseteq L \subseteq K} (-1)^{|L|} \\ & = F(K) + (-1)^{|K|} \sum_{Q\subset K} F(Q) \sum_{M \subseteq K\setminus Q} (-1)^{|Q|+|M|} .\end{align*}$$

Now $K\setminus Q$ is not the empty set which means that $|K\setminus Q|\ge 1$ so the inner sum becomes

$$(-1)^{|Q|} \sum_{M\subseteq K\setminus Q} (-1)^{|M|} = (-1)^{|Q|} \sum_{m=0}^{|K\setminus Q|} {|K\setminus Q|\choose m} (-1)^m = 0.$$

This leaves just $F(K)$ as claimed.