# Difference between revisions of "组合数学 (Fall 2019)/Pólya's theory of counting"

## Principle of Inclusion-Exclusion

Let $A$ and $B$ be two finite sets. The cardinality of their union is

$|A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|}$.

For three sets $A$, $B$, and $C$, the cardinality of the union of these three sets is computed as

$|A\cup B\cup C|=|A|+|B|+|C|-{\color{Blue}|A\cap B|}-{\color{Blue}|A\cap C|}-{\color{Blue}|B\cap C|}+{\color{Red}|A\cap B\cap C|}$.

This is illustrated by the following figure.

Generally, the Principle of Inclusion-Exclusion states the rule for computing the union of $n$ finite sets $A_1,A_2,\ldots,A_n$, such that

\begin{align} \left|\bigcup_{i=1}^nA_i\right| &= \sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|. \end{align}

In combinatorial enumeration, the Principle of Inclusion-Exclusion is usually applied in its complement form.

Let $A_1,A_2,\ldots,A_n\subseteq U$ be subsets of some finite set $U$. Here $U$ is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each $A_i$ contains the objects with some specific property (e.g. a "pattern") which we want to avoid. The problem is to count the number of objects without any of the $n$ properties. We write $\bar{A_i}=U-A_i$. The number of objects without any of the properties $A_1,A_2,\ldots,A_n$ is

\begin{align} \left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|=\left|U-\bigcup_{i=1}^nA_i\right| &= |U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|. \end{align}

For an $I\subseteq\{1,2,\ldots,n\}$, we denote

$A_I=\bigcap_{i\in I}A_i$

with the convention that $A_\emptyset=U$. The above equation is stated as:

 Principle of Inclusion-Exclusion Let $A_1,A_2,\ldots,A_n$ be a family of subsets of $U$. Then the number of elements of $U$ which lie in none of the subsets $A_i$ is $\sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I|$.

Let $S_k=\sum_{|I|=k}|A_I|\,$. Conventionally, $S_0=|A_\emptyset|=|U|$. The principle of inclusion-exclusion can be expressed as

$\left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|= S_0-S_1+S_2+\cdots+(-1)^nS_n.$

### Surjections

In the twelvefold way, we discuss the counting problems incurred by the mappings $f:N\rightarrow M$. The basic case is that elements from both $N$ and $M$ are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is $m^n$) and the number of injective (one-to-one) mappings (which is $(m)_n$), but the number of surjective is difficult. Here we apply the principle of inclusion-exclusion to count the number of surjective (onto) mappings.

 Theorem The number of surjective mappings from an $n$-set to an $m$-set is given by $\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n$.
Proof.
 Let $U=\{f:[n]\rightarrow[m]\}$ be the set of mappings from $[n]$ to $[m]$. Then $|U|=m^n$. For $i\in[m]$, let $A_i$ be the set of mappings $f:[n]\rightarrow[m]$ that none of $j\in[n]$ is mapped to $i$, i.e. $A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\}$, thus $|A_i|=(m-1)^n$. More generally, for $I\subseteq [m]$, $A_I=\bigcap_{i\in I}A_i$ contains the mappings $f:[n]\rightarrow[m]\setminus I$. And $|A_I|=(m-|I|)^n\,$. A mapping $f:[n]\rightarrow[m]$ is surjective if $f$ lies in none of $A_i$. By the principle of inclusion-exclusion, the number of surjective $f:[n]\rightarrow[m]$ is $\sum_{I\subseteq[m]}(-1)^{|I|}\left|A_I\right|=\sum_{I\subseteq[m]}(-1)^{|I|}(m-|I|)^n=\sum_{j=0}^m(-1)^j{m\choose j}(m-j)^n$. Let $k=m-j$. The theorem is proved.
$\square$

Recall that, in the twelvefold way, we establish a relation between surjections and partitions.

