Processing math: 100%

Discrete mathematics - Catalan number

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=anbn=a0bn+a1bn1++anb0
    • anbn 為兩個遞迴函數
  • cnanbn 的「Convalution」
    • cn=anbnC(x)=A(x)×B(x)
    • cn=ananC(x)=A(x)×A(x)=A(x)2

「生成函數」推導

令 Catalan number 等於 {an=a0an1+a1an2++an1a0,n1a0=1,a1=a0a0=1 以「生成函數」求此遞迴函數的顯式

  1. A(x)=n=0anxn

    • 因為由上式可以知道此遞迴從 n ≧ 1開始有意義

    • n=0anxna0=n=1(a0an1+a1an2++an1a0)xn

      • n=1(a0an1+a1an2++an1a0)xnxn=1(a0an1+a1an2++an1a0)xn1=xA(x)2
    • A(x)a0=xA(x)2xA(x)2A(x)+1=0

  2. A(x)=1±14x2x

    • (14x)12=r=0(12r)(4x)r
      • r=0(12r)(4x)r=n=012(121)(12r+1)r!(1)r4rxr
      • r=012(12)(32)(2r32)r!(1)r4rxr
      • r=0(1)r1(12)r1(1)(3)(2r3)r!(1)r4rxr
      • r=0(1)(3)(2r3)r!2rxr
      • r=0(1)(2)(3)(2r3)(2r2)(2r1)(2r)r!2rr!(2r1)2rxr
      • r=0(2r)!r!r!(2r1)xr
      • r=012r1(2rr)xr
  3. 因為 A(x) 會有兩個解,但是因為欲求之解不可能有負數情形,所以取其正解

  • A(x)=114x2x=1+r=012r1(2rr)xr2x
    • 12r=112r1(2rr)xr1,取 xn 的係數
    • 則 r = n+1,1212(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)
  1. Catalan number 為 1n+1(2nn)

Example

求取 n 個節點的「Binary ordered tree」個數?

1548332494667

,k ≧ 0

{an=a0an1+a1an2++an1a0,n1a0=1an=cn=1n+1(2nn)

變形

  • {an=a0an1+a1an2++an1a0,n1a0=1
    • an=cn=1n+1(2nn)
  • {an=a1an1+a2an2++an1a1,n1a1=1
    • an=cn1=1n(2(n1)n1)
  • {an=a2an1+a3an2++an1a2,n1a2=1
    • an=cn2=1n+1(2(n2)n2)

Example

n 個變數 x1,x2,,xn 之合法的括號數有幾個?

1548332797656

,k ≧ 1

{an=a1an1+a2an2++an1a1,n1a1=1cn1=1n(2(n1)n1)

「組合證明」推導

前導

令 Catalan number 等於 {an=a0an1+a1an2++an1a0,n1a0=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) 只能以規定的兩種步伐至 (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=a0an1+a1an2++an1a0,為以下方法數組成
    • (「自(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」個數問題等價

組合證明

一樣是上述的簡化的「合法路徑問題」,由下圖來討論

1548319123283

自 (0, 0) 至 (16, 16) 且不得超過中間雙線的部分(可觸及)

合法示意圖:

1548319440435

非法示意圖:

1548319549796

每個違法的路徑,必定會和下方紅色雙斜線接觸

1548320935256

「開始違法的座標」之後的路徑對紅色雙斜線做對稱化,則最後到達的座標必定在 (15,17),而這種轉換有幾個特性:

  • 1-1 對應
  • 可逆
    • 若再一次對稱回來,必定會對應到一個違法的路徑自(0,0)至(16,16)

所以自(0,0)至(15,17)的每種路徑,皆會對應到一個違法路徑

  • 合法路徑方法數
    • (3216)(3215)=116+1(21616) 為「Catalan number」
  • 所以從(0, 0)至(n, n)的「合法路徑為」
    • (2nn)(2nn1)

Example

有一場選舉,兩個候選人 A、B,假設知道 A 的票數一定比 B 多,假設 A 的總得票數為 p ,B 的總得票數為 q,請問有幾種開票的方法可保證每個當下 A 的得票數會大於 B 當下的得票數?

分析

有別於上面的題目,此處 A 每個當下的得票數絕對會比 B 每個當下的得票數還多

  • 不合法的開票方法:A→A→B→B→...
1548330759722

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

1548331206829

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

1548332141506
  • 合法的開票方法為
    • ((151)+11151)((111)+15111)=(2514)(2510)=1188640
  • 原本的問題之合法開票數
    • ((p1)+qp1)((q1)+pq1)