複製鏈接
請複製以下鏈接發送給好友

catalan

鎖定
卡塔蘭數組合數學中一個常在各種計數問題中出現的數列。以比利時的數學家歐仁·查理·卡塔蘭(1814–1894)命名。歷史上,清代數學家明安圖(1692年-1763年)在其《割圜密率捷法》最早用到“卡塔蘭數”,遠遠早於卡塔蘭。有中國學者建議將此數命名為“明安圖數”或“明安圖-卡塔蘭數”。卡塔蘭數的一般公式為 C(2n,n)/(n+1)。
中文名
卡塔蘭數
外文名
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出棧次序問題

一個棧(無窮大)的進棧序列為1,2,3,..n,有多少個不同的出棧序列?

catalan關於這個問題的5種變型

(2).找零錢(找一半)
有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票,另外n人只有10元鈔票,劇院無其它鈔票,問有多少種方法使得只要有10元的人買票,售票處就有5元的鈔票找零?
(3).三角網格
形如這樣的直角三角形網格,從左上角開始,只能向右走和向下走,問總共有多少種走法?
(4).括號排列
矩陣連乘:
,共有(n+1)項,依據乘法結合律,不改變其順序,只用括號表示成對的乘積,試問有幾種括號化的方案?或者説:有n對括號,可以並列或嵌套排列,共有多少種情況?
(5).球盒問題
球分兩種顏色,黑色和白色分別各有n只,盒子數量和球的個數相同,每個盒子裏面只能放一隻球,並且必須滿足如下限制,即每一個白球必須和一隻黑球配對(白球在黑球前,允許嵌套)。
例.用0表示白球,1表示黑球,則:
0011,010101,001011合法。
1100,101010,010110不合法。
(6).最適合理解的模型
n個0和n個1組成一個2n位的2進制數,要求從左到右掃描時,1的累計數始終都小於等於0的累計數,求滿足條件的數有多少?

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類似題目

(1).將多邊形劃分為三角形問題。將一個凸多邊形區域分成三角形區域的方法數?
(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]