• Surjection to ordered partition:
For a surjective $f:[n]\rightarrow[m]$, $(f^{-1}(0),f^{-1}(1),\ldots,f^{-1}(m-1))$ is an ordered partition of $[n]$.
• Ordered partition to surjection:
For an ordered $m$-partition $(B_0,B_1,\ldots, B_{m-1})$ of $[n]$, we can define a function $f:[n]\rightarrow[m]$ by letting $f(i)=j$ if and only if $i\in B_j$. $f$ is surjective since as a partition, none of $B_i$ is empty.

Therefore, we have a one-to-one correspondence between surjective mappings from an $n$-set to an $m$-set and the ordered $m$-partitions of an $n$-set.

The Stirling number of the second kind $\left\{{n\atop m}\right\}$ is the number of $m$-partitions of an $n$-set. There are $m!$ ways to order an $m$-partition, thus the number of surjective mappings $f:[n]\rightarrow[m]$ is $m! \left\{{n\atop m}\right\}$. Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.

 Proposition $\left\{{n\atop m}\right\}=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n$.

### Derangements

We now count the number of bijections from a set to itself with no fixed points. This is the derangement problem.

For a permutation $\pi$ of $\{1,2,\ldots,n\}$, a fixed point is such an $i\in\{1,2,\ldots,n\}$ that $\pi(i)=i$. A derangement of $\{1,2,\ldots,n\}$ is a permutation of $\{1,2,\ldots,n\}$ that has no fixed points.

 Theorem The number of derangements of $\{1,2,\ldots,n\}$ given by $n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}}$.
Proof.
 Let $U$ be the set of all permutations of $\{1,2,\ldots,n\}$. So $|U|=n!$. Let $A_i$ be the set of permutations with fixed point $i$; so $|A_i|=(n-1)!$. More generally, for any $I\subseteq \{1,2,\ldots,n\}$, $A_I=\bigcap_{i\in I}A_i$, and $|A_I|=(n-|I|)!$, since permutations in $A_I$ fix every point in $I$ and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets $A_i$. So the number of derangements is $\sum_{I\subseteq\{1,2,\ldots,n\}}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.$ By Taylor's series, $\frac{1}{\mathrm{e}}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\pm o\left(\frac{1}{n!}\right)$. It is not hard to see that $n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ is the closest integer to $\frac{n!}{\mathrm{e}}$.
$\square$

Therefore, there are about $\frac{1}{\mathrm{e}}$ fraction of all permutations with no fixed points.

### Permutations with restricted positions

We introduce a general theory of counting permutations with restricted positions. In the derangement problem, we count the number of permutations that $\pi(i)\neq i$. We now generalize to the problem of counting permutations which avoid a set of arbitrarily specified positions.

It is traditionally described using terminology from the game of chess. Let $B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\}$, called a board. As illustrated below, we can think of $B$ as a chess board, with the positions in $B$ marked by "$\times$".

 a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h

For a permutation $\pi$ of $\{1,\ldots,n\}$, define the graph $G_\pi(V,E)$ as

\begin{align} G_\pi &= \{(i,\pi(i))\mid i\in \{1,2,\ldots,n\}\}. \end{align}

This can also be viewed as a set of marked positions on a chess board. Each row and each column has only one marked position, because $\pi$ is a permutation. Thus, we can identify each $G_\pi$ as a placement of $n$ rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.

For example, the following is the $G_\pi$ of such $\pi$ that $\pi(i)=i$.

 a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h

Now define

\begin{align} N_0 &= \left|\left\{\pi\mid B\cap G_\pi=\emptyset\right\}\right|\\ r_k &= \mbox{number of }k\mbox{-subsets of }B\mbox{ such that no two elements have a common coordinate}\\ &=\left|\left\{S\in{B\choose k} \,\bigg|\, \forall (i_1,j_1),(i_2,j_2)\in S, i_1\neq i_2, j_1\neq j_2 \right\}\right| \end{align}

