PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[問題] 一唯隨機漫步

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