作者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/cn.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