Interpreted in chess game,

• $B$: a set of marked positions in an $[n]\times [n]$ chess board.
• $N_0$: the number of ways of placing $n$ non-attacking rooks on the chess board such that none of these rooks lie in $B$.
• $r_k$: number of ways of placing $k$ non-attacking rooks on $B$.

Our goal is to count $N_0$ in terms of $r_k$. This gives the number of permutations avoid all positions in a $B$.

 Theorem $N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!$.
Proof.
 For each $i\in[n]$, let $A_i=\{\pi\mid (i,\pi(i))\in B\}$ be the set of permutations $\pi$ whose $i$-th position is in $B$. $N_0$ is the number of permutations avoid all positions in $B$. Thus, our goal is to count the number of permutations $\pi$ in none of $A_i$ for $i\in [n]$. For each $I\subseteq [n]$, let $A_I=\bigcap_{i\in I}A_i$, which is the set of permutations $\pi$ such that $(i,\pi(i))\in B$ for all $i\in I$. Due to the principle of inclusion-exclusion, $N_0=\sum_{I\subseteq [n]} (-1)^{|I|}|A_I|=\sum_{k=0}^n(-1)^k\sum_{I\in{[n]\choose k}}|A_I|$. The next observation is that $\sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)!$, because we can count both sides by first placing $k$ non-attacking rooks on $B$ and placing $n-k$ additional non-attacking rooks on $[n]\times [n]$ in $(n-k)!$ ways. Therefore, $N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!$.
$\square$

#### Derangement problem

We use the above general method to solve the derange problem again.

Take $B=\{(1,1),(2,2),\ldots,(n,n)\}$ as the chess board. A derangement $\pi$ is a placement of $n$ non-attacking rooks such that none of them is in $B$.

 a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h

Clearly, the number of ways of placing $k$ non-attacking rooks on $B$ is $r_k={n\choose k}$. We want to count $N_0$, which gives the number of ways of placing $n$ non-attacking rooks such that none of these rooks lie in $B$.

By the above theorem

$N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=\sum_{k=0}^n(-1)^k\frac{n!}{k!}=n!\sum_{k=0}^n(-1)^k\frac{1}{k!}\approx\frac{n!}{e}.$

#### Problème des ménages

Suppose that in a banquet, we want to seat $n$ couples at a circular table, satisfying the following constraints:

• Men and women are in alternate places.
• No one sits next to his/her spouse.

In how many ways can this be done?

(For convenience, we assume that every seat at the table marked differently so that rotating the seats clockwise or anti-clockwise will end up with a different solution.)

First, let the $n$ ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are $n!$ different orders. Thus, there are $2(n!)$ ways to seat the $n$ ladies.

After sitting the wives, we label the remaining $n$ places clockwise as $0,1,\ldots, n-1$. And a seating of the $n$ husbands is given by a permutation $\pi$ of $[n]$ defined as follows. Let $\pi(i)$ be the seat of the husband of he lady sitting at the $i$-th place.

It is easy to see that $\pi$ satisfies that $\pi(i)\neq i$ and $\pi(i)\not\equiv i+1\pmod n$, and every permutation $\pi$ with these properties gives a feasible seating of the $n$ husbands. Thus, we only need to count the number of permutations $\pi$ such that $\pi(i)\not\equiv i, i+1\pmod n$.

Take $B=\{(0,0),(1,1),\ldots,(n-1,n-1), (0,1),(1,2),\ldots,(n-2,n-1),(n-1,0)\}$ as the chess board. A permutation $\pi$ which defines a way of seating the husbands, is a placement of $n$ non-attacking rooks such that none of them is in $B$.

 a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h

We need to compute $r_k$, the number of ways of placing $k$ non-attacking rooks on $B$. For our choice of $B$, $r_k$ is the number of ways of choosing $k$ points, no two consecutive, from a collection of $2n$ points arranged in a circle.

