Re: [理工] [離散]-移動路徑

[christianSK (AG)]

※ 引述《colinslik (~小礦礦~)》之銘言：
: A lattice path from (X0,Y0) to (Xn,Yn) in the xy plane is defined as a
: sequence of points (X0,Y0),(X1,Y1),...,(Xn,Yn) such that each Xi+1=Xi+1,
: and each Yi+1=Yi±1,i=1,2,...,n-1.How many lattices paths are there (0,1)
: to (10,3)? How many of them do not touch or cross the X axis?

(恕刪)

我覺得你誤解問題了

(1)  題目是說不要穿越x-axis 並不是說不要穿越 x=y 這條直線

(2)  走法是斜著走 也就是往右上或者是往左下走一個單位

這麼一來 由(0,1) --> (10,3) 不考慮限制下的走法

假設右上走了 u 次, 左下走了 v 次, 則

       u + v = 10             u = 6
                     ====>

       u - v =  2             v = 4       共有 C(10,4) =  210 種走法

接著考慮不合法的路徑

不合法的路徑則必然通過或是穿越 y = -1 這條直線

以 (0,1) 對此直線的對稱點 (0,-1) --> (10,3) 的走法數則是不合法的路徑數

一樣 假設右上走了 u 次, 左下走了 v 次, 則

       u + v = 10             u = 7
                     ====>

       u - v =  4             v = 3       共有 C(10,3) =  120 種走法

如此一來

C(10,4) - C(10,3) = 210 - 120 = 90  就是題目所要求的合法路徑數

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.32.74
※ 編輯: christianSK     來自: 140.114.32.74        (11/04 13:38)
推 colinslik:看懂了，感謝回答，不過還是想請問，如果是只能走X方向
→ colinslik:與Y方向，不能超過X=Y直線，起點(0,0) 終點(3,3) 要如何
→ colinslik:解呢?
→ christianSK:小黃書上說這個問題等同於左右刮號的問題
→ christianSK:所以也是calaten number
→ christianSK:不過我也還在想他是怎麼轉換成同樣問題的...= =
推 celiao:是說左括號是X方向，右括號是Y方向嗎...@@
→ christianSK:好像是耶 我好像可以理解了XD"