97年逢甲
R (->) , U( 向上的箭頭 ) ,從(0,0) -> (7,3)
在任一時間內 U的個數不能超過R的個數
也就是 任何時間 向上的步數不能超過向右的步數
老師解法是 全部方法 - 不合法的
而不合法的算法是 隨便取一種不合法的方式如
RUU RRURRRR
在" "發現不合法將上式改成
RUU UURUUUU --> 求這串的排列方法 就是不合法的走法
請問這觀念是什麼?
或是有其他方法解這題?
麻煩解答了 謝謝
Research Space for Linear Algebra & Discrete Mathematics
2 則留言:
其實這一題的觀念就是括號的應用，你可以把R想成(，U想成)；亦即一個(對應到一個)。
假設要走n個R, n個U, 相當於是要走到座標(n,n)的話, 那麼依照書上的轉換法, 每一條不合法的走法就相當於是最終會走n-1個R, n+1個U, 也就是終點都是(n-1,n+1); 反過來看, 從(0,0)要走到(n-1,n+1)的任一條path, 依照轉換法也會唯一對應到一組不合法的走法, 所以這兩件事會是等價的, 也就是說所有不合法的走法, 和從(0,0)要走到(n-1,n+1)的path, 有著一一對應的關係, 所以前者的path數就等同於後者的總數 (= c(2n,n+1))
張貼留言