We first see how to do this in a line.

 Lemma The number of ways of choosing $k$ non-consecutive objects from a collection of $m$ objects arranged in a line, is ${m-k+1\choose k}$.
Proof.
 We draw a line of $m-k$ black points, and then insert $k$ red points into the $m-k+1$ spaces between the black points (including the beginning and end). \begin{align} &\sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \\ &\qquad\qquad\qquad\quad\Downarrow\\ &\sqcup \, \bullet \,\, {\color{Red}\bullet} \, \bullet \,\, {\color{Red}\bullet} \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}\, \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet} \end{align} This gives us a line of $m$ points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence. There are ${m-k+1\choose k}$ ways of placing $k$ red points into $m-k+1$ spaces.
$\square$

The problem of choosing non-consecutive objects in a circle can be reduced to the case that the objects are in a line.

 Lemma The number of ways of choosing $k$ non-consecutive objects from a collection of $m$ objects arranged in a circle, is $\frac{m}{m-k}{m-k\choose k}$.
Proof.
 Let $f(m,k)$ be the desired number; and let $g(m,k)$ be the number of ways of choosing $k$ non-consecutive points from $m$ points arranged in a circle, next coloring the $k$ points red, and then coloring one of the uncolored point blue. Clearly, $g(m,k)=(m-k)f(m,k)$. But we can also compute $g(m,k)$ as follows: Choose one of the $m$ points and color it blue. This gives us $m$ ways. Cut the circle to make a line of $m-1$ points by removing the blue point. Choose $k$ non-consecutive points from the line of $m-1$ points and color them red. This gives ${m-k\choose k}$ ways due to the previous lemma. Thus, $g(m,k)=m{m-k\choose k}$. Therefore we have the desired number $f(m,k)=\frac{m}{m-k}{m-k\choose k}$.
$\square$

By the above lemma, we have that $r_k=\frac{2n}{2n-k}{2n-k\choose k}$. Then apply the theorem of counting permutations with restricted positions,

$N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.$

This gives the number of ways of seating the $n$ husbands after the ladies are seated. Recall that there are $2n!$ ways of seating the $n$ ladies. Thus, the total number of ways of seating $n$ couples as required by problème des ménages is

$2n!\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.$

## Inversion

### Posets

A partially ordered set or poset for short is a set $P$ together with a binary relation denoted $\le_P$ (or just $\le$ if no confusion is caused), satisfying

• (reflexivity) For all $x\in P, x\le x$.
• (antisymmetry) If $x\le y$ and $y\le x$, then $x=y$.
• (transitivity) If $x\le y$ and $y\le z$, then $x\le z$.

We say two elements $x$ and $y$ are comparable if $x\le y$ or $y\le x$; otherwise $x$ and $y$ are incomparable.

Notation
• $x\ge y$ means $y\le x$.
• $x\lt y$ means $x\le y$ and $x\neq y$.
• $x\gt y$ means $y\lt x$.

### The Möbius function

Let $P$ be a finite poset. Consider functions in form of $\alpha:P\times P\rightarrow\mathbb{R}$ defined over domain $P\times P$. It is convenient to treat such functions as matrices whose rows and columns are indexed by $P$.

