推 pcpo8992 :懂了!非常感謝 12/31 00:39
推 eggsu : 很棒的解釋，在「數學悠哉遊」有看過以上的說明 03/03 22:38
→ eggsu : 有興趣看書面資料的可以參考 03/03 22:38
※ 引述《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)