作者terry8575 (豪哥)
看板Grad-ProbAsk
標題[理工] 離散數學 全勝理論問題
時間Sun Apr 12 22:55:16 2020
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1586703318.A.8AB.html
1F：→ oepop: 重點是能夠和不合法的一一對應04/13 07:42
2F：→ oepop: 你把那些轉回去試試應該就能理解了04/13 07:42
左右兩邊都是10個，所以都可以一一去做對應這樣吧？
大大您說的轉回去是什麼意思？
抱歉我還是不太懂
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 10:33:32
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 10:34:46
3F：→ Ricestone: 左邊到右邊是想把不合法的對到"2,8"狀況中的一種04/13 10:57
4F：→ Ricestone: 會不懂的原因應該是這筆記沒有寫清楚為什麼右邊的元素04/13 10:58
5F：→ Ricestone: 的確全部都會被左邊對到04/13 10:58
6F：→ Ricestone: 不過其實就反過來想，"2,8"的情況隨便寫出來，可以用04/13 11:00
7F：→ Ricestone: 相反的方式映回左邊的狀況04/13 11:01
8F：→ Ricestone: 至於你下面的問題，那就只是代數而已04/13 11:02
9F：→ Ricestone: 因為(2n,n-1) = (n/(n+1))*(2n,n) 04/13 11:05
大大抱歉 想再請教您關於這個代數是怎麼寫出來的呀？
我算不太出來....
10F：→ Ricestone: 另外補充一下，右邊的狀況沒什麼好合不合法的04/13 11:11
11F：→ Ricestone: 那個"必不合法"其實不重要04/13 11:12
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 12:11:53
12F：→ Ricestone: (2n,n) = 2n*...*(n+1)/{n*...*1}04/13 12:17
13F：→ Ricestone: (2n,n-1) = 2n*...*(n+2)/{(n-1)*...*1}04/13 12:18
原來如此 Note這邊的計算我看懂了！！！！
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 12:56:30
14F：→ terry8575: 我看課本是這樣解釋的 04/13 12:59
17F：→ terry8575: 滿神奇的是所有不合法路徑只要經過一一對應的互相轉換04/13 13:08
18F：→ terry8575: 後必定都會出現4R6U。只是最後倒數第五行說4R6U也必定04/13 13:08
19F：→ terry8575: 能轉換為其他不合法路徑又是什麼意思？ 是指說它也能04/13 13:08
20F：→ terry8575: 轉換會原來的7R3U嗎？ 04/13 13:08
21F：→ terry8575: 抱歉最後一句改為5R5U... 上面拍得課本例題跟一開始 04/13 13:11
22F：→ terry8575: 的題目滿類似的耶 04/13 13:11
23F：→ Ricestone: 對 例如RURUUUURUR想要轉回不合法，那就從左邊開始找 04/13 13:15
24F：→ Ricestone: U開始比R多的地方，後面再全轉一次，就變原本的不合法 04/13 13:18
這樣我有比較懂了！ 謝謝大神的解析
回原題：
也就是說我先找到U比R多的地方，後面部分全做互換後一定可得到2R8U 的不合法路徑形
式。
由於一一對應（1to1）的關係，所以我後面2R8U做排組後所得出的組合個數其實就等於互
換前的不合法路徑個數了！
我的理解是這樣...
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 16:19:53
25F：→ Ricestone: 「一一對應」這個詞是 1-1 and onto，要小心 04/13 16:24
謝謝提醒
※ 編輯: terry8575 (101.10.19.106 臺灣), 04/13/2020 17:02:53