Proving the principle of inclusion-exclusion using Möbius inversion

214 Views Asked by At

In Enumerative Combinatorics v. I, Stanley applies Möbius inversion to $B_n$, the poset of subsets of $[n]$, to show that $\forall f,g : B_n \to \mathbb{C}$,

$$ g(S) = \sum_{T \subset S} f(T) \, \, \forall S \subset [n] \\ \iff \\ f(S)= \sum_{T \subset S} (-1)^{|S-T|} g(T) \, \, \forall S \subset [n]. $$

How can I get the usual statement of the principal of inclusion-exclusion from this?

1

There are 1 best solutions below

0
On

Let $X$ be a finite ambient set and $A_1,\ldots,A_n \subseteq X$. For $T \subseteq\{1,\ldots,n\}$, let $f(T)$ be the number of elements of $X$ which are contained exactly in the sets $A_t$ with $t\in T$, and let $g(T)$ be the number of elements of $X$ which are contained in the sets $A_t$ with $t\in T$ and possibly in others.

Clearly, $g(S) = \sum_{T\subseteq S} f(T)$ is true for all $S\subseteq\{1,\ldots,n\}$. By the stated inversion principle, then also the statement $f(S) = \sum_{T \subseteq S}(-1)^{\lvert S\rvert - \lvert T\rvert}g(T)$ is true for all $S\subseteq\{1,\ldots,n\}$. In the case $S = \{1,\ldots,n\}$, you get a variant of the principle of inclusion and exclusion.