【学习笔记】卡特兰数

发布时间 2023-10-28 22:21:14作者: CCComfy

卡特兰数

定义:

卡特兰数的计算公式涉及组合计数,它是很多组合问题的数学模型,是一个很常见的数列。

\(\bf{\underline{卡特兰数(Catalan)}}\) 是一个数列,它的一种定义是:

\[C_n=\frac{1}{n+1}\binom{2n}{n},n=0,1,2,... \]

卡特兰数有三个计算公式:

公式1

\[C_n=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n}-\binom{2n}{n+1} \]

适用于 \(n\) 较大的情况。

公式2

\[C_n=\sum C_kC_{n-k},C_0=1 \]

适用于 \(n\) 较小的卡特兰数,不需要求逆元,复杂度 \(n^2\)

公式3

\[C_n=\frac{4n-2}{n+1}C_{n-1},C_0=1 \]

接下来我们通过棋盘问题来推导公式1,通过二叉树问题来推导公式2。

应用

  • \(\bf{\underline{棋盘问题(公式1)}}\)

问题描述:现有一个 \(n\times n\) 的棋盘,从左下角走到右上角,且一直在主对角线下面走,不能穿过主对角线,求路径的方案数。

这个限制等价于走到任意一步 \(k\) 都需要满足向右走的次数大于等于向上走的次数。

首先不考虑主对角线的限制,那么从 \((0,0)\) 走到 \((n,n)\) 的方案数为 \(\binom{2n}{n}\),组合意义为:

每一步我可以选择向上走(记为 \(1\))和向右走(记为 \(2\)),一共走 \(2n\) 步,相当于一个长度为 \(2n\) 的全部为 \(0\) 的序列,我们需要选择其中的 \(n\) 个位置将其填为 \(1\),即 \(2n\)\(n\),为 \(\binom{2n}{n}\)

那么我们考虑加上这个限制,需要从总方案数上减去不合法方案数,我们看一种不合法情况:

image

如图,我们在对角线上面一格再画一个与其平行的对角线,可以发现只有所以穿过红线的路径(即不合法路径)才和蓝线有交,我们就是要统计这样的路径。
然后我们将这些路径在跨过红线后的部分关于蓝线对称:

image

可以发现这些线的终点都是 \((n-1,n+1)\),也就是 \((n,n)\) 关于蓝线对称后的点,这些路径与原跨过红线的路径都是一一对应的,这部分的方案数同理是 \(\binom{2n}{n-1}\),即不合法的路径数量,所以合法的路径的数量的即为两者相减:

\[\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n} \]

这正好就是卡特兰数的公式1。

  • \(\bf{\underline{括号问题(公式1)}}\)

问题描述:用 \(n\) 个左括号和 \(n\) 个右括号,求能组合出多少种合法的括号序列。

发现问题就是对于该字符串的任意长度前缀,都要满足左括号的数量大于等于右括号的数量,和上面的棋盘问题实际上是一样的,方案数为 \(C_n\)

  • \(\bf{\underline{出栈序列问题(公式1)}}\)

问题描述:给定一个入栈序列,求有多少种不同的出栈序列?

对于每个数,都是入栈一次,出栈一次,对于每个时刻,只有栈的大小大于等于 \(1\) 才可以出栈,即每时每刻需要满足入栈次数大于等于出栈次数,还是卡特兰数、

  • \(\bf{\underline{二叉树问题(公式2)}}\)

问题描述:\(n\) 个节点构成的二叉树,求有多少种不同的形态?

这个问题其实就是公式2的模型,设 \(f_{x,i}\)\(x\) 子树分配 \(i\) 个点的答案,考虑从叶子节点往上递归。

对于叶子节点,\(f_{x,0}=1\)

对于一个非叶子节点 \(x\),设其左子树节点数量+右子树节点数量 \(=k\),则

\[\begin{aligned} f_{x,k} & = f_{ls,k}\times f_{rs,0}+f_{ls,k-1}\times f_{rs,1}+...+f_{ls,1}\times_{rs,k-1}+f_{ls,0}+f_{rs,k}\\ & = \sum f_{ls,i}\times f_{rs,k-i} \end{aligned} \]

为卡特兰数递推式。

\[C_n=\sum C_i\times C_{n-i},C_0=1 \]

没了。