[理工] 棋盤走訪 可走斜線

看板Grad-ProbAsk作者 (JacobSyu)時間11年前 (2015/01/11 22:52), 11年前編輯推噓3(3推 0噓 11→)
留言14則, 5人參與, 最新討論串1/1
(0,0)->(m,n) 可以走三種走訪方式, 右、上、斜角 共有幾種方法? 延伸(不可往回走): (1)若(0,0)->(N,N) 不可超越對角線(但可壓線), 可走訪方式如上 (2)若(0,0)->(N,N) 第一次走訪就經過對角線方法數, 可走訪方式如上 各有幾種方法? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.244.143.12 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1420987927.A.4E4.html
→
01/11 23:32, , 1F
Sigma k=0~n,((m+n)-k)! / k!(m-k)!(n-k)!
01/11 23:32, 1F
→
01/11 23:34, , 2F
假設m個右，n個上，k個斜上
01/11 23:34, 2F
→
01/11 23:38, , 3F
不過sigma的上限應該是min(m,n)，歡迎討論
01/11 23:38, 3F
推
01/11 23:38, , 4F
不失一般性假設m>=n
01/11 23:38, 4F
推
01/11 23:52, , 5F
還有是種~~幾種~~不是總~~
01/11 23:52, 5F
→
01/12 00:18, , 6F
不好意思...種 打錯...
01/12 00:18, 6F
※ 編輯: JacobSyu (36.232.239.210), 01/12/2015 09:02:16 ※ 編輯: JacobSyu (36.232.239.210), 01/12/2015 09:12:04 ※ 編輯: JacobSyu (36.232.239.210), 01/12/2015 09:13:30
→
01/12 10:01, , 7F
到(m,n)還是(n,n)?
01/12 10:01, 7F
→
01/12 10:22, , 8F
若是對角線限制,則為(n,n);
01/12 10:22, 8F
→
01/12 10:23, , 9F
(1)也就是不可超越x=y的方法; 但可走斜線
01/12 10:23, 9F
→
01/12 11:36, , 10F
對角線是只能走1*1往右上的對角線嗎？
01/12 11:36, 10F
→
01/12 11:41, , 11F
嗚 對角線限制還可以走斜上就沒什麼想法了QQ
01/12 11:41, 11F
推
01/12 16:17, , 12F
延伸一。 應該就是往右走次數大於等於往上走次數 或是
01/12 16:17, 12F
→
01/12 16:17, , 13F
反過來 。 所以用全勝定理解得Sigma k=0~n,(2/(n-k+1)
01/12 16:17, 13F
→
01/12 16:17, , 14F
)*((2n)-k)! / k!(n-k)!(n-k)!
01/12 16:17, 14F
‣ 更多 JacobSyu 的文章
文章代碼(AID): #1KieuNJa (Grad-ProbAsk)