卡特蘭數

Catalan 數列

Catalan 數列 \(H_n\) 可以應用於以下問題：

有 \(2n\) 個人排成一行進入劇場。入場費 5 元。其中只有 \(n\) 個人有一張 5 元鈔票，另外 \(n\) 人只有 10 元鈔票，劇院無其它鈔票，問有多少種方法使得只要有 10 元的人買票，售票處就有 5 元的鈔票找零？
有一個大小為 \(n\times n\) 的方格圖左下角為 \((0, 0)\) 右上角為 \((n, n)\)，從左下角開始每次都只能向右或者向上走一單位，不走到對角線 \(y=x\) 上方（但可以觸碰）的情況下到達右上角有多少可能的路徑？
在圓上選擇 \(2n\) 個點，將這些點成對連接起來使得所得到的 \(n\) 條線段不相交的方法數？
對角線不相交的情況下，將一個凸多邊形區域分成三角形區域的方法數？
一個棧（無窮大）的進棧序列為 \(1,2,3, \cdots ,n\) 有多少個不同的出棧序列？
\(n\) 個結點可構造多少個不同的二叉樹？
由 \(n\) 個 \(+1\) 和 \(n\) 個 \(-1\) 組成的 \(2n\) 個數 \(a_1,a_2, \cdots ,a_{2n}\)，其部分和滿足 \(a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)\)，有多少個滿足條件的數列？

其對應的序列為：

\(H_0\)	\(H_1\)	\(H_2\)	\(H_3\)	\(H_4\)	\(H_5\)	\(H_6\)	...
1	1	2	5	14	42	132	...

遞推式

該遞推關係的解為：

\[ H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}}) \]

關於 Catalan 數的常見公式：

\[ H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases} \]

\[ H_n = \frac{H_{n-1} (4n-2)}{n+1} \]

\[ H_n = \binom{2n}{n} - \binom{2n}{n-1} \]

例題洛谷 P1044 棧

題目大意：入棧順序為 \(1,2,\ldots ,n\)，求所有可能的出棧順序的總數。

C++Python

#include <iostream>
using namespace std;
int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 這裏用的是常見公式2
  cout << f[n] << endl;
  return 0;
}

f = [0] * 25
f[0] = 1
n = int(input())
for i in range(1, n + 1):
    f[i] = int(f[i - 1] * (4 * i - 2) // (i + 1))
    # 這裏用的是常見公式2
print(f[n])

封閉形式

卡特蘭數的遞推式為

\[ H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2) \]

其中 \(H_0=1,H_1=1\)。設它的普通生成函數為 \(H(x)\)。

我們發現卡特蘭數的遞推式與卷積的形式很相似，因此我們用卷積來構造關於 \(H(x)\) 的方程：

\[ \begin{aligned} H(x)&=\sum_{n\ge 0}H_nx^n\\ &=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\ &=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\ &=1+xH^2(x) \end{aligned} \]

解得

\[ H(x)=\frac{1\pm \sqrt{1-4x}}{2x} \]

那麼這就產生了一個問題：我們應該取哪一個根呢？我們將其分子有理化：

\[ H(x)=\frac{2}{1\mp \sqrt{1-4x}} \]

代入 \(x=0\)，我們得到的是 \(H(x)\) 的常數項，也就是 \(H_0\)。當 \(H(x)=\dfrac{2}{1+\sqrt{1-4x}}\) 的時候有 \(H(0)=1\)，滿足要求。而另一個解會出現分母為 \(0\) 的情況（不收斂），捨棄。

因此我們得到了卡特蘭數生成函數的封閉形式：

\[ H(x)=\frac{1- \sqrt{1-4x}}{2x} \]

接下來我們要將其展開。但注意到它的分母不是斐波那契數列那樣的多項式形式，因此不方便套用等比數列的展開形式。在這裏我們需要使用牛頓二項式定理。我們來先展開 \(\sqrt{1-4x}\)：

\[ \begin{aligned} (1-4x)^{\frac{1}{2}} &=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n \end{aligned} \tag{1} \]

注意到

\[ \begin{aligned} \left(\frac{1}{2}\right)^{\underline{n}} &=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3)!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned} \]

這裏使用了雙階乘的化簡技巧。那麼帶回 \((1)\) 得到

\[ \begin{aligned} (1-4x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n \end{aligned} \]

帶回原式得到

\[ \begin{aligned} H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\ &=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\ &=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\ \end{aligned} \]

這樣我們就得到了卡特蘭數的通項公式。

路徑計數問題

非降路徑是指只能向上或向右走的路徑。

從 \((0,0)\) 到 \((m,n)\) 的非降路徑數等於 \(m\) 個 \(x\) 和 \(n\) 個 \(y\) 的排列數，即 \(\dbinom{n + m}{m}\)。
從 \((0,0)\) 到 \((n,n)\) 的除端點外不接觸直線 \(y=x\) 的非降路徑數：

先考慮 \(y=x\) 下方的路徑，都是從 \((0, 0)\) 出發，經過 \((1, 0)\) 及 \((n, n-1)\) 到 \((n,n)\)，可以看做是 \((1,0)\) 到 \((n,n-1)\) 不接觸 \(y=x\) 的非降路徑數。

所有的的非降路徑有 \(\dbinom{2n-2}{n-1}\) 條。對於這裏面任意一條接觸了 \(y=x\) 的路徑，可以把它最後離開這條線的點到 \((1,0)\) 之間的部分關於 \(y=x\) 對稱變換，就得到從 \((0,1)\) 到 \((n,n-1)\) 的一條非降路徑。反之也成立。從而 \(y=x\) 下方的非降路徑數是 \(\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}\)。根據對稱性可知所求答案為 \(2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}\)。
從 \((0,0)\) 到 \((n,n)\) 的除端點外不穿過直線 \(y=x\) 的非降路徑數：

用類似的方法可以得到：\(\dfrac{2}{n+1}\dbinom{2n}{n}\)

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用