[理工] [離散]-移動路徑
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
推
10/28 13:16, , 1F
10/28 13:16, 1F
推
10/28 13:20, , 2F
10/28 13:20, 2F
→
10/28 13:22, , 3F
10/28 13:22, 3F
→
10/28 13:23, , 4F
10/28 13:23, 4F
→
10/28 13:24, , 5F
10/28 13:24, 5F
→
10/28 13:25, , 6F
10/28 13:25, 6F
→
10/28 18:18, , 7F
10/28 18:18, 7F
→
10/28 18:19, , 8F
10/28 18:19, 8F
→
10/28 18:19, , 9F
10/28 18:19, 9F
→
10/29 00:23, , 10F
10/29 00:23, 10F
→
08/09 10:48, , 11F
08/09 10:48, 11F
→
09/11 14:01, , 12F
09/11 14:01, 12F
→
12/15 00:26,
5年前
, 13F
12/15 00:26, 13F
討論串 (同標題文章)