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

• Enumeration 9A
  *
  • Unordered Selections with Repetition
  • Property
  • Binomail Theorem

Enumeration 9A

Unordered Selections with Repetition

The number of unordered selections, without repetitions, of $m$ things from a set of size $n$ is

$\frac{n(n-1)\dotsc (n-m+1)}{m!}\overset{\bigtriangleup }{=} \begin{pmatrix} n \\ m \end{pmatrix}(binomial\ coefficient)$

Example 1
Let $A$ be a set with $|A|=8$

1. How many three-element subsets(3-subsets) does A have?
   Answer:

$\begin{pmatrix} 8 \\ 3 \end{pmatrix}=\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56$

2. How many 5-subsets does $|A|$ have?
   Answer:

$\begin{pmatrix} 8 \\ 5 \end{pmatrix}$

3. How many 9-subsets does $|A|$ have?
   Answer: 上面比下面小的时候，直接就等于0。

$\begin{pmatrix} 8 \\ 9 \end{pmatrix}=0$

Property

Pascal's Identity

$\begin{pmatrix} n \\ r \end{pmatrix}=\begin{pmatrix} n-1 \\ r-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ r \end{pmatrix}$

$\begin{pmatrix}n \\ r\end{pmatrix}$ is the number of r-subsets of $\{1,2,3,\dotsc ,b\}$
$\begin{pmatrix}n-1 \\ r-1\end{pmatrix}$ is the number of r-subsets with $n$
$\begin{pmatrix}n-1 \\ r\end{pmatrix}$ is the number of r-subsets without $n$
Pascal's Triangle

Clearly $\begin{pmatrix}n \\ r\end{pmatrix}=\begin{pmatrix}n \\ n-r\end{pmatrix}$ for $r\le n$

Binomail Theorem

$(x+y)^n=\sum_{r=0}^{n}=\begin{pmatrix}n \\ r\end{pmatrix}x^{n-r}y^r$

Example 2

$\begin{pmatrix}n \\ 0\end{pmatrix} + \begin{pmatrix}n \\ 1\end{pmatrix} + \dotsc + \begin{pmatrix}n \\ n\end{pmatrix} = 2^n$

Proof:

$(x+y)^n=\sum_{r=0}^{n}=\begin{pmatrix}n \\ r\end{pmatrix}x^{n-r}y^r$

substituting $x=y=1$ to the above identity

$2^n=(1+1)^n=\sum_{r=0}^{n}\begin{pmatrix}n \\ r\end{pmatrix}$

Example 3

$\begin{pmatrix}n \\ 0\end{pmatrix}^2 + \begin{pmatrix}n \\ 1\end{pmatrix}^2 + \dotsc + \begin{pmatrix}n \\ n\end{pmatrix}^2 = \begin{pmatrix}2n \\ n\end{pmatrix}$

Proof:
Note $(1+x)^n(1+x)^n=(1+x)^{2n}$. On the left-hand side, the coefficient of $x^n$ in $(1+x)^n(1+x)^n$

$\begin{pmatrix}n \\ 0\end{pmatrix}\begin{pmatrix}n \\ n\end{pmatrix}+\begin{pmatrix}n \\ 1\end{pmatrix}\begin{pmatrix}n \\ n-1\end{pmatrix}+\begin{pmatrix}n \\ 2\end{pmatrix}\begin{pmatrix}n \\ n-2\end{pmatrix}+\dotsc + \begin{pmatrix}n \\ n\end{pmatrix}\begin{pmatrix}n \\ 0\end{pmatrix}$

since

$(1+x)^n=\begin{pmatrix}n \\ 0\end{pmatrix}+\begin{pmatrix}n \\ 1\end{pmatrix}x+\dotsc +\begin{pmatrix}n \\ r\end{pmatrix}x^r+\begin{pmatrix}n \\ n\end{pmatrix}x^n$

Example 4

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

Example 5
Note $(x+y)^n=\sum_{r=0}^n\begin{pmatrix}n \\ r\end{pmatrix}x^{n-r}y^r$
Let $x=1$ and $y=-1$ then we have

$0=(1-1)^n$