3-3. 組合

Combination Formula

• $n$ 件相異物不允許重複取 $r$ 件組合的方法數: $\text{C}^n_r$ = $\text{C}$($n$, $r$) = $\dbinom{n}{r}$ = $\dfrac{ n(n - 1)...(n - r + 1)}{r!}$ = $\dfrac{n!}{(n - r)!r!}$, $n \ge r$

  $\because$ 組合 = 無次序排列 = $\dfrac{\text{P}^n_r}{r!}$

• $n$ 件相異物允許重複取 $r$ 件組合的方法數: $\dbinom{n + r - 1}{r}$ = $\dfrac{(n + r - 1)!}{r!(n - 1)!}$

  $^{ex.}$ 4 件相異物 A, B, C, D 無次序取 7 件作組合:

取	A	B	C	D
AABBCCD	$xx$	$xx$	$xx$	$x$
AACCCCD	$xx$		$xxxx$	$x$

$\rightarrow$ 等同於: $r$ 個 $x$ 與 $n$ - $1$ 個間隔的不全相異物排列，其等價問題: 1. $r$ 個相同球放入 $n$ 個相異箱子，允許空箱之方法數 2. $x_1$ + $x_2$ + ... + $x_n$ = $r$ 之非負整數整數解個數

$\rightarrow$ Corollary: $\color{red}{n}$ 個箱內必有物 $\Rightarrow \dbinom{n + (r {\color{red}{- n}}) - 1}{r {\color{red}{- n}}}$ = $\dbinom{r - 1}{r - n}$ = $\dbinom{r - 1}{n - 1}$ 1. $r$ 個相同球放入 $n$ 個相異箱子，不允許空箱之方法數 2. $x_1$ + $x_2$ + ... + $x_n$ = $r$ 之正整數整數解個數

$Example$: $\quad$ $x_1$ + $x_2$ + ... + $x_n \le r$ 之非負或正整數整數解個數? $solution$: $\quad$ 令 $x_{n + 1}$ = $r$ - ($x_1$ + $x_2$ + ... + $x_n$) $\Rightarrow x_1$ + $x_2$ + ... + $x_n$ + $x_{n + 1}$ = $r$, $x_{n + 1} \ge$ (正整數: $>$) $0$, 其中 $x_{n + 1}$ 稱為鬆弛變數 (slack variable)

Theorem of Combination

$\dbinom{n}{r}$ = $\dbinom{n - 1}{r}$ + $\dbinom{r - 1}{r - n}$

proof:

利用組合證法，$n$ 個相異物取 $r$ 個組合，固定一物 $A$

• 不取 $A$: $\dbinom{n - 1}{r}$

• 取到 $A$: $\dbinom{n - 1}{r - 1}$

$\because$「沒取到 $A$ 」與「有取到 $A$」為互斥事件 $\therefore \dbinom{n}{r}$ = $\dbinom{n - 1}{r}$ + $\dbinom{r - 1}{r - n}$

Corollary of Combination

$\dbinom{n}{r}$ = $\dbinom{n - 2}{r - 2}$ + $2 \dbinom{n - 2}{r - 1}$ + $\dbinom{n - 2}{r}$

固定一物 $A$ 和 $B$

• 取到 $A$ 和 $B$: $\dbinom{n - 2}{r - 2}$

• 不取 $A$ 或 $B$: $\dbinom{n - 2}{r - 1}$

• 不取 $A$ 和 $B$: $\dbinom{n - 2}{r}$

Vandermonde's Convolution

$\dbinom{r + s}{n}$ = $\dbinom{r}{0} \dbinom{s}{n}$ + $\dbinom{r}{1} \dbinom{s}{n - 1}$ + ... + $\dbinom{r}{n} \dbinom{s}{0}$ = $\displaystyle\sum_{k=0}^{n} \dbinom{r}{k} \dbinom{s}{n - k}$

$\Rightarrow r$ = $s$ = $n$ 代入: $\dbinom{2n}{n}$ = $\dbinom{n}{0}^2$ + $\dbinom{n}{1}^2$ + ... + $\dbinom{n}{n}^2$ = $\displaystyle\sum_{k=0}^{n} \dbinom{n}{k}^2$

Binomial Theorem

($x$ + $y$)$^n$ = $\displaystyle\sum_{k=0}^{n} \dbinom{n}{r} x^r y^{n - r}$, $n \in Z^+$

proof:

($x$ + $y$)$^n$ 展開後 $x^r y^{n - r}$ 之係數 $\dbinom{n}{r}$ 相當於「 $n$ 個 bits 中恰含 $r$ 個 1 與 $n$ - $r$ 個 0 之 bit string 個數」

Corollary of Binomial Theorem

($x_1$ + $x_2$ + ... + $x_k$)$^n$ = $\displaystyle\sum_{\tiny{n = \displaystyle\sum_{i=1}^{k} n_k, \; 0 \le n_i \le n_k}} \dbinom{n}{n_1, n_2, ..., n_k} {x_1}^{n_1} {x_2}^{n_2}$ ... ${x_k}^{n_2}$, $n \in Z^+$