Incidence algebra of poset
Let
$I(P)=\{\alpha:P\times P\rightarrow\mathbb{R}\mid \alpha(x,y)=0\text{ for all }x\not\le_P y\}$
be the class of $\alpha$ such that $\alpha(x,y)$ is non-zero only for $x\le_P y$.
Treating $\alpha$ as matrix, it is trivial to see that $I(P)$ is closed under addition and scalar multiplication, that is,
• if $\alpha,\beta\in I(P)$ then $\alpha+\beta\in I(P)$;
• if $\alpha\in I(P)$ then $c\alpha\in I(P)$ for any $c\in\mathbb{R}$;
where $\alpha,\beta$ are treated as matrices.
With this spirit, it is natural to define the matrix multiplication in $I(P)$. For $\alpha,\beta\in I(P)$,
$(\alpha\beta)(x,y)=\sum_{z\in P}\alpha(x,z)\beta(z,y)=\sum_{x\le z\le y}\alpha(x,z)\beta(z,y)$.
The second equation is due to that for $\alpha,\beta\in I(P)$, for all $z$ other than $x\le z\le y$, $\alpha(x,z)\beta(z,y)$ is zero.
By the transitivity of relation $\le_P$, it is also easy to prove that $I(P)$ is closed under matrix multiplication (the detailed proof is left as an exercise). Therefore, $I(P)$ is closed under addition, scalar multiplication and matrix multiplication, so we have an algebra $I(P)$, called incidence algebra, over functions on $P\times P$.
Zeta function and Möbius function
A special function in $I(P)$ is the so-called zeta function $\zeta$, defined as
$\zeta(x,y)=\begin{cases}1&\text{if }x\le_P y,\\0 &\text{otherwise.}\end{cases}$
As a matrix (or more accurately, as an element of the incidence algebra), $\zeta$ is invertible and its inversion, denoted by $\mu$, is called the Möbius function. More precisely, $\mu$ is also in the incidence algebra $I(P)$, and $\mu\zeta=I$ where $I$ is the identity matrix (the identity of the incidence algebra $I(P)$).

There is an equivalent explicit definition of Möbius function.

 Definition (Möbius function) $\mu(x,y)=\begin{cases} -\sum_{x\le z\lt y}\mu(x,z)&\text{if }x\lt y,\\ 1&\text{if }x=y,\\ 0&\text{if }x\not\le y. \end{cases}$

To see the equivalence between this definition and the inversion of zeta function, we may have the following proposition, which is proved by directly evaluating $\mu\zeta$.

 Proposition For any $x,y\in P$, $\sum_{x\le z\le y}\mu(x,z)=\begin{cases}1 &\text{if }x=y,\\ 0 &\text{otherwise.}\end{cases}$
Proof.
 It holds that $(\mu\zeta)(x,y)=\sum_{x\le z\le y}\mu(x,z)\zeta(z,y)=\sum_{x\le z\le y}\mu(x,z)$. On the other hand, $\mu\zeta=I$, i.e. $(\mu\zeta)(x,y)=\begin{cases}1 &\text{if }x=y,\\ 0 &\text{otherwise.}\end{cases}$ The proposition follows.
$\square$

Note that $\mu(x,y)=\sum_{x\le z\le y}\mu(x,z)-\sum_{x\le z\lt y}\mu(x,z)$, which gives the above inductive definition of Möbius function.

### Computing Möbius functions

We consider the simple poset $P=[n]$, where $\le$ is the total order. It follows directly from the recursive definition of Möbius function that

$\mu(i,j)=\begin{cases}1 & \text{if }i=j,\\ -1 & \text{if }i+1=j,\\ 0 & \text{otherwise.} \end{cases}$

Usually for general posets, it is difficult to directly compute the Möbius function from its definition. We introduce a rule helping us compute the Möbius function by decomposing the poset into posets with simple structures.

 Theorem (the product rule) Let $P$ and $Q$ be two finite posets, and $P\times Q$ be the poset resulted from Cartesian product of $P$ and $Q$, where for all $(x,y), (x',y')\in P\times Q$, $(x,y)\le (x',y')$ if and only if $x\le x'$ and $y\le y'$. Then $\mu_{P\times Q}((x,y),(x',y'))=\mu_P(x,x')\mu_Q(y,y')$.
