这是台湾清华赵启超教授离散数学11A11B课程的笔记。

• 11AB Enumeration

11AB Enumeration

Proof
We will show that every element $x$ of the union makes a net contribution of 1 to the right-hand side suppose $x$ belongs to precisely $r, 1\le r \le n$ of the sets $A_1, A_2, \dotsc, A_n$.

$\alpha _1=|A_1|+|A_2|+\dotsc +|A_n|$

$x$ contributes $r$ to $\alpha _1$
$\alpha _2$, $x$ contributes 1 to $|A_i \cap A_j|$, when both $A_i$ and $A_j$ are among the $r$ sets which contain $x$. There are $\begin{pmatrix} r \\ 2\end{pmatrix}$ such pairs, and so $\begin{pmatrix} r \\ 2\end{pmatrix}$ is the contribution of $x$ to $\alpha _2$.
In general, the contribution of $x$ to $\alpha _i, 1\le i \le r$ is $\begin{pmatrix} r \\ i\end{pmatrix}$.
If $i>r$, the contribution of $x$ to $\alpha _i$ is 0.
Hence the net contribution of $x$ to the right-hand side is $\begin{pmatrix} r \\ 1\end{pmatrix}-\begin{pmatrix} r \\ 2\end{pmatrix}+\dotsc +(-1)^{i-1}\begin{pmatrix} r \\ i\end{pmatrix}+\dotsc +(-1)^{r-1}\begin{pmatrix} r \\ r\end{pmatrix}=\begin{pmatrix} r \\ 0\end{pmatrix}$

since $\begin{pmatrix} r \\ 0\end{pmatrix}-\begin{pmatrix} r \\ 1\end{pmatrix}+\begin{pmatrix} r \\ 2\end{pmatrix}+\dotsc +(-1)^{r}\begin{pmatrix} r \\ r\end{pmatrix}=0$

Example 1
Let $\Phi(n)$ denote the number of integers $m$ in the range $1\le m \le n$ such that $m$ and $n$ are relatively prime, i.e., $gcd(m,n)=1$
$\Phi(n)$ is Euler's Phi Function or Euler's Totient Function

$\Phi(n)=|\{m:1\le m\le n,gcd(m,n)=1\}|$

$\Phi(p)=p-1$ if $p$ is a prime.
Find $\Phi(60)$
We have $60=2^2\times 3\times 5$