# 基礎組合工具
在認識組合前，一定要先學會一些重要基礎組合工具，這些工具可以讓我們在計算組合數時有很大的幫助。

## 階乘!
階乘是表示一種累乘，以$n!$表示從$n$乘到1的結果，而階乘可以非常方便於計算組合數。

$$n!=n×(n-1)×...×1$$

### Example 2.1.1
假設今天有5個人要排成一列，則這五個人有幾種排列順序？
:::spoiler Hint:純排列
假設現在有五個空位，第一個位置5個人都可以選擇，則第二個位置剩下4個人可以選擇，第三個位置又剩下3個人選擇，...，以此類推。
則五個人共有5×4×3×2×1種排法，也就是5!。

5!=120種
A:120種
:::
\
除此之外，階乘這個超方便的東西還可以用來表示比較麻煩的計算，像是遇到相同物的排列情況...

### Example 2.1.2
若今天有八種水果要排成一列，分別有1顆西瓜、2顆蓮霧、2顆蘋果、3顆芒果，
則這8個水果共有幾種不同的排列順序？
:::spoiler Hint:可以先將一樣的水果編號，比如1號蓮霧和2號蓮霧，但最後記得除掉相同排列
首先，先假設八種水果都不一樣，則共有8!種排法。
但是，其中包含了相同的水果：2顆蓮霧、2顆蘋果與3顆芒果任意交換順序是一樣的排法。
比如`XXXXXABX`和`XXXXXBAX`(X是除了蓮霧的其他水果，暫時不討論)，我們將2顆蓮霧編號AB，但其實這兩種排法是一樣的，所以數量需要除掉2!，同理2顆蘋果與3顆芒果需要分別除掉2!和3!。
所以就可以計算出這8個水果的排列數為：
$\frac{(全部視為不同物)}{(蓮霧、蘋果和芒果自己的交換是一樣的)}=\frac{8!}{2!2!3!}=3360$

A:3360種
:::
\
寫到這裡可能會有個疑問，為什麼重複的組合數是被「除掉」了而不是「扣掉」？這就要牽扯到乘法原理和加法原理了。

## 乘法原理和加法原理
為什麼要先說乘法原理？單純因為前面的例題都是使用到乘法原理XD
如果兩個情況是**獨立事件**，則這兩個組合情況就可以互相搭配相乘，而這就是**乘法原理**。簡單來說就是一個事件發生的每一種情況都可以對應另一個事件，方法數相互獨立不影響。
像是Ex 2.1.1，第一個位子先選定一個人後，第二個位子就是剩下的四個人做選擇，而第一個位子無論一開始放置的是五人中的哪個，第二個位子始終都剩下4種選擇，而這就需要用乘法原理相乘。
\
那加法原理又是什麼，表示兩個事件的權重相等(發生機率一樣)且不重複的組合，就把兩者組合情況相加。換句話說就是在計算組合題目時分case計算後，所有情況數就是這些case分別的情況數總和。
\
文字說明總是難以理解，但看過題目認識怎麼使用比較重要~

### Example 2.1.3
以下是一個麵店的菜單：

| 主食 | 小菜 | 飲料 |
| -------- | -------- | -------- |
| 牛肉麵 150元 | 皮蛋豆腐 45元 | 可樂 |
| 牛肉湯麵 90元 | 燙青菜 40元 | 雪碧 |
| 酸辣麵 150元 | 滷蛋+海帶+豆干 35元 | 檸檬紅茶 |
| 大魯麵 95元 | | 冬瓜茶 |

而店內推出兩種套餐優惠方案：

| A套餐 199超值全餐 | B套餐 200吃飽飽|
| -------- | -------- |
| 主食+任意小菜+飲料 | 主食+3道小菜 |

今天小明想點一個套餐當宵夜，問小明共有幾種餐點搭配組合？

