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

[JacobSyu (JacobSyu)]

(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
→ shanbb: Sigma k=0~n,((m+n)-k)! / k!(m-k)!(n-k)!
→ shanbb: 假設m個右，n個上，k個斜上
→ shanbb: 不過sigma的上限應該是min(m,n)，歡迎討論
推 hutdris: 不失一般性假設m>=n
推 shanbb: 還有是種~~幾種~~不是總~~
→ JacobSyu: 不好意思...種  打錯...
※ 編輯: 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
→ shanbb: 到(m,n)還是(n,n)?
→ JacobSyu: 若是對角線限制,則為(n,n);
→ JacobSyu: (1)也就是不可超越x=y的方法; 但可走斜線
→ a88241050: 對角線是只能走1*1往右上的對角線嗎？
→ shanbb: 嗚 對角線限制還可以走斜上就沒什麼想法了QQ
推 killerw74: 延伸一。 應該就是往右走次數大於等於往上走次數 或是
→ killerw74: 反過來 。  所以用全勝定理解得Sigma k=0~n,(2/(n-k+1)
→ killerw74: )*((2n)-k)! / k!(n-k)!(n-k)!