-
catalan
鎖定
- 中文名
- 卡塔蘭數
- 外文名
- catalan
- 別 名
- 卡特蘭數
- 命 名
- 歐仁·查理·卡塔蘭
- 類 型
- 常在各種計數問題中出現的數列
目錄
catalan性質
令h(0)=1,h(1)=1，卡塔蘭數滿足遞歸式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),這是n階遞推關係;
還可以化簡為1階遞推關係: 如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1
該遞推關係的解為：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
卡塔蘭數列的前幾項為(sequence A 0 0 0 1 0 8 in OEIS) [注： n = 0, 1, 2, 3, … n]
1, 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理解應用和公式推導
catalan出棧次序問題
catalan關於這個問題的5種變型
(2).找零錢（找一半）
有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少種方法使得只要有10元的人買票，售票處就有5元的鈔票找零？
(3).三角網格
形如這樣的直角三角形網格，從左上角開始，只能向右走和向下走，問總共有多少種走法？
(4).括號排列
矩陣連乘：
，共有（n+1）項，依據乘法結合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？或者説：有n對括號，可以並列或嵌套排列，共有多少種情況？
(5).球盒問題
例.用0表示白球，1表示黑球，則：
0011，010101，001011合法。
1100，101010，010110不合法。
(6).最適合理解的模型
catalan理解方式
模型 | 事件1 | 事件2 |
(1) | 入棧 | 出棧 |
(2) | 用5元支付 | 用10元支付 |
(3) | 向下走 | 向右走 |
(4) | 左括號 | 右括號 |
(5) | 0 | 1 |
(6) | 0 | 1 |
注：同列事件可視為等價，且在題目要求中事件1的次數/大小需要始終大於事件2。
觀察模型 (6)：在2n位上填入n個0的方案數為
。而從
中減去不符合要求的方案數即為所求答案。
在從左往右掃時，必然會在某一個奇數位2p+1上首先出現p+1個1，和p個0
此後的 [2p+2,2n]上的2n−(2p+1)位有n−p個0, n−p−1個1。如若把後面這部分2n−(2p+1)位的1與0互換，使之成為n−p個1，n−p−1個0，結果得1個由n+1個1和n−1個0組成的2n位數，即一個不合法的方案必定對應着一個由n+1個1和n-1個0組成的一個排列。
可以倒過來反證：
任意一個由n+1個1和n-1個0組成的一個排列，由於1的個數多了2個，且2n為偶數，所以必定在某個奇數位2p+1上出現1的個數超過0的個數。同樣把後面部分1和0互換，成為了由n個0和n個1組成的2n位數。
由此，每一個不合法的方案總是與唯一一個由n+1個1和n−1個0組成的排列一一對應。
於是，不合法的方案數就可以寫作：
例如 10100101
是由4個0和4個1組成的8位2進制數。但從左而右掃描在第5位（顯示為紅色）出現0的累計數3超過1的累計數2，它對應於由3個1，5個0組成的10100010。
反過來 10100010
對應於 10100101
因而不合要求的2n位數與n+1個0，n－1個1組成的排列一一對應，故有“卡塔蘭數”Catalan
此公式還可繼續化簡：
catalan類似題目
(2).有N個節點的二叉樹共有多少種情形？
(3).一位大城市的律師在她住所以北n個街區和以東n個街區處工作。每天她走2n個街區去上班。如果他
從不穿越（但可以碰到）從家到辦公室的對角線，那麼有多少條可能的道路？
(4).在圓上選擇2n個點,將這些點成對連接起來使得所得到的n條線段不相交的方法數?
(5).與之相關的還有如NOIP2003 棧等題目。
catalan簡單代碼實現(python)
class Solution: def numTrees(self, n: int) -> int: #初始化一個數組，並將首個元素初始化為1 s=[0]*(n+1) s[0]=1 #開始循環遍歷 for i in range(1,n+1): #為節約內存，首先算出i-1的值 b=i-1 #為節約內存，只遍歷一半，並將這個結果乘以2即可 for j in range(i//2): s[i]+=s[j]*s[b-j] s[i]*=2 #當i為奇數時，還要將s[i//2]的值加上 if i%2==1: s[i]+=s[i//2]**2 #返回數組最後一個元素 return s[-1]
