※ 引述《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)