:::spoiler Hint:分別計算A套餐和B套餐的組合可能
A套餐組合：4種主食/3種小菜/4種飲料
根據乘法原理，A套餐共有4×3×4=48種組合。
B套餐組合：4種主食+全部小菜
則B套餐只有4種組合。
最後根據加法原理，所有套餐的餐點搭配可能有48+4=52種。
A:52種
:::

## 排列P
排列P是綜合前面的階乘與乘法原理的好用工具，讓我們延伸前面例題舉例。
### Example 2.1.4
延伸一下Ex 2.1.3，如果明天和後天小明也想要吃套餐，只不過希望這三天選擇都是不一樣的套餐組合，則小明這三天的餐點搭配有幾種可能？
:::spoiler Hint:第一天有52種，則第二天剩下...？
第二天剩下51種(扣掉第一天的選擇)，第三天又剩下50種，則這三天的選擇共有52×51×50=132600種

A:132600種
:::
\
而這樣的排列我們便可以用P表示，記做$P_{3}^{52}=52×51×50$
定義$P_{n}^{m}$為m種組合取n天的組合數量，想像成這m種組合的任意排列但其中m-n種為相同物，若除掉這些排列數後便是這n天的排列數，則公式可表示為：
$$P_{n}^{m}=\frac{m!}{(m-n)!}$$
當我們有了好用的排列P後，我們就可以更廣泛的運用在其他組合上，比如以下的經典體型：
### Example 2.1.5
今天有7人參加舞會，若想選擇其中4人排列一直線拍照，則共有多少取法？
:::spoiler Hint:看看是否能利用P表示？
在7人中取4人做有順序排列，故有$P_{4}^{7}=7×6×5×4=840$種排列

A:840種
:::

## 組合C
除了排列P，還有另一個好用工具便是組合C，我們將前面例題延伸想想看：
### Example 2.1.6
同Ex 2.1.5，若今天在這7人中有4人可以獲得飲料(皆相同)，則共有幾種可能？
:::spoiler Hint:與前面不同的是這4人飲料是相同物，沒有排列順序
我們知道4個人的排列數有$P_{4}^{7}=840$種，但這時已經考慮了4人的排列順序，又因為飲料皆相同，則要除掉4!的排列數。
故組合數有$\frac{840}{4!}=35$種

A:35種
:::
定義$C_{n}^{m}$為m人中取n人的情況數，表示這n人沒有排列，故要比$P_{n}^{m}$多除掉一個n!，以公式表示為：
$$C_{n}^{m}=\frac{P_{n}^{m}}{n!}=\frac{m!}{(m-n)!n!}$$
有了超好用的組合C後，綜合所有前面所學，我們已經可以解決大部分的高中排列組合題目了XD

## 排容原理(容斥原理)
前面學完所有基本的組合符號，接下來要介紹的是運算技巧與方法。
有時遇到正推複雜的運算時，不妨逆向思考，**逆推**反而更簡單！也就是算出不合的解再扣掉重複的意思，而這也就是排容原理的精髓。
用數學公式敘述就是：
$$n(A\cup B)=n(A)+n(B)-n(A\cap B)$$
其中A、B表示兩不同事件集合，$n(X)$ 表示集合裡面的元素數量。$A\cap B$ 表示A**或**B的情況數，而 $A\cup B$ 表示A**和**B同時發生的情況數。
用個例題解釋最快XD
### Example 2.1.7
甲乙丙丁4個人排成一列，問甲排首或是乙排第二個的組合數有多少種？
:::spoiler Hint:用排容原理計算，A=甲排首、B=乙排第二
甲排首+乙排第二-甲排首**且**乙排第二=甲排首**或**乙排第二
A甲排首有3!=6種，不失一般性，B乙排第二也有6種，而甲排首且乙排第二就只有2!=2種。
$n(A)=n(B)=6，n(A\cap B)=2$
則知道甲排首或乙排第二有：
$\begin{split}n(A\cup B)&=n(A)+n(B)-n(A\cap B)\\&=6+6-2=10\end{split}$

