※ 引述《pcpo8992 (E~T shot)》之铭言： : 问题是用递回如何解caralan number Cn=1/n+1*C(2n n) : 有爬过文但不太了解，也去维基百科看也不太了解 : 可以请大大说帮忙解说吗 : 小弟对生成函数和递回之间不太了解 : 谢谢 我刚刚想说也去看一下维基 看了发现他是写成另一个卡特兰数的形式 2n 2n 就是变成C - C 来证明的,过程也不是用递回,所以就先不管它了XD n n+1 其实我们要解的问题就是下面这个递回式 a = 1 ∕ 0 ﹨ n-1 a = Σ a a , ∀n>0 n i=0 i (n-1)-i 这个递回式我也不知道是从哪个题目先想出来的 不过大致上有以下这几种比较常见的例子可以看: n个节点的相异二元树个数.矩阵相乘中n个乘号的乘法方法数, stack输入1,2,...,n之後可能产生出来的输出总数等等... (其他还有一些例子维基上面有写,可以再去参考看看) 我主要就说这个递回式我的解法: 首先我们知道 a = a a + a a + ... + a a n 0 n-1 1 n-2 n-1 0 等号左右都加上Σx的n次方(也就是普通的生成函数解法)可得下式: ∞ n ∞ n Σ a x = Σ (a a + a a + ... + a a )x ...(1) n=1 n n=1 0 n-1 1 n-2 n-1 0 ∞ n 令F(x) = Σ a x n=0 n 则左式= F(x) - a 右式= x(F(x))^2 0 右式怕你看不懂 我稍微解释一下 其实你把F(x)*F(x)暴力法乘开可以发现下面这个式子 0 1 2 a a x + (a a + a a )x + (a a + a a +a a )x + ... 0 0 0 1 1 0 0 2 1 1 2 0 跟(1)式中等号右方的数就只差一倍的x , 所以再补乘上这一倍x就可以了 又因为a = 1 这个递回条件, 0 因此我们有新的等式出现: F(x) - 1 = x(F(x))^2 把它看成F(x)的二次式 也就是 x F(x)^2 - F(x) +1 = 0 1±√(1-4x) => F(x) = ------------- 2x => 2x*F(x) = 1±√(1-4x) ∞ 1/2 k = 1±Σ C *(-4x) ...(2) (二项式定理) k=0 k 1/2 (1/2)(1/2 - 1)(...)(1/2 - k + 1) 其中C 又等於---------------------------------- k k! 1 1*(-1)(-3)(...)(3-2k) = ----- * ----------------------- 2^k k! k-1 1*3*5*...*(2k-3) = 2^(-k) * (-1) * ------------------ k! k-1 1*3*5*...*(2k-3) 2*4*6*...*(2k-2) = 2^(-k) * (-1) * ------------------ * ------------------ k! 2*4*6*...*(2k-2) k-1 (2k-2)! = 2^(-k) * (-1) * ------------------- 2^(k-1) *k!(k-1)! k-1 2k-2 = 2^(1-2k)*(-1) *(1/k)*C k-1 再代回刚刚的(2)式可得 ∞ k-1 2k-2 2xF(x) = 1±Σ 2^(1-2k)*(-1) *(1/k)*C *(-4x)^k k=0 k-1 ∞ 2k-2 = 1±(-2)Σ (1/k)*C x^k k=0 k-1 ∞ n 把F(x) = Σ a x 代回 n=0 n ∞ n+1 ∞ 2k-2 => Σ a x = (1/2) ±(-1)Σ (1/k)*C x^k n=0 n k=0 k-1 接下来就剩比较系数了 n+1 我们要求的是a ,也就是要知道右式中x 项系数, n 1 2n 将右式中k=n+1代入就会得到 a = ------- * C n (n+1) n 也就是我们的卡特兰数了 虽然过程有点复杂 可是可以复习一下二项式定理跟生成函数也是不错XD --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.139.83 ※ 编辑: jameschou 来自: 140.113.139.83 (12/30 14:46)