Proof.
 We use the recursive definition $\mu(x,y)=\begin{cases} -\sum_{x\le z\lt y}\mu(x,z)&\text{if }x\lt y,\\ 1&\text{if }x=y,\\ 0&\text{if }x\not\le y. \end{cases}$ to prove the equation in the theorem. If $(x,y)=(x',y')$, then $x=x'$ and $y=y'$. It is easy to see that both sides of the equation are 1. If $(x,y)\not\le(x',y')$, then either $x\not\le x'$ or $y\not\le y'$. It is also easy to see that both sides are 0. The only remaining case is that $(x,y)\lt (x',y')$, in which case either $x\lt x'$ or $y\lt y'$. \begin{align} \sum_{(x,y)\le (u,v)\le (x',y')}\mu_P(x,u)\mu_Q(y,v) &=\left(\sum_{x\le u\le x'}\mu_P(x,u)\right)\left(\sum_{y\le v\le y'}\mu_Q(y,v)\right)=I(x,x')I(y,y')=0, \end{align} where the last two equations are due to the proposition for $\mu$. Thus $\mu_P(x,x')\mu_Q(y,y')=-\sum_{(x,y)\le (u,v)\lt (x',y')}\mu_P(x,u)\mu_Q(y,v)$. By induction, assume that the equation $\mu_{P\times Q}((x,y),(u,v))=\mu_P(x,u)\mu_Q(y,v)$ is true for all $(u,v)\lt (x',y')$. Then \begin{align} \mu_{P\times Q}((x,y),(x',y')) &=-\sum_{(x,y)\le (u,v)\lt (x',y')}\mu_{P\times Q}((x,y),(u,v))\\ &=-\sum_{(x,y)\le (u,v)\lt (x',y')}\mu_P(x,u)\mu_Q(y,v)\\ &=\mu_P(x,x')\mu_Q(y,y'), \end{align} which complete the proof.
$\square$
Poset of subsets
Consider the poset defined by all subsets of a finite universe $U$, that is $P=2^U$, and for $S,T\subseteq U$, $S\le_P T$ if and only if $S\subseteq T$.
 Möbius function for subsets The Möbius function for the above defined poset $P$ is that for $S,T\subseteq U$, $\mu(S,T)= \begin{cases} (-1)^{|T|-|S|} & \text{if }S\subseteq T,\\ 0 &\text{otherwise.} \end{cases}$
Proof.
 We can equivalently represent each $S\subseteq U$ by a boolean string $S\in\{0,1\}^U$, where $S(x)=1$ if and only if $x\in S$. For each element $x\in U$, we can define a poset $P_x=\{0, 1\}$ with $0\le 1$. By definition of Möbius function, the Möbius function of this elementary poset is given by $\mu_x(0,0)=\mu_x(1,1)=1$, $\mu_x(0,1)=-1$ and $\mu(1,0)=0$. The poset $P$ of all subsets of $U$ is the Cartesian product of all $P_x$, $x\in U$. By the product rule, $\mu(S,T)=\prod_{x\in U}\mu_x(S(x), T(x))=\prod_{x\in S\atop x\in T}1\prod_{x\not\in S\atop x\not\in T}1\prod_{x\in S\atop x\not\in T}0\prod_{x\not\in S\atop x\in T}(-1)=\begin{cases} (-1)^{|T|-|S|} & \text{if }S\subseteq T,\\ 0 &\text{otherwise.} \end{cases}$
$\square$
Note that the poset $P$ is actually the Boolean algebra of rank $|U|$. The proof relies only on that the fact that the poset is a Boolean algebra, thus the theorem holds for Boolean algebra posets.
Posets of divisors
Consider the poset defined by all devisors of a positive integer $n$, that is $P=\{a\gt 0\mid a|n\}$, and for $a,b\in P$, $a\le_P b$ if and only if $a|b\,$.
 Möbius function for divisors The Möbius function for the above defined poset $P$ is that for $a,b\gt 0$ that $a|n$ and $b|n$, $\mu(a,b)= \begin{cases} (-1)^{r} & \text{if }\frac{b}{a}\text{ is the product of }r\text{ distinct primes},\\ 0 &\text{otherwise, i.e. if }a\not|b\text{ or }\frac{b}{a}\text{ is not squarefree.} \end{cases}$
