一道身高排列問題

==問題==

設有身高不等的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那種慢慢生長的方式感到不太適應（雖然是自己想出來的）。