作者ddtddt (得)
看板puzzle
標題[分享] 一唯隨機漫步
時間Sat Aug 20 07:11:16 2016
從原點出發，在一直線上走20步，每一步可以往右或往左一單位。
已知最後一次經過原點是第12步時，請問共有幾種走法可能?
________________________________________
原點
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.67.211
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1471648279.A.B9D.html
1F：推 Django: 924 * (1+6+14+14) * 2 = 64680 ? 08/20 15:18
答案是正確，不過希望可以寫成通式~或是多分享一下想法~
2F：推 arthurduh1: C(12,6) * 2 * C(6,3) 08/20 15:41
3F：推 arthurduh1: 阿 上面沒考慮最後一步，要看最後一步可以回到原點嗎 08/20 15:50
最後一步回到原點的話，就算最後一次經過原點是在第20步喔 :)
謝謝兩位加入討論
4F：→ arthurduh1: 可以的話乘兩倍，不行的話是 08/20 15:52
請問!! 在一直線上走2N步，最後一次經過原點是第2K步，共有幾種走法?
5F：→ arthurduh1: 同一樓 C(12,6) * 2 * C(6,3) * (2-1/4) 08/20 15:54
6F：→ arthurduh1: C(2m,m) * 2 * C(2n-2m-2,n-m-1) * (2-1/(n-m)) 08/20 15:55
7F：→ arthurduh1: m=K, n=N 08/20 15:57
計算了一下答案正確! 還可以化簡成一個比較乾淨漂亮的形式~~
可以請a大分享一下你的想法嗎?
※ 編輯: ddtddt (114.44.74.174), 08/20/2016 16:18:58
8F：→ arthurduh1: 2*C(2n-2m-2,n-m-1) 是由原點出發、中途不回原點的 08/20 16:28
9F：→ arthurduh1: 方法數的一半(看起頭往哪方向走)(最後可回原點) 08/20 16:30
10F：→ arthurduh1: C(2n-2m-2,n-m-1)/(n-m) 則是 Catalan number 08/20 16:30
11F：→ arthurduh1: 是中途不回原點、最後回到原點的方法數 08/20 16:31
12F：→ arthurduh1: 的一半 08/20 16:32
13F：→ arthurduh1: 可以化簡的話，可能也有解釋方法，你可以試試 08/20 16:32
14F：推 arthurduh1: 化簡後: C(2m,m) * 2 * C(2n-2m-1,n-m) 08/20 16:53
15F：→ arthurduh1: 解釋: C(2n-2m-1,n-m) 是從原點走2n-2m-1步、不超過 08/20 16:55
16F：→ arthurduh1: 原點的方法數 (可以碰到) 08/20 16:56
17F：→ arthurduh1: 實際上在這個問題是從 正負1出發、不碰到原點的方法數 08/20 16:57
18F：推 walkwall: 解法讚 08/20 18:06
19F：推 Django: 就是 從正負1開始 走(2n-2k-1)步 一路領先的方法數囉? 08/20 18:18
20F：→ arthurduh1: 對，用一路領先的語言的話，起始票數是 (1,0) 08/20 19:04