Proof.
 Denote $n=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k}$. Represent $n$ by a tuple $(n_1,n_2,\ldots,n_k)$. Every $a\in P$ corresponds in this way to a tuple $(a_1,a_2,\ldots,a_k)$ with $a_i\le n_i$ for all $1\le i\le k$. Let $P_i=\{1,2,\ldots,n_i\}$ be the poset with $\le$ being the total order. The poset $P$ of divisors of $n$ is thus isomorphic to the poset constructed by the Cartesian product of all $P_i$, $1\le i\le k$. Then \begin{align} \mu(a,b) &=\prod_{1\le i\le k}\mu(a_i,b_i)=\prod_{1\le i\le k\atop a_i=b_i}1\prod_{1\le i\le k\atop b_i-a_i=1}(-1)\prod_{1\le i\le k\atop b_i-a_i\not\in\{0,1\}}0 =\begin{cases} (-1)^{\sum_{i}(b_i-a_i)} & \text{if all }b_i-a_i\in\{0,1\},\\ 0 &\text{otherwise.} \end{cases}\\ &=\begin{cases} (-1)^{r} & \text{if }\frac{b}{a}\text{ is the product of }r\text{ distinct primes},\\ 0 &\text{otherwise.} \end{cases} \end{align}
$\square$

### Principle of Möbius inversion

We now introduce the the famous Möbius inversion formula.

 Möbius inversion formula Let $P$ be a finite poset and $\mu$ its Möbius function. Let $f,g:P\rightarrow \mathbb{R}$. Then $\forall x\in P,\,\, g(x)=\sum_{y\le x} f(y)$, if and only if $\forall x\in P,\,\, f(x)=\sum_{y\le x}g(y)\mu(y,x)$.

The functions $f,g:P\rightarrow\mathbb{R}$ are vectors. Evaluate the matrix multiplications $f\zeta$ and $g\mu$ as follows:

$(f\zeta)(x)=\sum_{y\in P}f(y)\zeta(y,x)=\sum_{y\le x}f(y)$,

and

$(g\mu)(x)=\sum_{y\in P}g(y)\mu(y,x)=\sum_{y\le x}g(y)\mu(y,x)$.

The Möbius inversion formula is nothing but the following statement

$f\zeta=g\Leftrightarrow f=g\mu$,

which is trivially true due to $\mu\zeta=I$ by basic linear algebra.

The following dual form of the inversion formula is also useful.

 Möbius inversion formula, dual form Let $P$ be a finite poset and $\mu$ its Möbius function. Let $f,g:P\rightarrow \mathbb{R}$. Then $\forall x\in P, \,\, g(x)=\sum_{y{\color{red}\ge} x} f(y)$, if and only if $\forall x\in P, \,\, f(x)=\sum_{y{\color{red}\ge} x}\mu(x,y)g(y)$.

To prove the dual form, we only need to evaluate the matrix multiplications on left:

$\zeta f=g\Leftrightarrow f=\mu g$.
Principle of Inclusion-Exclusion
Let $A_1,A_2,\ldots,A_n\subseteq U$. For any $J\subseteq\{1,2,\ldots,n\}$,
• let $f(J)$ be the number of elements that belongs to exactly the sets $A_i, i\in J$ and to no others, i.e.
$f(J)=\left|\left(\bigcap_{i\in J}A_i\right)\setminus\left(\bigcup_{i\not\in J}A_i\right)\right|$;
• let $g(J)=\left|\bigcap_{i\in J}A_i\right|$.
For any $J\subseteq\{1,2,\ldots,n\}$, the following relation holds for the above defined $f$ and $g$:
$g(J)=\sum_{I\supseteq J}f(I)$.
Applying the dual form of the Möbius inversion formula, we have that for any $J\subseteq\{1,2,\ldots,n\}$,
$f(J)=\sum_{I\supseteq J}\mu(J,I)g(I)=\sum_{I\supseteq J}\mu(J,I)\left|\bigcap_{i\in I}A_i\right|$,
where the Möbius function is for the poset of all subsets of $\{1,2,\ldots,n\}$, ordered by $\subseteq$, thus it holds that $\mu(J,I)=(-1)^{|I|-|J|}\,$ for $J\subseteq I$. Therefore,
$f(J)=\sum_{I\supseteq J}(-1)^{|I|-|J|}\left|\bigcap_{i\in I}A_i\right|$.
We have a formula for the number of elements with exactly those properties $A_i, i\in J$ for any $J\subseteq\{1,2,\ldots,n\}$. For the special case that $J=\emptyset$, $f(\emptyset)$ is the number of elements satisfying no property of $A_1,A_2,\ldots,A_n$, and
$f(\emptyset)=\left|U\setminus\bigcup_iA_i\right|=\sum_{I\subseteq \{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|$
which gives precisely the Principle of Inclusion-Exclusion.
Möbius inversion formula for number theory
The number-theoretical Möbius inversion formula is stated as such: Let $N$ be a positive integer,
$g(n)=\sum_{d|n}f(d)\,$ for all $n|N$
if and only if
$f(n)=\sum_{d|n}g(d)\mu\left(\frac{n}{d}\right)\,$ for all $n|N$,
where $\mu$ is the number-theoretical Möbius function, defined as
$\mu(n)=\begin{cases}1 & \text{if }n\text{ is product of an even number of distinct primes,}\\ -1 &\text{if }n\text{ is product of an odd number of distinct primes,}\\ 0 &\text{otherwise.}\end{cases}$
The number-theoretical Möbius inversion formula is just a special case of the Möbius inversion formula for posets, when the poset is the set of divisors of $N$, and for any $a,b\in P$, $a\le_P b$ if $a|b$.

## Sieve Method in Number Theory

### The Euler totient function

Two integers $m, n$ are said to be relatively prime if their greatest common diviser $\mathrm{gcd}(m,n)=1$. For a positive integer $n$, let $\phi(n)$ be the number of positive integers from $\{1,2,\ldots,n\}$ that are relative prime to $n$. This function, called the Euler $\phi$ function or the Euler totient function, is fundamental in number theory.

We now derive a formula for this function by using the principle of inclusion-exclusion.

 Theorem (The Euler totient function) Suppose $n$ is divisible by precisely $r$ different primes, denoted $p_1,\ldots,p_r$. Then $\phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)$.
Proof.
 Let $U=\{1,2,\ldots,n\}$ be the universe. The number of positive integers from $U$ which is divisible by some $p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\}$, is $\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}}$. $\phi(n)$ is the number of integers from $U$ which is not divisible by any $p_1,\ldots,p_r$. By principle of inclusion-exclusion, \begin{align} \phi(n) &=n+\sum_{k=1}^r(-1)^k\sum_{1\le i_1\lt i_2\lt \cdots \lt i_k\le n}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_k}}\\ &=n-\sum_{1\le i\le n}\frac{n}{p_i}+\sum_{1\le i\lt j\le n}\frac{n}{p_i p_j}-\sum_{1\le i\lt j\lt k\le n}\frac{n}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{n}{p_{1}p_{2}\cdots p_{r}}\\ &=n\left(1-\sum_{1\le i\le n}\frac{1}{p_i}+\sum_{1\le i\lt j\le n}\frac{1}{p_i p_j}-\sum_{1\le i\lt j\lt k\le n}\frac{1}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{1}{p_{1}p_{2}\cdots p_{r}}\right)\\ &=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right). \end{align}
$\square$

## Reference

• Stanley, Enumerative Combinatorics, Volume 1, Chapter 2.
• van Lin and Wilson, A course in combinatorics, Chapter 10, 25.