作者colinslik (~小礦礦~)
站內Grad-ProbAsk
標題[理工] [離散]-移動路徑
時間Thu Oct 28 13:03:45 2010
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?
我再黃子嘉離散第五版 5-99頁看到的，他是標90年中山資工的
我想問的是關於第2題，限制條件是do not touch or cross the X axis，但是他給
的解法是C(10,6)-C(10,3)=90
因為原題目答案的組合太龐大，所以我挑了個比較小的問題來驗證，就是由點(0,0)到
點(3,3)不能接觸或超過X=Y 直線的所有走法，用該題的方法，先列出第一次不合規定
的情況
XYY|XXY ←→ XYY|YYX 所以答案是C(6,3)-C(6,4)=20-15=5
X為沿X方向走一格，Y為沿Y方向走一格
但是我列出我找到的5種解法
1.XYXYXY
2.XYXXYY
3.XXYXYY
4.XXYYXY
5.XXXYYY
以上1,4兩種走法都在到達點(3,3)前接觸到X=Y 直線，看起來似乎與題目要求不合
，可以請各位前輩幫小弟解答一下，我的想法哪裡有錯，或者是這題本來就不是用
這種解法，如果是後者，希望可以提供一下解法，感謝各位了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.112.127
推 compulsory:下面你想的解 是可以接觸X=Y 但Y在這過程中<=X 10/28 13:16
推 compulsory:題目不可碰觸X軸 表示任何時間點右上方向不可<右下方向 10/28 13:20
→ compulsory:在你下面的小範例 任何時間點左(X)>上(Y) 10/28 13:22
→ compulsory: = 10/28 13:23
→ compulsory:題目 任何時間點右上方向>右下方向 10/28 13:24
→ compulsory: = 10/28 13:25
→ colinslik:不好意思 我不太懂你的意思 你是指原題目要求是 10/28 18:18
→ colinslik:任何時間點右上方向=>右下方向 這個意思嗎 其實我想問 10/28 18:19
→ colinslik:的主要就是這裡 10/28 18:19
→ daniel770624:我看不懂你們打的...我只知道題目是同時走X和Y 10/29 00:23