作者ddtddt (得)
看板puzzle
标题[分享] 一唯随机漫步
时间Sat Aug 20 07:11:16 2016
从原点出发，在一直线上走20步，每一步可以往右或往左一单位。
已知最後一次经过原点是第12步时，请问共有几种走法可能?
________________________________________
原点
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.44.67.211
※ 文章网址: https://webptt.com/cn.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