A:10種
:::
這題還可以繼續延伸...

## 笛摩根定律(De Morgan's laws)
先來延伸前面例題~
### Example 2.1.8
甲乙丙丁4個人排成一列，試求甲不排首且乙不排第二個的組合數有多少種？
:::spoiler Hint:前面已經算過**甲排首或乙排第二**了...
四個人隨便排的排列數有4!=24種，扣掉甲排首或以排第二就會是甲不排首且乙不排第二了。
則組合數有4!-10=14種

A:14種
:::
而這種計算方法便使用到笛摩根定律，扣除了部分情況計算餘集的方法，以數學公式表示為：
$$(A\cup B)'=A'\cap B'$$
同時取餘集變成
$$(A\cap B)'=A'\cup B'$$

# 有趣例題講解
### Problem 2.1.1
甲乙丙丁戊5個人排成一列，規定乙一定在甲的右邊，且丙一定在戊的左邊，求這五人共有幾種排列方法？
:::spoiler :relieved: Hint:階乘排列+對稱性
5個人的排列有5!
乙可能在甲左側或右側，因**對稱性**可知兩種情況數量相等。
同理，因**等價性**，丙與戊的關係相等於乙和甲。
則排列數有$5!×\frac{1}{2}×\frac{1}{2}=30$

A:30種
:::

>[!Important] 延伸問題
>改變排列規則，若規定乙一定在甲左側，且丙也在甲左側，則排列數有幾種？
>:::spoiler :relieved: Hint:獨立分析甲乙丙三人
>先分析甲乙丙三人，可能的排列有`乙丙甲`或`丙乙甲`2種情況，而剩餘丁戊兩人沒有額外規定，可以用**插空法**加入排列。
>丁共有4個空格可以插入(3人有4個空格)，而戊就有5個空格可以插入(4人)
>也可以將甲乙丙視為同物和丁戊做排列
>則共有$2×4×5=40$種組合
>
>A:40種
>:::

### Problem 2.1.2
若今天甲乙丙丁戊己6人要拍成一列，因為甲乙是情侶，不想要拍照離開彼此，所以他們兩個位置必定要相鄰，則6人共有幾種排列方式？
:::spoiler :relieved: Hint:將甲乙視為一體
先將`甲乙`視為一體跟剩下4人做排列，共有5!種排列，而`甲乙`自己有2!種排列。
故總排列有$5!×2!=240$種

A:240種
:::

### Problem 2.1.3
繼續上題P 2.1.2，若丙丁兩人是死對頭，不想在拍照時排在一起，則此六人排列情況共有幾種？
:::spoiler :relieved: Hint:視為一體+扣除
承P 2.1.2，已經知道`甲乙`相鄰的排列數有240種，接著分析`甲乙`且`丙丁`相鄰再扣除。
六人排列變成`甲乙` `丙丁`戊己4人排列，乘上一體的兩人排列，共有4!×2!×2!=96種。
則`甲乙`相鄰丙丁分離的排列數有240-96=144種

---
<另解> 使用插空法
先排列`甲乙`戊己3個總共有3!×2!種排列
接著將丙丁插空到3個群體間，共有4個空格，排列數有$P_{2}^{4}$
綜合以上可知排列數有$3!×2!×P_{2}^{4}=144$種

A:144種
:::

### Problem 2.1.4
一班上共有40位學生，今天任意選取兩位同學擔任今天的值日生，問共有多少取法？
:::spoiler :relieved: Hint:組合C取人
在40人中取2人不排列，故取法有$C_{2}^{40}=780$種

A:780種
:::

