※ 引述《IDontBite (大便兔子)》之銘言： : 從坐標原點(0,0)走到(n,n), : 走法只能往上或往右(每步1單位), : 自己的 y 座標必須恆小於等於 x 座標, : (也就是必須在 x = y 這條線下方) : 問走法有幾種? : 答案是 : 2n : C : n : _________ : (n+1) : 想了好久都不懂為什麼, 有請高手0.0 你隔壁那個戴眼鏡的~他這麼說: 以代號R表示向右一步Right 以代號U表示向上一步Up 那此題目等於RURURRUUR.....等共2N個字做排列~ any time: 當時已走的 R的數量 ≧ 當時已走的 U的數量 亦等同 ()()(())括號做排列， 因為無 )( 此種括號排列 any time:當時已走的 "("的數量 ≧ 當時已走的 ")"的數量 [方法一] 全部的走法有: 2n C n 不合法的走法: 2n 2n! C = _____________ n-1 (n+1)!(n-1)! 將一個R換成U n+1 是U 向上一步 n-1 是R 向右一步 則這路徑的其中必有某處【當時已走的 U數量 > 當時已走的 R數量 】 =>使得 路徑高過 [x = y 這條線] (就是不管怎麼走~必有違規的走法=就是超過x = y) (全部的走法)-(不合法的走法)= 合法的走法 即可 --------------------- [方法二] 例如N=5 全部走法: 10 C 5 例R U R R U U R U R U 不合法的走法: 將第一個違法的字~與剩下來的字隔開 例 "U" | R R R U U R U R U | | | | | | | | | | <=反向處理 U U U R R U R U R --------------------------- 變成 U U U U R R U R U R 也就是 10! 10 ____ = c 4!6! 4 (全部的走法)-(不合法的走法)= 合法的走法 ========================================= 2n C n _________ (n+1) 其實這個公式叫 nth Catalan number 本身是求 n個點的有序二元樹 共有幾種 要用遞迴證明~非常難寫~ 但是功用可套到各種等價題目~~ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.137.203.215 ※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:28) ※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:28) ※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:29) ※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:31)