# 组合数学 (Spring 2016)/Sieve methods

## Principle of Inclusion-Exclusion

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

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

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

$\displaystyle{ |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 $\displaystyle{ n }$ finite sets $\displaystyle{ A_1,A_2,\ldots,A_n }$, such that

\displaystyle{ \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 $\displaystyle{ A_1,A_2,\ldots,A_n\subseteq U }$ be subsets of some finite set $\displaystyle{ U }$. Here $\displaystyle{ U }$ is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each $\displaystyle{ 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 $\displaystyle{ n }$ properties. We write $\displaystyle{ \bar{A_i}=U-A_i }$. The number of objects without any of the properties $\displaystyle{ A_1,A_2,\ldots,A_n }$ is

\displaystyle{ \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 $\displaystyle{ I\subseteq\{1,2,\ldots,n\} }$, we denote

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

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

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

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

$\displaystyle{ \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 $\displaystyle{ f:N\rightarrow M }$. The basic case is that elements from both $\displaystyle{ N }$ and $\displaystyle{ M }$ are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is $\displaystyle{ m^n }$) and the number of injective (one-to-one) mappings (which is $\displaystyle{ (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 $\displaystyle{ n }$-set to an $\displaystyle{ m }$-set is given by $\displaystyle{ \sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n }$.
Proof.
 Let $\displaystyle{ U=\{f:[n]\rightarrow[m]\} }$ be the set of mappings from $\displaystyle{ [n] }$ to $\displaystyle{ [m] }$. Then $\displaystyle{ |U|=m^n }$. For $\displaystyle{ i\in[m] }$, let $\displaystyle{ A_i }$ be the set of mappings $\displaystyle{ f:[n]\rightarrow[m] }$ that none of $\displaystyle{ j\in[n] }$ is mapped to $\displaystyle{ i }$, i.e. $\displaystyle{ A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\} }$, thus $\displaystyle{ |A_i|=(m-1)^n }$. More generally, for $\displaystyle{ I\subseteq [m] }$, $\displaystyle{ A_I=\bigcap_{i\in I}A_i }$ contains the mappings $\displaystyle{ f:[n]\rightarrow[m]\setminus I }$. And $\displaystyle{ |A_I|=(m-|I|)^n\, }$. A mapping $\displaystyle{ f:[n]\rightarrow[m] }$ is surjective if $\displaystyle{ f }$ lies in none of $\displaystyle{ A_i }$. By the principle of inclusion-exclusion, the number of surjective $\displaystyle{ f:[n]\rightarrow[m] }$ is $\displaystyle{ \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 $\displaystyle{ k=m-j }$. The theorem is proved.
$\displaystyle{ \square }$

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

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

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

The Stirling number of the second kind $\displaystyle{ \left\{{n\atop m}\right\} }$ is the number of $\displaystyle{ m }$-partitions of an $\displaystyle{ n }$-set. There are $\displaystyle{ m! }$ ways to order an $\displaystyle{ m }$-partition, thus the number of surjective mappings $\displaystyle{ f:[n]\rightarrow[m] }$ is $\displaystyle{ 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 $\displaystyle{ \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 $\displaystyle{ \pi }$ of $\displaystyle{ \{1,2,\ldots,n\} }$, a fixed point is such an $\displaystyle{ i\in\{1,2,\ldots,n\} }$ that $\displaystyle{ \pi(i)=i }$. A derangement of $\displaystyle{ \{1,2,\ldots,n\} }$ is a permutation of $\displaystyle{ \{1,2,\ldots,n\} }$ that has no fixed points.

 Theorem The number of derangements of $\displaystyle{ \{1,2,\ldots,n\} }$ given by $\displaystyle{ n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}} }$.
Proof.
 Let $\displaystyle{ U }$ be the set of all permutations of $\displaystyle{ \{1,2,\ldots,n\} }$. So $\displaystyle{ |U|=n! }$. Let $\displaystyle{ A_i }$ be the set of permutations with fixed point $\displaystyle{ i }$; so $\displaystyle{ |A_i|=(n-1)! }$. More generally, for any $\displaystyle{ I\subseteq \{1,2,\ldots,n\} }$, $\displaystyle{ A_I=\bigcap_{i\in I}A_i }$, and $\displaystyle{ |A_I|=(n-|I|)! }$, since permutations in $\displaystyle{ A_I }$ fix every point in $\displaystyle{ I }$ and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets $\displaystyle{ A_i }$. So the number of derangements is $\displaystyle{ \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, $\displaystyle{ \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 $\displaystyle{ n!\sum_{k=0}^n\frac{(-1)^k}{k!} }$ is the closest integer to $\displaystyle{ \frac{n!}{\mathrm{e}} }$.
$\displaystyle{ \square }$

Therefore, there are about $\displaystyle{ \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 $\displaystyle{ \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 $\displaystyle{ B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\} }$, called a board. As illustrated below, we can think of $\displaystyle{ B }$ as a chess board, with the positions in $\displaystyle{ B }$ marked by "$\displaystyle{ \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 $\displaystyle{ \pi }$ of $\displaystyle{ \{1,\ldots,n\} }$, define the graph $\displaystyle{ G_\pi(V,E) }$ as

\displaystyle{ \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 $\displaystyle{ \pi }$ is a permutation. Thus, we can identify each $\displaystyle{ G_\pi }$ as a placement of $\displaystyle{ n }$ rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.

For example, the following is the $\displaystyle{ G_\pi }$ of such $\displaystyle{ \pi }$ that $\displaystyle{ \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

\displaystyle{ \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,

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

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

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

#### Derangement problem

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

Take $\displaystyle{ B=\{(1,1),(2,2),\ldots,(n,n)\} }$ as the chess board. A derangement $\displaystyle{ \pi }$ is a placement of $\displaystyle{ n }$ non-attacking rooks such that none of them is in $\displaystyle{ 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 $\displaystyle{ k }$ non-attacking rooks on $\displaystyle{ B }$ is $\displaystyle{ r_k={n\choose k} }$. We want to count $\displaystyle{ N_0 }$, which gives the number of ways of placing $\displaystyle{ n }$ non-attacking rooks such that none of these rooks lie in $\displaystyle{ B }$.

By the above theorem

$\displaystyle{ 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 $\displaystyle{ 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 $\displaystyle{ n }$ ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are $\displaystyle{ n! }$ different orders. Thus, there are $\displaystyle{ 2(n!) }$ ways to seat the $\displaystyle{ n }$ ladies.

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

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

Take $\displaystyle{ 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 $\displaystyle{ \pi }$ which defines a way of seating the husbands, is a placement of $\displaystyle{ n }$ non-attacking rooks such that none of them is in $\displaystyle{ 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 $\displaystyle{ r_k }$, the number of ways of placing $\displaystyle{ k }$ non-attacking rooks on $\displaystyle{ B }$. For our choice of $\displaystyle{ B }$, $\displaystyle{ r_k }$ is the number of ways of choosing $\displaystyle{ k }$ points, no two consecutive, from a collection of $\displaystyle{ 2n }$ points arranged in a circle.

We first see how to do this in a line.

 Lemma The number of ways of choosing $\displaystyle{ k }$ non-consecutive objects from a collection of $\displaystyle{ m }$ objects arranged in a line, is $\displaystyle{ {m-k+1\choose k} }$.
Proof.
 We draw a line of $\displaystyle{ m-k }$ black points, and then insert $\displaystyle{ k }$ red points into the $\displaystyle{ m-k+1 }$ spaces between the black points (including the beginning and end). \displaystyle{ \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 $\displaystyle{ m }$ points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence. There are $\displaystyle{ {m-k+1\choose k} }$ ways of placing $\displaystyle{ k }$ red points into $\displaystyle{ m-k+1 }$ spaces.
$\displaystyle{ \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 $\displaystyle{ k }$ non-consecutive objects from a collection of $\displaystyle{ m }$ objects arranged in a circle, is $\displaystyle{ \frac{m}{m-k}{m-k\choose k} }$.
Proof.
 Let $\displaystyle{ f(m,k) }$ be the desired number; and let $\displaystyle{ g(m,k) }$ be the number of ways of choosing $\displaystyle{ k }$ non-consecutive points from $\displaystyle{ m }$ points arranged in a circle, next coloring the $\displaystyle{ k }$ points red, and then coloring one of the uncolored point blue. Clearly, $\displaystyle{ g(m,k)=(m-k)f(m,k) }$. But we can also compute $\displaystyle{ g(m,k) }$ as follows: Choose one of the $\displaystyle{ m }$ points and color it blue. This gives us $\displaystyle{ m }$ ways. Cut the circle to make a line of $\displaystyle{ m-1 }$ points by removing the blue point. Choose $\displaystyle{ k }$ non-consecutive points from the line of $\displaystyle{ m-1 }$ points and color them red. This gives $\displaystyle{ {m-k\choose k} }$ ways due to the previous lemma. Thus, $\displaystyle{ g(m,k)=m{m-k\choose k} }$. Therefore we have the desired number $\displaystyle{ f(m,k)=\frac{m}{m-k}{m-k\choose k} }$.
$\displaystyle{ \square }$

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

$\displaystyle{ 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 $\displaystyle{ n }$ husbands after the ladies are seated. Recall that there are $\displaystyle{ 2n! }$ ways of seating the $\displaystyle{ n }$ ladies. Thus, the total number of ways of seating $\displaystyle{ n }$ couples as required by problème des ménages is

$\displaystyle{ 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 $\displaystyle{ P }$ together with a binary relation denoted $\displaystyle{ \le_P }$ (or just $\displaystyle{ \le }$ if no confusion is caused), satisfying

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

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

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

### The Möbius function

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

Incidence algebra of poset
Let
$\displaystyle{ 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 $\displaystyle{ \alpha }$ such that $\displaystyle{ \alpha(x,y) }$ is non-zero only for $\displaystyle{ x\le_P y }$.
Treating $\displaystyle{ \alpha }$ as matrix, it is trivial to see that $\displaystyle{ I(P) }$ is closed under addition and scalar multiplication, that is,
• if $\displaystyle{ \alpha,\beta\in I(P) }$ then $\displaystyle{ \alpha+\beta\in I(P) }$;
• if $\displaystyle{ \alpha\in I(P) }$ then $\displaystyle{ c\alpha\in I(P) }$ for any $\displaystyle{ c\in\mathbb{R} }$;
where $\displaystyle{ \alpha,\beta }$ are treated as matrices.
With this spirit, it is natural to define the matrix multiplication in $\displaystyle{ I(P) }$. For $\displaystyle{ \alpha,\beta\in I(P) }$,
$\displaystyle{ (\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 $\displaystyle{ \alpha,\beta\in I(P) }$, for all $\displaystyle{ z }$ other than $\displaystyle{ x\le z\le y }$, $\displaystyle{ \alpha(x,z)\beta(z,y) }$ is zero.
By the transitivity of relation $\displaystyle{ \le_P }$, it is also easy to prove that $\displaystyle{ I(P) }$ is closed under matrix multiplication (the detailed proof is left as an exercise). Therefore, $\displaystyle{ I(P) }$ is closed under addition, scalar multiplication and matrix multiplication, so we have an algebra $\displaystyle{ I(P) }$, called incidence algebra, over functions on $\displaystyle{ P\times P }$.
Zeta function and Möbius function
A special function in $\displaystyle{ I(P) }$ is the so-called zeta function $\displaystyle{ \zeta }$, defined as
$\displaystyle{ \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), $\displaystyle{ \zeta }$ is invertible and its inversion, denoted by $\displaystyle{ \mu }$, is called the Möbius function. More precisely, $\displaystyle{ \mu }$ is also in the incidence algebra $\displaystyle{ I(P) }$, and $\displaystyle{ \mu\zeta=I }$ where $\displaystyle{ I }$ is the identity matrix (the identity of the incidence algebra $\displaystyle{ I(P) }$).

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

 Definition (Möbius function) $\displaystyle{ \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 $\displaystyle{ \mu\zeta }$.

 Proposition For any $\displaystyle{ x,y\in P }$, $\displaystyle{ \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 $\displaystyle{ (\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, $\displaystyle{ \mu\zeta=I }$, i.e. $\displaystyle{ (\mu\zeta)(x,y)=\begin{cases}1 &\text{if }x=y,\\ 0 &\text{otherwise.}\end{cases} }$ The proposition follows.
$\displaystyle{ \square }$

Note that $\displaystyle{ \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 $\displaystyle{ P=[n] }$, where $\displaystyle{ \le }$ is the total order. It follows directly from the recursive definition of Möbius function that

$\displaystyle{ \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 $\displaystyle{ P }$ and $\displaystyle{ Q }$ be two finite posets, and $\displaystyle{ P\times Q }$ be the poset resulted from Cartesian product of $\displaystyle{ P }$ and $\displaystyle{ Q }$, where for all $\displaystyle{ (x,y), (x',y')\in P\times Q }$, $\displaystyle{ (x,y)\le (x',y') }$ if and only if $\displaystyle{ x\le x' }$ and $\displaystyle{ y\le y' }$. Then $\displaystyle{ \mu_{P\times Q}((x,y),(x',y'))=\mu_P(x,x')\mu_Q(y,y') }$.
Proof.
 We use the recursive definition $\displaystyle{ \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 $\displaystyle{ (x,y)=(x',y') }$, then $\displaystyle{ x=x' }$ and $\displaystyle{ y=y' }$. It is easy to see that both sides of the equation are 1. If $\displaystyle{ (x,y)\not\le(x',y') }$, then either $\displaystyle{ x\not\le x' }$ or $\displaystyle{ y\not\le y' }$. It is also easy to see that both sides are 0. The only remaining case is that $\displaystyle{ (x,y)\lt (x',y') }$, in which case either $\displaystyle{ x\lt x' }$ or $\displaystyle{ y\lt y' }$. \displaystyle{ \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 $\displaystyle{ \mu }$. Thus $\displaystyle{ \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 $\displaystyle{ \mu_{P\times Q}((x,y),(u,v))=\mu_P(x,u)\mu_Q(y,v) }$ is true for all $\displaystyle{ (u,v)\lt (x',y') }$. Then \displaystyle{ \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.
$\displaystyle{ \square }$
Poset of subsets
Consider the poset defined by all subsets of a finite universe $\displaystyle{ U }$, that is $\displaystyle{ P=2^U }$, and for $\displaystyle{ S,T\subseteq U }$, $\displaystyle{ S\le_P T }$ if and only if $\displaystyle{ S\subseteq T }$.
 Möbius function for subsets The Möbius function for the above defined poset $\displaystyle{ P }$ is that for $\displaystyle{ S,T\subseteq U }$, $\displaystyle{ \mu(S,T)= \begin{cases} (-1)^{|T|-|S|} & \text{if }S\subseteq T,\\ 0 &\text{otherwise.} \end{cases} }$
Proof.
 We can equivalently represent each $\displaystyle{ S\subseteq U }$ by a boolean string $\displaystyle{ S\in\{0,1\}^U }$, where $\displaystyle{ S(x)=1 }$ if and only if $\displaystyle{ x\in S }$. For each element $\displaystyle{ x\in U }$, we can define a poset $\displaystyle{ P_x=\{0, 1\} }$ with $\displaystyle{ 0\le 1 }$. By definition of Möbius function, the Möbius function of this elementary poset is given by $\displaystyle{ \mu_x(0,0)=\mu_x(1,1)=1 }$, $\displaystyle{ \mu_x(0,1)=-1 }$ and $\displaystyle{ \mu(1,0)=0 }$. The poset $\displaystyle{ P }$ of all subsets of $\displaystyle{ U }$ is the Cartesian product of all $\displaystyle{ P_x }$, $\displaystyle{ x\in U }$. By the product rule, $\displaystyle{ \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} }$
$\displaystyle{ \square }$
Note that the poset $\displaystyle{ P }$ is actually the Boolean algebra of rank $\displaystyle{ |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 $\displaystyle{ n }$, that is $\displaystyle{ P=\{a\gt 0\mid a|n\} }$, and for $\displaystyle{ a,b\in P }$, $\displaystyle{ a\le_P b }$ if and only if $\displaystyle{ a|b\, }$.
 Möbius function for divisors The Möbius function for the above defined poset $\displaystyle{ P }$ is that for $\displaystyle{ a,b\gt 0 }$ that $\displaystyle{ a|n }$ and $\displaystyle{ b|n }$, $\displaystyle{ \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 $\displaystyle{ n=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k} }$. Represent $\displaystyle{ n }$ by a tuple $\displaystyle{ (n_1,n_2,\ldots,n_k) }$. Every $\displaystyle{ a\in P }$ corresponds in this way to a tuple $\displaystyle{ (a_1,a_2,\ldots,a_k) }$ with $\displaystyle{ a_i\le n_i }$ for all $\displaystyle{ 1\le i\le k }$. Let $\displaystyle{ P_i=\{1,2,\ldots,n_i\} }$ be the poset with $\displaystyle{ \le }$ being the total order. The poset $\displaystyle{ P }$ of divisors of $\displaystyle{ n }$ is thus isomorphic to the poset constructed by the Cartesian product of all $\displaystyle{ P_i }$, $\displaystyle{ 1\le i\le k }$. Then \displaystyle{ \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} }
$\displaystyle{ \square }$

### Principle of Möbius inversion

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

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

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

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

and

$\displaystyle{ (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

$\displaystyle{ f\zeta=g\Leftrightarrow f=g\mu }$,

which is trivially true due to $\displaystyle{ \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 $\displaystyle{ P }$ be a finite poset and $\displaystyle{ \mu }$ its Möbius function. Let $\displaystyle{ f,g:P\rightarrow \mathbb{R} }$. Then $\displaystyle{ \forall x\in P, \,\, g(x)=\sum_{y{\color{red}\ge} x} f(y) }$, if and only if $\displaystyle{ \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:

$\displaystyle{ \zeta f=g\Leftrightarrow f=\mu g }$.
Principle of Inclusion-Exclusion
Let $\displaystyle{ A_1,A_2,\ldots,A_n\subseteq U }$. For any $\displaystyle{ J\subseteq\{1,2,\ldots,n\} }$,
• let $\displaystyle{ f(J) }$ be the number of elements that belongs to exactly the sets $\displaystyle{ A_i, i\in J }$ and to no others, i.e.
$\displaystyle{ f(J)=\left|\left(\bigcap_{i\in J}A_i\right)\setminus\left(\bigcup_{i\not\in J}A_i\right)\right| }$;
• let $\displaystyle{ g(J)=\left|\bigcap_{i\in J}A_i\right| }$.
For any $\displaystyle{ J\subseteq\{1,2,\ldots,n\} }$, the following relation holds for the above defined $\displaystyle{ f }$ and $\displaystyle{ g }$:
$\displaystyle{ g(J)=\sum_{I\supseteq J}f(I) }$.
Applying the dual form of the Möbius inversion formula, we have that for any $\displaystyle{ J\subseteq\{1,2,\ldots,n\} }$,
$\displaystyle{ 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 $\displaystyle{ \{1,2,\ldots,n\} }$, ordered by $\displaystyle{ \subseteq }$, thus it holds that $\displaystyle{ \mu(J,I)=(-1)^{|I|-|J|}\, }$ for $\displaystyle{ J\subseteq I }$. Therefore,
$\displaystyle{ 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 $\displaystyle{ A_i, i\in J }$ for any $\displaystyle{ J\subseteq\{1,2,\ldots,n\} }$. For the special case that $\displaystyle{ J=\emptyset }$, $\displaystyle{ f(\emptyset) }$ is the number of elements satisfying no property of $\displaystyle{ A_1,A_2,\ldots,A_n }$, and
$\displaystyle{ 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 $\displaystyle{ N }$ be a positive integer,
$\displaystyle{ g(n)=\sum_{d|n}f(d)\, }$ for all $\displaystyle{ n|N }$
if and only if
$\displaystyle{ f(n)=\sum_{d|n}g(d)\mu\left(\frac{n}{d}\right)\, }$ for all $\displaystyle{ n|N }$,
where $\displaystyle{ \mu }$ is the number-theoretical Möbius function, defined as
$\displaystyle{ \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 $\displaystyle{ N }$, and for any $\displaystyle{ a,b\in P }$, $\displaystyle{ a\le_P b }$ if $\displaystyle{ a|b }$.

## Sieve Method in Number Theory

### The Euler totient function

Two integers $\displaystyle{ m, n }$ are said to be relatively prime if their greatest common diviser $\displaystyle{ \mathrm{gcd}(m,n)=1 }$. For a positive integer $\displaystyle{ n }$, let $\displaystyle{ \phi(n) }$ be the number of positive integers from $\displaystyle{ \{1,2,\ldots,n\} }$ that are relative prime to $\displaystyle{ n }$. This function, called the Euler $\displaystyle{ \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 $\displaystyle{ n }$ is divisible by precisely $\displaystyle{ r }$ different primes, denoted $\displaystyle{ p_1,\ldots,p_r }$. Then $\displaystyle{ \phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right) }$.
Proof.
 Let $\displaystyle{ U=\{1,2,\ldots,n\} }$ be the universe. The number of positive integers from $\displaystyle{ U }$ which is divisible by some $\displaystyle{ p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\} }$, is $\displaystyle{ \frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}} }$. $\displaystyle{ \phi(n) }$ is the number of integers from $\displaystyle{ U }$ which is not divisible by any $\displaystyle{ p_1,\ldots,p_r }$. By principle of inclusion-exclusion, \displaystyle{ \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} }
$\displaystyle{ \square }$

## Reference

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