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