Catalan卡特蘭數入門

簡介

卡特蘭數是組合數學中的一種常見數列

它的前幾項為：

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

公式

遞歸公式1

$f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)$

遞歸公式2

$f(n)=\frac{f(n-1)*(4*n-2)}{n+1}$

組合公式1

$f(n)=\frac{C_{2n}^n}{n+1}$

組合公式2，重要！重要！重要！

$f(n)=C_{2n}^n-C_{2*n}^{n-1}$

遞推公式

$f[n]=\sum_{i=0}^{n-1}f[i]*f[n-i-1]$

一般在做題的時候，都是利用這個公式進行遞推

證明

不會:stuck_out_tongue_closed_eyes:。（衆人：那你在這瞎bb啥。:triumph:）

這個東西的證明我确實不會

不過我在這裡教大家一種非常簡單易懂的記憶方法，

記$f[n]$為卡特蘭數的第$n$項

首先你要明白一件事情

一棵$n$個節點的二叉樹的形态總數，就是卡特蘭數的第$n$項

對于一棵二叉樹，遞歸的考慮

一棵隻有一個節點的二叉樹隻有一種形态

對于不是一個節點的二叉樹，按照他的左右孩子進行讨論

設它的左孩子有$i$個節點，那麼它的形态數為$f[i]$

那麼它的右孩子有$n-i-1$個節點，那麼它的形态數為$f[n-i-1]$ 

又因為每一個節點都可以作為根節點

是以不難得到遞推式

例題

都是裸題我就不細講了

洛谷P1722 矩陣 II

http://www.cnblogs.com/zwfymqz/p/7725346.html

洛谷P1044 棧

洛谷P1976 雞蛋餅

http://www.cnblogs.com/zwfymqz/p/7725386.html

總結

卡特蘭數是一種常見的數列

需要每一位選手掌握它的遞推式

卡特蘭數一般不會單獨出現，往往會出現在一些題目的部分分中，如2017某省省選(具體忘記了。)

在考場上，要證明一個東西是卡特蘭數是非常困難的

自己手玩點小資料，隻要前幾項吻合，那一般就是卡特蘭數啦

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。