數論之卡特蘭數

2020 年 12 月 1 日
筆記
數論

1、基本模型

有一個長度為 $2n$的$01$序列，其中$1,0$各 $n$個，要求對於任意的整數 $k \in [1,2n] $，數列的前 $k$個數中，$1$的個數不少於$0$

滿足條件的序列的數量為

\[Cat_n=\frac{C_{2n}^n}{n+1}
\]

另一種形式

\[Cat_n=C_{2n}^n-C_{cn}^{n-1}
\]

又一種形式

\[Cat(n)=\frac{1}{n+1}\sum_{i=0}^n{C_n^i}^2
\]

遞推式

\[Cat_n=\sum_{i=0}^{n-1}Cat_i \times Cat_{n-i-1}
\]

\[Cat(n+1)=\frac{2(2n+1)}{n+2}Cat(n)
\]

2、證明

主要是運用了翻折的思想

傳送門

可以通過這種方法得出更為普遍的結論

比如這道題

3、推論

以下問題都與卡特蘭數有關

$1$、$n$個左括弧和$n$個右括弧組成的合法括弧序列的數量為$Cat_n$

$2$、$1,2,…,n$經過一個棧，形成的合法出棧序列的數量為$Cat_n$

$3$、$n$個節點構成的不同二叉樹的數量為$Cat_n$

$4$、在平面直角坐標繫上，每一步只能向上或向右走，從$(0,0)$走到$(n,n)$並且除兩個端點外不接觸直線$y=x$的路線數量為$2Cat_n-1$

$5$、對凸 $n+2$ 邊形進行不同的三角形分割的方案數(分割線斷點僅為頂點，且分割線僅在頂點上相交)

$6$、$n$ 層的階梯切割為 $n$ 個矩形的切法數

4、解題思路

$1$、通過遞推式得到卡特蘭數

比如這道題

$2$、可以將題目轉化為卡特蘭數的模型

比如這道題

$3$、還可以找規律

卡特蘭數的前幾項:$1,1,2,5,14,42,132$

5、一些技巧

卡特蘭的題目有很多需要高精度，建議學習一下我的高精度板子

還有一些題目給出的模數不是質數

我們可以把模數分解質因數，求出在模每一個質數下的答案，再用中國剩餘定理和到一起

但是還有一種更簡單的方法

因為分子比分母中一定存在數量更多的(或一樣多)的因數 $p$

於是可以分別算出分子和分母中含有的某個質數 $p$ 的指數是多少

再用上面的指數減去下面的指數，做一個快速冪就行了

求 $n!$ 中 $p$ 的指數

int cnt=0;
while(n){
	n/=p;
	cnt+=;
}

Tags: 數論