==問題==
設有身高不等的10人排成一列，若想讓任一較矮者不夾在兩較高者之間，則排列方法有多少種？
==解答==
假定身高分別為：0, 1, 2, 3, 4, 5, 6, 7, 8, 9。先寫出幾個可能的情況：
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
1, 3, 6, 9, 8, 7, 5, 4, 2, 0
2, 5, 7, 8, 9, 6, 4, 3, 1, 0
（排列組合最重要的就是要舉例！）
這些排列有什麼特徵？
仔細觀察可以發現，一旦最高的9確定後，接著比較矮的8就要選擇在9的左或右，然後是7選擇在左或右，依此類推。
=方法1=
依照上面的觀察，我們可以從9開始去「生成」所有可行的排法。例如：
(i) 9 → 89 → 897 → 8976 → 89765 → 489765 → 4897653 → 48976532 → 148976532 → 1489765320
(ii) 9 → 98 → 987 → 6987 → 69875 → 698754 → 3698754 → 36987542 → 136987542 → 0136987542
也就是說，一開始就有一個9，然後放8，而8可以選擇在9的左邊或是右邊；接著放7，而7可以選擇左邊或是右邊；...依此類推。從8開始到0，每個數字都可選擇左邊或右邊，於是算式為
$$\underbrace{2 \times 2 \times \cdots \times 2}_{9 {\text 個}} = 2^9 = 512.$$
=方法2=
另外一個方法是，首先想像有10個空位：
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜
接著填入9，有以下可能情況：
(i) 9⬜⬜⬜⬜⬜⬜⬜⬜⬜
(ii) ⬜9⬜⬜⬜⬜⬜⬜⬜⬜
...
(xi) ⬜⬜⬜⬜⬜⬜⬜⬜9⬜
(x) ⬜⬜⬜⬜⬜⬜⬜⬜⬜9
對於情形(i)，我們在9的左邊沒有任何空格可以填數字，而在右方有9個位置可以填數字，於是方法為$C^9_0 \times C^9_9$。
對於情形(ii)，我們在9的左邊有1個空格可以填數字，而在右方有8個位置可以填數字，於是方法為$C^9_1 \times C^8_8$。
...
對於情形(xi)，我們在9的左邊有8個空格可以填數字，而在右方有1個位置可以填數字，於是方法為$C^9_8 \times C^1_1$。
對於情形(x)，我們在9的左邊有9個空格可以填數字，而在右方有0個位置可以填數字，於是方法為$C^9_9 \times C^0_0$。
綜上所述，所求方法數為
$$\begin{align*} &C^9_0 \times C^9_9 + C^9_1 \times C^8_8 + \cdots + C^9_8 \times C^1_1 + C^9_9 \times C^0_0 \\ =&C^9_0 \times 1 + C^9_1 \times 1 + \cdots + C^9_8 \times 1 + C^9_9 \times 1 \\ =&C^9_0 + C^9_1 + \cdots + C^9_8 + C^9_9 \\ =& 2^9 \\ =&512 \end{align*}$$
（這裡引用了二項式定理：$(A + B)^n = C^n_0 A^n B^0 + C^n_1 A^{n-1}B^1 + C^n_2 A^{n-2} B^2 + \cdots + C^n_n A^0 B^n$，其中代入$A=1, B=1$，可得$C^n_0 + C^n_1 + C^n_2 + \cdots +C^n_n = 2^n$。）
==註記==
我個人喜歡用方法2，覺得比較自然，也比較好玩（可以跟組合級數扯上關係）。對於方法1那種慢慢生長的方式感到不太適應（雖然是自己想出來的）。
