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

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