Re: [組合]排列組合
※ 引述《mvpnashmvp (林桑)》之銘言：
: How many arrangements of the integer 1,2,...,n are there such that each
: integer(except the first integer) differs by 1 from some integer to
: the left of it in the arrangement?
n=1: 1
n=2: 12 21
n=3: 123 213 231 321
n=4: 1234 2134 2314 2341 3214 3241 3421 4321
n=5: 12345 ... 等16個
經過觀察看起來真的是 2^(n-1)，試著歸納看看
n=1 顯然成立
假設 n<k 皆成立，現在考慮 n=k 的情況
_ _ _ _ _ _ _ _ k 最後一個擺 k，由歸納恰有 2^(k-2) 種方法
_ _ _ _ _ _ _ k 1 倒數第二個擺 k，那麼由條件最後一個只能擺 1 (為什麼?)
由歸納恰有 2^(k-3) 種方法
_ _ _ _ _ _ k 2 1 倒數第三個擺 k，那麼最後兩個只能依序擺 2 1
由歸納恰有 2^(k-4) 種方法
..........
_ _ k (k-3) (k-4) ... 1 第三個擺 k，有 2^1 種方法
_ k (k-2) (k-3) ... 1 第二個擺 k，有 2^0 種方法
最後在第一個擺 k，只有一種方法
k-2
所以總方法數為 1 + Σ 2^i = 2^(k-1)
i=0
故對於 n=k 亦成立
由數學歸納法證得方法數確為 2^(n-1)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.251.61
※ 編輯: mixxim 來自: 140.112.251.61 (03/15 03:30)
討論串 (同標題文章)