[離散] 路徑選擇數問題?!

[ttfang29 (踢踢煩)]

各位大大 不好意思想請問一個有關 路徑選擇數的問題（不允許回頭）

簡易版是高中就有學過的：

   ┌┬┬┬┬┐
   ├┼┼┼┼┤
   ├┼┼┼┼┤
   └┴┴┴┴┘
比如說像這種二維方塊　要從(0,0)走到(5,3)

就從左下角一路標示上去到右上角  e.g.: (2,1) = (1,1) + (2,0) = (1+1)+1 = 3


想請問的是　如果是3維(x,y,z),4維(x,y,z,w)的話該怎麼做呢？

原題是問4維(0,0,0,0)走到(4,3,5,4)的方法數共幾種? (不允許回頭)

請問這種問題是否有數學式子解？　　　

謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.181
※ 編輯: ttfang29        來自: 140.112.4.181        (06/05 13:00)
→ genghis     :會不會是(x,y,z)=(x-1,y,z)+(x,y-1,z)+(x,y,z-1)
→ genghis     :(x,y,z,w)=(x-1,y,z,w)+(x,y-1,z,w)+...
→ genghis     :這種關係...
推 went27      :google "dynamic programming"
→ ttfang29    :感謝樓上兩位~ 所以還是得用類似遞迴的方式求解囉?
→ ttfang29    :有辦法用手算算得出來嗎?
→ TheMatt     :(x,y,z,w)=x!*y!*z!*w!這樣行嗎?
→ TheMatt     :搞錯，是(x+y+z+w)!/(x!*y!*z!*w!)
                                          正解
推 went27      :二維畫方格的情形就是遞迴 手算的話要從小算到大
→ ttfang29    :感謝TheMatt大大! 我想懂了~也謝謝went27跟genghis
所以情況是像這樣:

以2維的情況來想  +x = →  ;  +y = ↑

如果要走到(4,3) ，就需要 4個→ , 3個↑  所以排列數是

   4+3 個箭頭  ，  其中 4個重覆(相同)的→, 3個↑  =  (4+3)!/(4!3!)

推廣的n維的情況就如TheMatt所述

故所求= (4+3+5+4)!/(4!3!5!4!) = 50450400
※ 編輯: ttfang29        來自: 140.112.4.181        (06/05 14:03)