当前位置：首页 > news >正文

卡特兰数、斯特林数基础

news 2025/8/4 21:48:27

卡特兰数

从格点 $(0, 0)$ 走到格点 $(n, n)$ ，只能向右或向上走，不能穿过对角线，的路径的条数，称为卡特兰数 $H_n$ 。

则有 $H_0=1$ 。

通项公式：

$Hn=(2nn)−(2nn−1)H_n=\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} 2n\\ n-1 \end{pmatrix}$
$Hn=(2nn)n+1H_n=\frac {\begin{pmatrix} 2n\\ n \end{pmatrix}}{n+1}$
$Hn=4n−2n+1Hn−1H_n=\frac{4n-2}{n+1}H_{n-1}$

折线法

证明一下卡特兰数的公式。

先证明公式1：
如果没有限制，那么路径总数是，从 $2 n$ 步移动之中，选出 $n$ 步向上走，另外 $n$ 步向右走的方案数 $(2nn)\begin{pmatrix} 2n\\ n \end{pmatrix}$ 。

如果有限制，我们画出 $y = x + 1$ 的函数图像，碰到这条线，意味着不合法。
把所有不合法的路径沿着这条图像对折过来，其终点必然是 $(n - 1, n + 1)$ 。
换句话说，所有到达 $(n - 1, n + 1)$ 的路径，都对应着到达 $(n, n)$ 的一条不合法路径。因此答案就是 $(2nn)−(n+1+n−1n−1)\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} n+1+n-1\\ n-1 \end{pmatrix}$
在这里插入图片描述

QED.

证明一下公式2：
$(2nn)−(2nn−1)\begin{pmatrix} 2n\\ n \end{pmatrix}-\begin{pmatrix} 2n\\ n-1 \end{pmatrix}$
$=(2n)!n!n!−(2n)!(n+1)!(n−1)!=\frac{(2n)!}{n!n!}-\frac {(2n)!}{(n+1)!(n-1)!}$
$=(2n)!n!(n−1)!n−(2n)!n!(n−1)!(n+1)=\frac{(2n)!}{n!(n-1)!n}-\frac {(2n)!}{n!(n-1)!(n+1)}$
$=(2n)!n!(n−1)!⋅(1n−1n+1)=\frac{(2n)!}{n!(n-1)!}\cdot\left(\frac{1}{n}-\frac 1{n+1}\right)$
$=(2n)!n!(n−1)!n−(2n)!n!(n−1)!(n+1)=\frac{(2n)!}{n!(n-1)!n}-\frac {(2n)!}{n!(n-1)!(n+1)}$
$=(2n)!n!(n−1)!⋅(1n−1n+1)=\frac{(2n)!}{n!(n-1)!}\cdot\left(\frac{1}{n}-\frac 1{n+1}\right)$
$=(2n)!n!(n−1)!⋅1n(n+1)=\frac{(2n)!}{n!(n-1)!}\cdot\frac {1}{n(n+1)}$
$=(2n)!n!n!⋅1n+1=\frac{(2n)!}{n!n!}\cdot\frac {1}{n+1}$
$=(2nn)⋅1n+1=\begin{pmatrix} 2n\\ n \end{pmatrix}\cdot\frac {1}{n+1}$

QED.

证明一下公式3：
留作习题，读者自证不难。

常见情况

特点：一种操作不能超过另一种操作，或操作之间不能有交集。

例如：

一个由 $n$ 个 $0$ ， $n$ 个 $1$ 组成的长度为 $2 n$ 的字符串，满足所有前缀中， $1$ 的个数不能超过 $0$ 的个数，这样的子串数量。
包含 $n$ 组括号的合法表达式的数量。
（想要括号序列合法，必须保证所有前缀中，左括号的数量大于等于右括号的数量）
一个栈的进栈序列为 $1, 2, ..., n$ ，则出栈序列的可能数量。
（必须保证出栈数量小于等于进栈数量）
在圆上选择 $2 n$ 个点，连接起来形成 $n$ 条不相交的弦的方案数。
（把 $n$ 条不相交的弦映射为括号序列，把弦的左端映射为左括号，右端映射为右括号）
通过连接顶点将 $n + 2$ 条边的正多边形分为 $n$ 个三角形的方案数（三角剖分）。
（想要保证分为 $n$ 个三角形，必须保证连接的线不相交）
$n$ 个节点可以构造多少颗不同的二叉树？
考虑对 $n + 2$ 条边的多边形三角剖分，把剖分得出的三角形抽象为一个节点，对它相邻的三角形连边，最后得出必定是一颗二叉树。
一段连乘积有多少种运算次序？
（相当于给连乘积加括号）

