Catalan數應用

• Catalan數應用
  • 原理
  • 卡特蘭數經典應用
    • 括號化
    • 買票找零
    • 組合數與階乘計算

卡特蘭數又稱卡塔蘭數，是組合數學中一個常出現在各種計數問題中的數列。由以比利時的數學家歐仁·查理·卡塔蘭 (1814–1894)命名。
其前幾項為 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … Catalan數是許多計數問題的最終形式。

原理

• 令h(0)=1,h(1)=1，catalan數滿足遞推式：
  h(n)=h(0)?h(n?1)+h(1)?h(n?2)+...+h(n?1)?h(0)(n>=2)

• 另類遞推公式:

• h(n)=h(n?1)?(4?n?2)/(n+1)
• x=(2nn)n+1(n=0,1,2,?)
• h(n)=(2nn)?(2nn?1)(n=0,1,2,?)

公式中(nm)=n!(n?m)!

卡特蘭數經典應用

括號化

矩陣鏈乘： f(n)=a1×a2×a3×?×an，依據乘法結合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？

思路：可以這樣考慮，首先通過括號化，將公式分成兩個部分，然后分別對兩個部分進行括號化。比如分成(a1)×(a2×a3×?×an)，然后再對(a1)和(a2×a3×?×an)分別括號化；又如分成(a1×a2)×(a3×?×an)，然后再對(a1×a2)和 (a3×?×an)括號化;以此類推，得公式

f(n)=f(1)f(n?1)+f(2)f(n?2)+f(3)f(n?3)+?+f(n?1)f(1)

f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5,結合遞歸式，不難發現f(n)=h(n-1)。

買票找零

原題描述如下：

2n個人排隊買票，其中n個人持50元，n個人持100元。每張票50元，且一人只買一張票。初始時售票處沒有零錢找零。請問這2n個人一共有多少種排隊順序，不至于使售票處找不開錢？

思路：隊伍的序號標為0,1,…,2n-1,并把50元看作左括號，100元看作右括號，合法序列即括號能完成配對的序列。對于一個合法的序列，第0個一定是左括號，它必然與某個右括號配對，記其位置為k。那么從1到k-1、k+1到2n-1也分別是兩個合法序列。那么，k必然是奇數（1到k-1一共有偶數個），設k=2i+1。那么剩余括號的合法序列數為f(2i)*f(2n-2i-2)個。取i=0到n-1累加即可。

f(2n)=∑i=0n?1f(2i)f(2n?2i?2)(n≥1)

另f(0)=0,(00)=0,即可得

f(2n)=(2nn)n+1(n≥1)

公式推導如下，出自從《編程之美》買票找零問題說起，娓娓道來卡特蘭數——兼爬坑指

構造生成函數:

g(x)=h0x2+h2x4+?+h2n?2x2n+h2nx2n+2+?
其中 h2n=f(2n)=∑n?1i=0f(2i)f(2n?2i?2)(n≥1)

生成函數平方：

[g(x)]2==h0x2+h2x4+?+h2n?2x2n+h2nx2n+2+?h20x4+(h0h2+h2h0)x6+?+(h0h2n?2+h2h2n?4+?+h2n?2h0)x2n+2+?

則：

[g(x)]2?g(x)=h20x4?h2x4?h0x2

對于題目,假設h0=f(0)=0,則根據遞推公式后續項全為0，不合題意，那么h0=f(0)=1,可以推出h2=f(2)=1,帶入公式，則有:

[g(x)]2?g(x)+x2=0

解得g(x)=1±1?4x2??????√2
根據生成函數的各項系數為非負，舍去其一，在根據

(1+z)1/2=1+∑n=1∞(?1)n?1n×22n?1(2n?2n?1)zn

可以得到

g(x)=∑n=1∞1n(2n?2n?1)x2n

則

h2n=1n+1(2nn)

組合數與階乘計算

#!/usr/bin/env python # -*- coding: utf-8 -*-import operator'''factorial function:階乘函數;也可用math.factorial''' def factorial(n):return reduce(operator.mul, range(1, int(n+1)));'''combinational calculation:組合計算''' def comb(n, m):return reduce(operator.mul, range(n-m+1, n+1)) / factorial(m)'''calculation on the arrangement:排列組合計算''' def arr(n, m):return factorial(n) / factorial(n-m)if __name__ == "__main__":print factorial(10)print comb(6,3)print arr(10,7)

參考：

• http://www.cnblogs.com/wuyuegb2312/p/3016878.html

總結

以上是生活随笔為你收集整理的Catalan数应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。