[理工] 離散數學 全勝理論問題

[terry8575 (豪哥)]

https://i.imgur.com/1kTIprJ.jpg
剛剛複習到這一題
要從（0，0）走到（7，3），R不能少於U的走法有幾種？

印象中老師說當R的個數少於U時（如RUU），後面不管怎麼樣都一定是不成立的
所以前面三個是RUU（不合法）
所以之後的R跟U就可以互換過來，因為互換過來也一定是不合法
可是互換之前的RUU明明U的個數就已經超過R了
不是本來就不合法了嗎，為什麼後面還要互換過來呀？
我卡在這個觀念轉不太過來.....


還有下面的Note 部分
為什麼最後括號取法總數-不合法取法數算出來的合法取法數的答案會是(1/n+1)*C（2n取
n）呢？

求大神開導


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.19.106 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1586703318.A.8AB.html
→ oepop: 重點是能夠和不合法的一一對應
→ oepop: 你把那些轉回去試試應該就能理解了
左右兩邊都是10個，所以都可以一一去做對應這樣吧？
大大您說的轉回去是什麼意思？
抱歉我還是不太懂
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 10:33:32
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 10:34:46
→ Ricestone: 左邊到右邊是想把不合法的對到"2,8"狀況中的一種
→ Ricestone: 會不懂的原因應該是這筆記沒有寫清楚為什麼右邊的元素
→ Ricestone: 的確全部都會被左邊對到
→ Ricestone: 不過其實就反過來想，"2,8"的情況隨便寫出來，可以用
→ Ricestone: 相反的方式映回左邊的狀況
→ Ricestone: 至於你下面的問題，那就只是代數而已
→ Ricestone: 因為(2n,n-1) = (n/(n+1))*(2n,n)
大大抱歉  想再請教您關於這個代數是怎麼寫出來的呀？
我算不太出來....
→ Ricestone: 另外補充一下，右邊的狀況沒什麼好合不合法的
→ Ricestone: 那個"必不合法"其實不重要
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 12:11:53
→ Ricestone: (2n,n) = 2n*...*(n+1)/{n*...*1}
→ Ricestone: (2n,n-1) = 2n*...*(n+2)/{(n-1)*...*1}
原來如此  Note這邊的計算我看懂了！！！！
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 12:56:30
→ terry8575: 我看課本是這樣解釋的
→ terry8575: https://i.imgur.com/DOIViJe.jpg
→ terry8575: https://i.imgur.com/pvUf3AZ.jpg
→ terry8575: 滿神奇的是所有不合法路徑只要經過一一對應的互相轉換
→ terry8575: 後必定都會出現4R6U。只是最後倒數第五行說4R6U也必定
→ terry8575: 能轉換為其他不合法路徑又是什麼意思？ 是指說它也能
→ terry8575: 轉換會原來的7R3U嗎？
→ terry8575: 抱歉最後一句改為5R5U...   上面拍得課本例題跟一開始
→ terry8575: 的題目滿類似的耶
→ Ricestone: 對  例如RURUUUURUR想要轉回不合法，那就從左邊開始找
→ Ricestone: U開始比R多的地方，後面再全轉一次，就變原本的不合法
這樣我有比較懂了！  謝謝大神的解析
回原題：
也就是說我先找到U比R多的地方，後面部分全做互換後一定可得到2R8U 的不合法路徑形
式。
由於一一對應（1to1）的關係，所以我後面2R8U做排組後所得出的組合個數其實就等於互
換前的不合法路徑個數了！
我的理解是這樣...
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 16:19:53
→ Ricestone: 「一一對應」這個詞是 1-1 and onto，要小心
謝謝提醒
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 17:02:53