Processing math: 100%

2022年5月12日 星期四

一道身高排列問題

==問題==

設有身高不等的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,每個數字都可選擇左邊或右邊,於是算式為

2×2××29=29=512.

=方法2=

        另外一個方法是,首先想像有10個空位:

⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜

接著填入9,有以下可能情況:

(i) 9⬜⬜⬜⬜⬜⬜⬜⬜⬜

(ii) ⬜9⬜⬜⬜⬜⬜⬜⬜⬜

...

(xi) ⬜⬜⬜⬜⬜⬜⬜⬜9⬜

(x) ⬜⬜⬜⬜⬜⬜⬜⬜⬜9

        對於情形(i),我們在9的左邊沒有任何空格可以填數字,而在右方有9個位置可以填數字,於是方法為C90×C99

        對於情形(ii),我們在9的左邊有1個空格可以填數字,而在右方有8個位置可以填數字,於是方法為C91×C88

...

        對於情形(xi),我們在9的左邊有8個空格可以填數字,而在右方有1個位置可以填數字,於是方法為C98×C11

        對於情形(x),我們在9的左邊有9個空格可以填數字,而在右方有0個位置可以填數字,於是方法為C99×C00

        綜上所述,所求方法數為
C90×C99+C91×C88++C98×C11+C99×C00=C90×1+C91×1++C98×1+C99×1=C90+C91++C98+C99=29=512

(這裡引用了二項式定理:(A+B)n=Cn0AnB0+Cn1An1B1+Cn2An2B2++CnnA0Bn,其中代入A=1,B=1,可得Cn0+Cn1+Cn2++Cnn=2n。)

==註記==

        我個人喜歡用方法2,覺得比較自然,也比較好玩(可以跟組合級數扯上關係)。對於方法1那種慢慢生長的方式感到不太適應(雖然是自己想出來的)。

沒有留言:

張貼留言