Re: [組合]排列組合
※ 引述《yclinpa (薇楷的爹)》之銘言：
: ※ 引述《mixxim (米克斯)》之銘言：
: : 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=9 為例，作為一般性證明的提示：
: 考慮字串「大小小大大大小大」，此字串對應到 4-53267819.
: 觀察重點：(a) 第一位數字如何決定？
: (b) 「小」數排列的規則為何？「大」數排列的規則為何？
: 這些提示應該就夠了。
提供一個想法
每一位數字都 大於他左邊的每一個數字 或 小於他左邊的每一個數字
這樣保證左邊會有跟他差1的數字
因此最右邊是1或n，接著每位數字均可選"剩下的數中，最大的或最小的數字"
得2*2*2*....2*1=2^(n-1)種
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.49.226
推
03/16 00:41, , 1F
03/16 00:41, 1F
推
03/16 00:49, , 2F
03/16 00:49, 2F
→
03/16 00:50, , 3F
03/16 00:50, 3F
→
03/16 01:01, , 4F
03/16 01:01, 4F
討論串 (同標題文章)