Re: [理工] [離散]-移動路徑
※ 引述《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)
推
11/04 21:35, , 1F
11/04 21:35, 1F
→
11/04 21:36, , 2F
11/04 21:36, 2F
→
11/04 21:36, , 3F
11/04 21:36, 3F
→
11/04 22:21, , 4F
11/04 22:21, 4F
→
11/04 22:21, , 5F
11/04 22:21, 5F
→
11/04 22:21, , 6F
11/04 22:21, 6F
推
11/05 01:56, , 7F
11/05 01:56, 7F
→
11/05 22:41, , 8F
11/05 22:41, 8F
討論串 (同標題文章)