### Problem 2.1.5
今天班上有9人，為了參加活動需將所有同學平分成三組，問有多少種分配方法？
:::spoiler :relieved: Hint:先取人+隊伍排列
假設分成三組編號一二三，則第一組的學生在9人中取3人，有$C_{3}^{9}$種。
同理，第二組有$C_{3}^{6}$種、第三組有$C_{3}^{3}$種。
但因為組其實不會有編號，也就是需要除掉組之間的交換可能，所以要再除3!
綜合上述，學生的可能分配方法共有：
$C_{3}^{9}×C_{3}^{6}×C_{3}^{3}×\frac{1}{3!}=280$種

A:280種
:::

> [!Important] 延伸問題
> 若今天班上有8個人，為了參加活動需將所有學生分成三組，分別有兩人、三人、三人，問共有多少種分配方法？
> :::spoiler :relieved: Hint:一樣先取人+隊伍排列
> 在8人中取2人為第一組，有$C_{2}^{8}$種，接著剩下的6人取3人當第二組，有$C_{3}^{6}$種，最後的三人為第三組。
> 3人都兩組交換不影響分配，所以要除2!的交換組合。
> 綜合上述可知分配方法共：
> $C_{2}^{8}×C_{3}^{6}×C_{3}^{3}×\frac{1}{2!}=280$種
>
> A:280種
> :::

### Problem 2.1.6
某冰淇淋店最少需準備n桶不同口味的冰淇淋，才能滿足廣告所稱「任選兩球不同口味冰淇淋的組合數超過100種」。試問來店顧客從n桶中任選兩球（可為同一口味）共有幾種方法？(111學測數學A)
:::spoiler :relieved: Hint:用C試著解出n
要在n桶冰淇淋中取2個不同口味共有$C_{2}^{n}$種，則用不等式求n
$C_{2}^{n}>100\Rightarrow n(n-1)>200\Rightarrow n\geq 15$
則取n=15，接著加上兩球同一口味的情況15種
$C_{2}^{15}+15=105+15=120$種

A:120種
:::

### Problem 2.1.7
從男生5人，女生3人中選出4人組成代表團。則代表團中有男生也有女生的選法有幾種？
:::spoiler :relieved: Hint:可正推或逆推(逆推可能比較快？)
分析4個人的性別組合，有3種case：
(1)3男1女
先在5男中取3人、再從3女中取1人，共有$C_{3}^{5}C_{1}^{3}$種
(2)2男2女
先在5男中取2人、再從3女中取2人，共有$C_{2}^{5}C_{2}^{3}$種
(1)1男3女
先在5男中取1人、再從3女中取3人，共有$C_{1}^{5}C_{3}^{3}$種
則綜合以上的情況，得出選法共有：
$C_{3}^{5}C_{1}^{3}+C_{2}^{5}C_{2}^{3}+C_{1}^{5}C_{3}^{3}=30+30+5=65$種

---
<另解>使用扣除法
題目欲在8人中選出4人，不過不能取到全為男生或是全為女生，但女生只有3人，所以只需要討論4人全部為男生的情況。
故總情況數為$C_{4}^{8}-C_{4}^{5}=70-5=65$

A:65種
:::

### Problem 2.1.8
有11個導遊，其中5人只會說國語，另外4人只會說英語，還有2人會說國語和英語兩種，若現在需要出動4位會說國語和4位說英語的導遊，問共有幾種選擇方法？
:::spoiler :cold_sweat: Hint:有一個好的分case技巧(加法原理)
最麻煩的部分是2位都會說的導遊，我們分成三種情況討論：
(1)0位都會說的導遊在國語
則國語的5人取4人，英語的有4+2人取4人，共有$C_{4}^{5}C_{4}^{6}=75$種
(2)1位都會說的導遊在國語
先在都會說的取1位導遊出來，則國語變成5人取3人，英語的有4+1人取4人，共有$C_{1}^{2}C_{3}^{5}C_{4}^{5}=100$種
(3)2位都會說的導遊在國語
則國語變成5人取2人，英語就4人全取，共有$C_{2}^{5}C_{4}^{4}=10$種
綜合上述三種情況，所有的選擇方法共有：
75+100+10=185種

A:185種
:::