Discrete mathematics - Catalan number
給定兩個生成函數:
- A(x)=∑∞n=0anxn
- B(x)=∑∞n=0bnxn
則:
- A(x)±B(x)=∑∞n=0(an+bn)xn
- A(x)×B(x)=(a0+a1x+a2x2+…)×(b0+b1x+b2x2+…)⇒(a0b0)+(a0b1+a1b0)x+(a2b0+a1b1+a0b2)x2+…
定義
- cn=an⊗bn=a0bn+a1bn−1+…+anb0
- an、bn 為兩個遞迴函數
- 稱 cn 為 an、bn 的「Convalution」
- cn=an⊗bn⇒C(x)=A(x)×B(x)
- cn=an⊗an⇒C(x)=A(x)×A(x)=A(x)2
「生成函數」推導
令 Catalan number 等於 {an=a0an−1+a1an−2+…+an−1a0,n≥1a0=1,a1=a0a0=1 以「生成函數」求此遞迴函數的顯式
令 A(x)=∑∞n=0anxn
因為由上式可以知道此遞迴從 n ≧ 1開始有意義
∑∞n=0anxn−a0=∑∞n=1(a0an−1+a1an−2+…+an−1a0)xn
- ∑∞n=1(a0an−1+a1an−2+…+an−1a0)xn⇒x⋅∑∞n=1(a0an−1+a1an−2+…+an−1a0)xn−1=x⋅A(x)2
A(x)−a0=x⋅A(x)2⇒xA(x)2−A(x)+1=0
A(x)=1±√1−4x2x
- (1−4x)12=∑∞r=0(12r)(−4x)r
- ∑∞r=0(12r)(−4x)r=∑∞n=012(12−1)…(12−r+1)r!(−1)r4rxr
- ⇒∑∞r=012(−12)(−32)…(−2r−32)r!(−1)r4rxr
- ⇒∑∞r=0(−1)r−1(12)r1(1)(3)…(2r−3)r!(−1)r4rxr
- ⇒−∑∞r=0(1)(3)…(2r−3)r!2rxr
- ⇒∑∞r=0(1)(2)(3)…(2r−3)(2r−2)(2r−1)(2r)r!⋅2r⋅r!⋅(2r−1)2rxr
- ⇒−∑∞r=0(2r)!r!⋅r!(2r−1)xr
- ⇒−∑∞r=012r−1(2rr)xr
- (1−4x)12=∑∞r=0(12r)(−4x)r
因為 A(x) 會有兩個解,但是因為欲求之解不可能有負數情形,所以取其正解
- A(x)=1−√1−4x2x=1+∑∞r=012r−1(2rr)xr2x
- ⇒12∑∞r=112r−1(2rr)xr−1,取 xn 的係數
- 則 r = n+1,⇒12⋅12(n+1)−1(2(n+1)(n+1))xn
- ⇒an=12(2n+1)⋅(2n+2)×(2n+1)(n+1)×(n+1)⋅(2nn)=1n+1(2nn)
- Catalan number 為 1n+1(2nn)
Example
求取 n 個節點的「Binary ordered tree」個數?

,k ≧ 0
⇒{an=a0an−1+a1an−2+…+an−1a0,n≥1a0=1⇒an=cn=1n+1(2nn)
變形
- {an=a0an−1+a1an−2+…+an−1a0,n≥1a0=1
- an=cn=1n+1(2nn)
- {an=a1an−1+a2an−2+…+an−1a1,n≥1a1=1
- an=cn−1=1n(2(n−1)n−1)
- {an=a2an−1+a3an−2+…+an−1a2,n≥1a2=1
- an=cn−2=1n+1(2(n−2)n−2)
Example
n 個變數 x1,x2,…,xn 之合法的括號數有幾個?
![]()
,k ≧ 1
{an=a1an−1+a2an−2+…+an−1a1,n≥1a1=1⇒cn−1=1n(2(n−1)n−1)
「組合證明」推導
前導
令 Catalan number 等於 {an=a0an−1+a1an−2+…+an−1a0,n≥1a0=1,a1=a0a0=1 則我們可以將此遞迴視為一個「合法路徑問題」
- 在一個二維空間下,從原點 (0, 0) 只能走下面兩種步伐至 (m, n)
- 步伐 R:(x, y) → (x+1, y)
- 步伐 U:(x, y) → (x, y+1)
- 並且在路徑中,不能發生 U 大於 R 的情形
- 違法:(0,0)→R→R→U→U→U→R→...→(m,n)
- 首先我們先將問題簡化成「Catalan number」可以解釋的問題,再來推廣
- 在一個二維空間下,從原點 (0, 0) 只能走下面兩種步伐至 (n, n)
- 步伐 R:(x, y) → (x+1, y)
- 步伐 U:(x, y) → (x, y+1)
- 並且在路徑中,不能發生 U 大於 R 的情形
- 在一個二維空間下,從原點 (0, 0) 只能走下面兩種步伐至 (n, n)
討論
- 若問題再進一步簡化成「自點(0, 0) 只能以規定的兩種步伐至 (0, 0)」
- 令該方法數為 a0,並且其方法數視為 1
- 而當問題為「自點(0, 0) 只能以規定的兩種步伐至 (1, 1)」時
- 只有唯一種方法,就是 (0,0)→R→U→(1,1)
- 而我們更可以進一步將此看成
- a1 = 「自(0,0)至(0,0)的方法數」×(唯一的走法:...→R→U→...)×「自(1,1)至(1,1)的方法數」
- a1=a0×1×a0=a0a0
所以,在一個二維空間下,從原點 (0, 0) 只能以規定兩種步伐至 (n, n)的方法數為
- an=a0an−1+a1an−2+…+an−1a0,為以下方法數組成
- (「自(0,0)至(0,0)的方法數」×(唯一的走法:...→R→U→...)×「自(1,1)至(n,n)的方法數」) +
- (「自(0,0)至(1,1)的方法數」×(唯一的走法:...→R→U→...)×「自(2,2)至(n,n)的方法數」) +
- ....
- (「自(0,0)至(n-1,n-1)的方法數」×(唯一的走法:...→R→U→...)×「自(n,n)至(n,n)的方法數」)
由上方討論可以得知簡化的「合法路徑問題」與 n 個節點的「Binary ordered tree」個數問題等價
組合證明
一樣是上述的簡化的「合法路徑問題」,由下圖來討論

自 (0, 0) 至 (16, 16) 且不得超過中間雙線的部分(可觸及)
合法示意圖:

非法示意圖:

每個違法的路徑,必定會和下方紅色雙斜線接觸
![]()
將「開始違法的座標」之後的路徑對紅色雙斜線做對稱化,則最後到達的座標必定在 (15,17),而這種轉換有幾個特性:
- 1-1 對應
- 可逆
- 若再一次對稱回來,必定會對應到一個違法的路徑自(0,0)至(16,16)
所以自(0,0)至(15,17)的每種路徑,皆會對應到一個違法路徑
- 合法路徑方法數
- (3216)−(3215)=116+1(2⋅1616) 為「Catalan number」
- 所以從(0, 0)至(n, n)的「合法路徑為」
- (2nn)−(2nn−1)
Example
有一場選舉,兩個候選人 A、B,假設知道 A 的票數一定比 B 多,假設 A 的總得票數為 p ,B 的總得票數為 q,請問有幾種開票的方法可保證每個當下 A 的得票數會大於 B 當下的得票數?
分析
有別於上面的題目,此處 A 每個當下的得票數絕對會比 B 每個當下的得票數還多
- 不合法的開票方法:A→A→B→B→...

假設 A 得到 15 票,B 得到 11 票,則上圖中綠色為合法的開票方法,紅色虛線為不合法的開票方法,但是這樣討論之下,綠色的開票方法在尚未開票時其實也觸碰了紅色雙斜線,然而為何還是正確的開票方法,因為我們在尚未開票時不討論誰贏的比較多,所以我們可以將起點平移到 (1, 0) 處,代表第一章開出來的票一定是 A 得到,且亦不牴觸我們方才的假設

則每個非法路徑會唯一對應到「自 (1,0) 至 (11,15) 的開票方法」

- 合法的開票方法為
- ((15−1)+1115−1)−((11−1)+1511−1)=(2514)−(2510)=1188640
- 原本的問題之合法開票數為
- ((p−1)+qp−1)−((q−1)+pq−1)