---
# System prepended metadata

title: 自創-組合機率解
tags: [進階組合]

---

# 組合機率解
組合機率解是我自己在解組合題目時自創的工具，機率解可以簡化許多分case的事件。結合換句話說的技巧，一個組合題目就可以用機率解一條式子解出答案！
用自己的理解簡化題目可以先一步看透題目的演算法，在計算特定數值的情況也變得不困難了。

## 對稱性(有A就有B)
對稱性是最普遍也最常使用的性質，如果可以刻意使用對稱性找到相同的case，則可以大大簡化計算複雜度。
對稱性的例子最常見的就是骰子，若同時丟兩顆骰子並分析點數總和，則會得到以下圖表：
![兩顆骰子點數和二維圖](https://hackmd.io/_uploads/Bkns5yNskl.png =50%x)
不難發現以點數和為7出現次數最多，而其餘點數呈現對稱，比如3的次數和11一樣、4的次數和10一樣等等。
可以把骰子的對稱性理解成難度，丟出總和12的點數雖然困難，但要丟出最小的總和2也一樣難，兩者都只有一種情況符合，呈現對稱性。

如果把點數和的分布圖畫出來就可以更明顯的看到對稱性了：
![兩顆骰子點數和一維圖](https://hackmd.io/_uploads/BJNi6kNj1l.png =66%x)
在這個數據分布圖中可以很明顯地看到，骰子點數和的發生機率會以7維對稱軸呈現兩邊對稱。
可以把對稱性理解成**若A情況發生，則一定會有一個B發生**的意思，既然有「最小的骰子點數和」出現，那麼一定也有「最大骰子點數和」的出現而且機率相等。

有了對骰子對稱性的認識，其實對稱性還可以延伸並用在許多地方。

### Example 2.4.1
同時丟三顆骰子計算點數和，證明出現點數和為偶數的機率為$\frac{1}{2}$。
:::spoiler 解題思路：
先壓界，三顆骰子點數和最小為3，最大為18，又點數和會有對稱性，也就是P(X=3)=P(X=18)，骰子點數和為3的機率等於骰子點數和為18的機率，同理，骰子點數和為k的機率等於骰子點數和為(21-k)的機率。
根據對稱性可以知道骰子點數和為偶數機率=骰子點數和為奇數機率，故機率各為$\frac{1}{2}$
:::
\
這樣的對稱性又稱為**奇偶對稱性**，也就是奇數情況剛好會和偶數出現形況互相配對，也就是奇數情況與偶數情況的對稱性。

## 等價性(A和B本質一樣)
等價性和對稱性的本質很類似，是在說明**A物的權重與B物相等**，比如男女排列時，每個男生和每個女生就是等價的，沒有誰的出現機率比較高；或是很多種水果做排列時，每個水果也都是等價的。

### Example 2.4.2
用1,2,3,4,5五個數字排列成一個五位數，且每個數字不重複，試求小於30000的五位數有幾個？
:::spoiler 解題思路：
小於30000的五位數表示萬位數只能放`1`或`2`，又`1`、`2`數字等價，所以萬位數是1或2的情況數一樣多。
不失一般性假設萬位是1，則後面四位數可以隨便排，有4!種，同理，萬位數是2的也有4!種。
故總數量有2×4!=48種

A:48種
:::
等價性除了物品的等價之外，也可以是case的等價，利用等價性可以同時處理相同的case情形。若能靈活運用等價性的技巧，結合不失一般性的假設，可以分小範圍的case去等價其他的case情況數。

## 不失一般性(A還B先都沒差)
不失一般性是一種假設方式，表示先隨便取一種情況討論，因為這樣的討論並不影響結果，或是其它結果可以用等價性來計算。
比如以下這種填色的討論：

### Example 2.4.3
在一個2×2的正方形表格中填入顏色，共有紅、橙、黃、綠、藍、靛、紫7種顏色，且規定任意相鄰兩格不可為同色，問共有幾種填法？
![2×2表格](https://hackmd.io/_uploads/SyC3T-dske.png =20%x)
:::spoiler Hint:不失一般性先假設其中一格的顏色
因為顏色相互等價，所以不失一般性可以假設左上角填入了紅色(其他顏色可以仿照此情形)。
![2×2表格填色_紅](https://hackmd.io/_uploads/B1WlxG_okg.png =20%x)
若左上角為紅色，則需要分析相鄰兩格(星號位置)的可能下列兩種情況：
(1)相鄰兩格同色
除了紅色還有6個顏色可以填，不失一般性假設星號填入橙色，又最後右下角還可以填入6種顏色，共有36種情況。
(2)相鄰兩格不同色
除了紅色還有6個顏色可以填，不失一般性假設星號分別填入橙色、黃色(任意取2種有排列)，又最後右下角還可以填入5種顏色，共有$P_{2}^{6}×5=150$種情況。
綜合上述，2×2的正方形的可能填色情形共有36+150=186(種)

A:186種
:::
\
除了填色之外，不失一般性可以用在任何需要討論case的情況，接著搭配對稱性與等價性去計算其他case的數量。
接著舉例一種情況的不失一般性假設情形：
### Example 2.4.4
有標號分別為1、2的紅色卡片2張，標號分別為1、2的綠色卡片2張，標號分別為1、2的藍色卡片2張。現在將全部六張卡片放入下方2×3的長方形格子內，每格只能放置一張卡片。試問同一列、同一行的卡片顏色均不相同的情況數共有幾種？
![2×3表格](https://hackmd.io/_uploads/SyH_mQVc1e.png =25%x)
:::spoiler Hint:不失一般性假設列的填色情形
可以先分析第一列的填色情形，3種顏色共有3!種填法，而不失一般性的假設填色情況是`紅綠藍`。
若排列要滿足「每一行的顏色都不同」可以利用平移法，也就是整個排序平移一格變成`綠藍紅`，再次平移變成`藍紅綠`，可以發現第二列滿足的排列數共有2種，又第一列的6種情形都等價，故總排列數有：
3!×2=12(種)

A:12種
:::
\
有了以上的組合機率解，在解組合題目時會有意想不到的簡化效果！

# 解題流程
計算上除了組合機率解的簡化問題之外，也有其他的計算方法可以處理特殊的問題，若換個方式來思考題目，可以直接破解題目的演算法，也就完全了解題目在做什麼了。

## 壓界(值域由A到B)
結合對稱性與等價性，壓界很適合用在分布是對稱分布的情況上，若知道了情況的最大與最小值，或是極限情況，就可以猜出中間的分布，也可以更簡單的計算平均情況(期望值)。

### Example 2.4.5
模考對稱分布(書

## 進位制(將A代換成B)
進位制是要遇到特殊題型才會使用的技巧，要先知道題目的循環節，可以將數字變數變換找出題目的演算法，知道進位制後轉換的技巧。
用一題例題來舉例比較清楚。

### Example 2.4.6
學科能力