# 組合數延伸性質
先前的組合C都是使用於取物或是排列形況計算，但組合數其實還有很多有趣的性質，這些性質可以幫助我們化簡組合數，甚至是用另一個方式理解組合數！

## 巴斯卡三角形(Pascal's triangle)
一提到組合數就不得不提一下巴斯卡三角形，巴斯卡三角形是一個很特別的數列，長像是一個無限延伸的三角形，呈左右對稱，每一項都會是上方兩項的合，而巴斯卡三角形的前面幾層看起來會像是這樣：
會發現第3層的`2`就是由上面兩個1的總合而來，同理，其他數字也可以這樣加來計算得出。
而觀察之後可能會發現，巴斯卡三角形和組合數似乎有這樣一個關係：
如果將每一層的層數和位置數用組合數表示，會發現每一項都剛好符合巴斯卡三角形，而這也是巴斯卡三角形和組合數很重要的關係。

如果你問我這些巴斯卡三角形的數字是怎麼推得的，最簡單的說明方式就是用多項式說明。
## 多項式的巴斯卡三角形
可以先將每一層看作是$(x+y)^{n}$，其中$n$就是層數，利用二項式定理，可以簡單列出前幾層的展開式：
第一層：$(x+y)^{0}=1$
第二層：$(x+y)^{1}=x+y$
第三層：$(x+y)^{2}=x^{2}+2xy+y^{2}$
第四層：$(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}$
第五層：$(x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{2}+4xy^{3}+y^{4}$
觀察一下可以發現，多項式的展開式係數剛好就是巴斯卡三角形的數字，而根據最一開始可以知道的巴斯卡三角形數字是由上面兩項相加而得，利用多項式理解就是**因式**的關係。

比如第四層的$3x^{2}y$就可以由第三層的$x^{2}$或$2xy$獲得，而要從第三層變成第四層就要再多乘一次$(x+y)$，這樣第三層的$x^{2}$乘上y、$2xy$乘上x後就都變成了$x^{2}y$，所以第四層的$x^{2}y$係數就會是第三層的$x^{2}$和$2xy$係數總和。同理，其他數字也可以用相同方式推導得出。

至為什麼係數剛好就是組合數C？這時候就要回到多項式來看
一樣以第四層的$3x^{2}y$舉例，先把$(x+y)^{3}$展開成$(x+y)×(x+y)×(x+y)$，根據乘法公式，$x^{2}y$就是在三個(x+y)中取一個y，剩下的兩個是x，所以總共會有$C_{1}^{3}$個，而這就是$3x^{2}y$的係數。同理，其他數字也可以用相同方式推導得出。

會了組合數與二項式定理的關係後，來試試底下的例題：
### Example 2.2.1
定義函數$f(x)=(x+y+z)^{4}$，則在$f(x)$的展開式中，$xyz^{2}$的係數是多少？$x^{3}y$的係數是多少？$x^{2}yz^{2}$的係數是多少？
:::spoiler Hint:利用與多項式的巴斯卡三角形一樣的展開技巧試試看
先將$f(x)$看作$(x+y+z)×(x+y+z)×(x+y+z)×(x+y+z)$，而xyz^{2}表示在四個(x+y+z)中取了1個x、1個y，其餘為z，則共有$C_{1}^{4}C_{1}^{3}=12$個，而這就是$xyz^{2}$的係數。

同理，$x^{3}y$的係數就是取3個x、1個y，也就是$C_{3}^{4}C_{1}^{1}=4$
最後$x^{2}yz^{2}$中因為有5個未知數，但$f(x)$只有4個(x+y+z)因式，所以展開式中不會存在$x^{2}yz^{2}$，則係數為0。

A:(1)12 (2)4 (3)0
:::

## 組合數延伸性質
透過巴斯卡三角形與多項式，我們可以簡單整理出幾個組合數會有的性質：
:::success
$Lemma\ 1:$組合數對稱性(Symmetry Lemma)
$$C_{n}^{m}=C_{m-n}^{m}(m>n)$$
:::
要證明這個引理也很簡單，可以透過組合數定義或是巴斯卡三角形證明。
1. 組合數定義證明
根據定義可以知道：
$C_{n}^{m}=\frac{m!}{n!(m-n)!}=\frac{m!}{(m-n)![m-(m-n)]!}=C_{m-n}^{m}$
2. 說故事證明
有些證明也可以創造一個事件說明就好。
$C_{n}^{m}$就是在m個物中取n個的情況數，也可以視為取m-n個物淘汰，所以也會等於$C_{m-n}^{m}$
如果要便於記憶，就知道巴斯卡三角形是對稱的就好了！
---

:::success
$Lemma\ 2:$帕斯卡恆等式(Pascal's Identity)
$$C_{n+1}^{m+1}=C_{n}^{m}+C_{n+1}^{m}(m>n)$$
:::
這個引理其實就是巴斯卡三角形的性質，任一項會等於上面兩項的合。
1. 組合數證明
$\begin{split}C_{n}^{m}+C_{n+1}^{m}&=\frac{m!}{n!(m-n)!}+\frac{m!}{(n+1)!(m-n-1)!}(通分)\\&=\frac{(n+1)×m!+(m-n)×m!}{(n+1)!(m-n)!}=\frac{(m+1)×m!}{(n+1)!(m-n)!}\\&=\frac{(m+1)!}{(n+1)![(m+1)-n+1]!}=C_{n+1}^{m+1}\end{split}$
2. 說故事證明
一樣創造一個事件來證明引理。
若教室中有m+1個人，欲選出n+1個人作為代表，假設教室有一人叫做小明，則可以分成兩種情況(有選擇到小明或是沒有選擇到小明)：
(1)若n+1人中包含了小明，則其餘的m人中可選出n人作為代表，共有$C_{n}^{m}$種
(2)若n+1人中不包含小明，則其餘的m人中可選出n+1人作為代表，共有$C_{n+1}^{m}$種
而綜合兩種情況就是在m+1個人選出n+1個人作為代表的組合數，則證明了$C_{n+1}^{m+1}=C_{n}^{m}+C_{n+1}^{m}$

### Example 2.2.2
計算$C_{1}^{3}+C_{2}^{4}+C_{3}^{5}+...+C_{18}^{20}$。
:::spoiler Hint:可以補一項讓數列可以一直化簡
在數列中加一項$C_{0}^{3}$，可以發現加上第一項$C_{1}^{3}$後變成了$C_{1}^{4}$，而這一項又可以跟第二項繼續化簡。
$\begin{split}(C_{0}^{3}+C_{1}^{3})+C_{2}^{4}+C_{3}^{5}+...+C_{18}^{20}&=(C_{1}^{4}+C_{2}^{4})+C_{3}^{5}+...+C_{18}^{20}\\&=C_{2}^{5}+C_{3}^{5}+...+C_{18}^{20}\\&=...=C_{18}^{21}=C_{3}^{21}=1330\end{split}$

A:1330
:::

---

:::success
$Lemma\ 3:$組合數級數求和
$$\sum^{n}_{k=0}C_{k}^{n}=2^{n}$$
:::
這個引理是敘述同一列組合數級數和的公式，也是很重要的計算性質
1. 多項式證明(二項式定理)
我們知道組合數會是二項式定理的展開係數，而$C_{k}^{n}$的和就是$(x+y)^{n}$的係數和，若將$x=y=1$代入，則得到了$C_{0}^{n}+C_{1}^{n}+C_{2}^{n}+...+C_{n}^{n}=(1+1)^{n}=2^{n}$
2. 說故事證明
先創造一個開燈事件，假設有n盞燈，而每一盞燈都會有開、關兩種情況，故所有燈的開關情形組合數有$2^{n}$種。
若逐一分析，當n盞燈中有0盞為開的組合數有$C_{0}^{n}$種；當n盞燈中有1盞為開的組合數有$C_{1}^{n}$種；以此類推；當n盞燈中有n盞為開的組合數有$C_{n}^{n}$種。將上述情況全部加總後為所有燈的開關情形，故也證明了$C_{0}^{n}+C_{1}^{n}+C_{2}^{n}+...+C_{n}^{n}=2^{n}$

### Example 2.2.3
試證明$(x+1)^{n}$的展開式中x的奇數項係數和會等於x的偶數項係數和。
:::spoiler Hint:可以想想x代入多少
先假設x的奇數項係數和是A，偶數項和是B
若x=1代入，則$(1+1)^{n}=2^{n}=C_{0}^{n}+C_{1}^{n}+C_{2}^{n}+...+C_{n}^{n}=A+B$
若x=-1代入，則$(-1+1)^{n}=0^{n}=C_{0}^{n}-C_{1}^{n}+C_{2}^{n}-...+(-1)^{n}C_{n}^{n}=A-B$
將兩式相加後可以得到$2A=2^{n}+0$，則$A=2^{n-1}$，$B=2^{n-1}$
故證明了A=B，也就是奇數項係數和等於偶數項和。

---
<另解>利用巴斯卡三角形定義
我們可以知道，奇數項係數會是$C_{0}^{n}$、$C_{2}^{n}$、$C_{4}^{n}...$，如果利用帕斯卡恆等式推得上一層，也就是把每一項分兩項看，則$C_{0}^{n}=C_{0}^{n-1}$、$C_{2}^{n}=C_{1}^{n-1}+C_{2}^{n-1}$、$C_{4}^{n}=C_{3}^{n-1}+C_{4}^{n-1}...$
所以所有奇數項的和就會是$C_{0}^{n-1}+C_{1}^{n-1}+C_{2}^{n-1}+...+C_{n-1}^{n-1}=2^{n-1}$
同理，偶數項係數會是$C_{1}^{n}$、$C_{3}^{n}$、$C_{5}^{n}...$，也把每一項都拆兩項來看，則$C_{1}^{n}=C_{0}^{n-1}+C_{1}^{n-1}$、$C_{3}^{n}=C_{2}^{n-1}+C_{3}^{n-1}$、$C_{5}^{n}=C_{4}^{n-1}+C_{5}^{n-1}...$
所以所有偶數項的和也是$C_{0}^{n-1}+C_{1}^{n-1}+C_{2}^{n-1}+...+C_{n-1}^{n-1}=2^{n-1}$
綜合上述可以知道所有奇數項係數和等於偶數項係數和

:::
---

:::success
$Lemma\ 4:$范德蒙恆等式(Vandermonde's Identity)
$$C_{r}^{m+n}=\sum^{r}_{k=0}C_{k}^{m}C_{r-k}^{n}(m>n)$$
:::
這個引理雖然看起來很複雜，但其實只須要說一個故事就能證明
假設今天有兩個箱子，左邊箱子有m顆球，右邊箱子有n顆球，欲在這m+n顆球中取出r顆。
則所有情況數可以分析左邊箱子就好。
若左邊箱子選了0顆球，則右箱就要選$C_{r}^{n}$顆；
若左邊箱子選了1顆球，則右箱就要選$C_{r-1}^{n}$顆；
同理，若左邊箱子選了k顆球，則右箱就要選$C_{r-k}^{n}$顆。
將上述所有情況加總後就會是把兩箱子混在一起，在m+n顆球中取出r顆的組合數，為$C_{r}^{m+n}$種。

### Exmaple 2.2.4
試證明：
$$(C_{0}^{n})^{2}+(C_{1}^{n})^{2}+(C_{2}^{n})^{2}+...+(C_{n}^{n})^{2}=(C_{n}^{2n})^{2}$$
:::spoiler Hint:結合組合數對稱性
利用組合數對稱性，將$(C_{0}^{n})^{2}$換成$C_{0}^{n}C_{n}^{n}$，同理將$(C_{1}^{n})^{2}$換成$C_{1}^{n}C_{n-1}^{n}$，以此類推。
則$(C_{0}^{n})^{2}+(C_{1}^{n})^{2}+(C_{2}^{n})^{2}+...+(C_{n}^{n})^{2}=C_{0}^{n}C_{n}^{n}+C_{1}^{n}C_{n-1}^{n}+C_{2}^{n}C_{n-2}^{n}+...+C_{n}^{n}C_{0}^{n}$
最後利用Vandermonde's Identity可知$C_{0}^{n}C_{n}^{n}+C_{1}^{n}C_{n-1}^{n}+C_{2}^{n}C_{n-2}^{n}+...+C_{n}^{n}C_{0}^{n}=(C_{n}^{2n})^{2}$

故$(C_{0}^{n})^{2}+(C_{1}^{n})^{2}+(C_{2}^{n})^{2}+...+(C_{n}^{n})^{2}=(C_{n}^{2n})^{2}$得證

:::

---
說故事證明雖然不是非常嚴謹的證明，但在組合理解與計算上卻有很大的幫助，有時候計算組合題型時也可以將題目轉化成另一個故事形式來計算，直接將組合數化簡成容易理解的形式！直接轉化題目技巧：[進階-組合初步處理](/14-bAetUR6qM-uEUMqCbXw)

# 有趣例題講解
### Problem 2.2.1
試求$C_{0}^{12}+2C_{1}^{12}+3C_{2}^{12}+...+12C_{12}^{12}$？
:::spoiler :relieved: Hint:試試組合數對稱性
令$S=C_{0}^{12}+2C_{1}^{12}+3C_{2}^{12}+...+12C_{12}^{12}$
而根據組合數多稱性可以改寫$S=C_{12}^{12}+2C_{11}^{12}+3C_{10}^{12}+...+12C_{0}^{12}$
把兩式相加後得到$2S=12(C_{0}^{12}+C_{1}^{12}+C_{2}^{12}+...+C_{12}^{12})=12×2^{12}$
則$S=12×2048=24576$

A:24576
:::

### Problem 2.2.2
設$(1+\sqrt{2})^{6}=a+b\sqrt{2}$，其中a,b為整數。則b的值為？(103學測數學)
:::spoiler :relieved: Hint:試試二項式定理
$(1+\sqrt{2})^{6}=(1+2C_{2}^{6}+4_{4}^{6}+8)+(C_{1}^{6}+2C_{3}^{6}+4C_{5}^{6})\sqrt{2}$
$b=C_{1}^{6}+2C_{3}^{6}+4C_{5}^{6}=6+40+24=70$

A:70
:::

### Problem 2.2.3
關於組合數與二項式定理的敘述，下列何者正確？
(1) $C_{50}^{100}>2^{50}$
(2) $C_{8}^{20}+C_{8}^{21}=C_{9}^{21}$
(3) $C_{1}^{10}+C_{2}^{10}+...+C_{10}^{10}=2^{10}$
(4) $C_{0}^{8}+2C_{1}^{8}+4C_{2}^{8}+...+2^{8}C_{8}^{8}=3^{8}$
(5) $C_{0}^{6}C_{4}^{4}+C_{1}^{6}C_{3}^{4}+C_{2}^{6}C_{2}^{4}+C_{3}^{6}C_{1}^{4}+C_{4}^{6}C_{0}^{4}=C_{4}^{10}$
:::spoiler :cold_sweat: Hint:組合數延伸性質
將每個選項逐步分析，其中可能包含不同的組合數延伸性質
(1)$C_{50}^{100}=\frac{100×99×98×...×51}{50×49×48×...×1}>\frac{100×98×96×...×2}{50×49×48×...×1}=2^{50}$
(2)根據帕斯卡恆等式，$C_{9}^{21}=C_{8}^{20}+C_{9}^{20}$，很明顯$C_{9}^{20}\neq C_{8}^{21}$
(3)組合數的級數求和，$2^{10}=C_{0}^{10}+C_{1}^{10}+C_{2}^{10}+...+C_{10}^{10}$，題目中少了一項$C_{0}^{10}$
(4)利用二項式定理$C_{0}^{8}+2C_{1}^{8}+4C_{2}^{8}+...+2^{8}C_{8}^{8}=(1+2)^{8}=3^{8}$
(5)根據Vandermonde's Identity，假設左邊箱子有6顆球，右邊箱子有4顆球，則若要在這10顆球中取4顆的情況數可以看成左箱分別取了1、2、3、4顆球，則說明了$C_{0}^{6}C_{4}^{4}+C_{1}^{6}C_{3}^{4}+C_{2}^{6}C_{2}^{4}+C_{3}^{6}C_{1}^{4}+C_{4}^{6}C_{0}^{4}=C_{4}^{10}$

A:(1)(4)(5)
:::

### Problem 2.2.4
若$w+x+y+z=3$，問(w,x,y,z)的所有非負整數解$C_{w}^{3}C_{x}^{4}C_{y}^{5}C_{z}^{6}$的總和為？
:::spoiler :relieved: Hint:利用Vandermonde's Identity
4個未知數可以表示4個箱子分別要取的球數，而4個箱子內分別有3、4、5、6顆球，則題目所求為總共18顆球取4顆的情況數。
$C_{4}^{18}=\frac{18×17×16×15}{4×3×2×1}=3060$

A:3060
:::