公式法

事实上有：
$Hn=∑i=0n−1HiHn−i−1H_n=\overset{n-1}{\underset{i=0}\sum}H_iH_{n-i-1}$

可以从两个方面来证明一下：

出栈序列
考虑 $i$ 是最后一个出栈的数，则 $[1, i - 1]$ 在 $i$ 进栈之前就出栈了，情况数有 $H_{i-1}$ 种，而 $i$ 后面的 $n - i$ 个数，则必然在 $i$ 出栈前就出栈了，情况数有 $H_{n-i}$ 种，枚举这个 $i$ ，得到
$Hn=∑i=1nHi−1Hn−i=∑i=0n−1HiHn−i−1H_n=\overset{n}{\underset{i=1}\sum}H_{i-1}H_{n-i}=\overset{n-1}{\underset{i=0}\sum}H_iH_{n-i-1}$
格点计数
我们知道，在格点卡特兰数的要求中，路径不能越过对角线。我们可知，在走到终点之前的一步，一定是向上走的：

红色表示最后一步。

显然，碰到对角线之后，一定是向右走的，我们枚举对角线上的一个点，使得走完向右走的那一步之后，不能越过新的对角线，统计的路径条数：
在这里插入图片描述
绿色，枚举的位置。
红色，最后一步。
蓝色，新的对角线。

此时我们发现，从底下走到绿色圆圈，不能越过对角线。与从绿色箭头走到红色圆圈，不能越过蓝线，是两个更小的卡特兰数问题，因此可以用乘法原理计数。

我们注意到，我们枚举的一种新的情况，在我们枚举的更旧的情况中都属于不合法情况，不会被重复统计。

QED.

用公式同样可以解释各种卡特兰数的情况。

一个由 $n$ 个 $0$ ， $n$ 个 $1$ 组成的长度为 $2 n$ 的字符串，满足所有前缀中， $1$ 的个数不能超过 $0$ 的个数，这样的子串数量。
注意到最后一个字符一定是 $1$ ，枚举一个位置的 $0$ ，使得这个 $0$ 与末尾的那个 $1$ 匹配，转化为格点计数的情况。
包含 $n$ 组括号的合法表达式的数量。
同理。
一个栈的进栈序列为 $1, 2, ..., n$ ，则出栈序列的可能数量。
同理。
在圆上选择 $2 n$ 个点，连接起来形成 $n$ 条不相交的弦的方案数。
同理，枚举一个点与最后那个点（任意指定一个固定的点为最后的点）连接成弦。
通过连接顶点将 $n + 2$ 条边的正多边形分为 $n$ 个三角形的方案数（三角剖分）。
同理4。
$n$ 个节点可以构造多少颗不同的二叉树？
枚举根节点有 $i$ 个左子树，则就会有 $n - i - 1$ 个右子树，显然。

斯特林数

第一类斯特林数

定义 $[nm]\begin{bmatrix}n\\ m\end{bmatrix}$ 表示 $n$ 元集合划分为 $m$ 个非空环排列的方案数，即无符号第一类斯特林数，或简称为第一类斯特林数，斯特林轮换数。

第一类斯特林数有递推式：
$[nm]=[n−1m−1]+(n−1)[n−1m]\begin{bmatrix} n\\ m \end{bmatrix}=\begin{bmatrix} n-1\\ m-1 \end{bmatrix}+(n-1)\begin{bmatrix} n-1\\ m \end{bmatrix}$

递推式容易证明，留作习题。

第二类斯特林数

定义 ${nm}\begin{Bmatrix} n\\ m \end{Bmatrix}$ 表示将 $n$ 元集合划分为 $m$ 个非空子集的方案数，即第二类斯特林数，或斯特林子集数。

第二类斯特林数有递推式：
${nm}={n−1m−1}+m{n−1m}\begin{Bmatrix} n\\ m \end{Bmatrix}=\begin{Bmatrix} n-1\\ m-1 \end{Bmatrix}+m\begin{Bmatrix} n-1\\ m \end{Bmatrix}$