【组合数学】从简单的计算机问题讲解Catalan数

Answer 1

锐腾君已经有一段时间没有出现。近期，大学里忙着期末考试，高中学生们也正面临1月份的考试。大家都忙于准备。

上周一，锐腾的一门课程迎来了期末考试。我在此推荐复旦学子可以考虑第五模块的《计算思维》课程，汪老师和黄老师的课程非常有趣，能学到不少知识。上课时甚至有机会与黄老师进行一些特别的互动（不过实际上并没有）。

这门课的期末考试中有一道题目是这样的：对于n个元素进行入栈出栈操作，总共有多少种出栈序列？

即便部分读者可能不明白这个问题的含义，本文将提供直观解答。本文大纲如下：

通过合法括号串引入Catalan计数问题
利用递推方法解决Catalan计数问题
利用基本计数方法解决Catalan计数问题
(可选)从Dyck路问题再看Catalan计数问题
(可选)简单的生成函数理论
(可选)利用生成函数理论解决Catalan计数问题
Catalan数的实际应用问题

阅读建议：数学基础一般的读者可以略过第4-6部分，仅阅读第1-3及第7部分。若第3部分难以理解，可直接略过证明部分。

从合法括号串引出Catalan计数问题

让我们首先考虑一个基本问题：电脑识别含括号的表达式时如何进行配对？例如，对于表达式 (a+(b-c)*2)^(d+e)，如何判断括号结构？这可以简化为括号串 (())()。

括号串只包含左括号和右括号。合法括号串意味着左括号数量始终大于等于右括号数量，直到结束。例如，对于1对左右括号，只有一个合法括号串：()；对于2对左右括号，有两个合法括号串：(()) 和 ()()；对于3对左右括号，有5个合法括号串：((())), ()(()), ()()(), (())(), (()())。

对于n对左右括号，合法括号串数量称为Catalan数。本文将探讨如何计算这类问题。

利用递推方法求解Catalan计数问题

我们观察Catalan计数问题的递推性质。例如，对2对括号，有2种合法括号串：(())和()()。这可以分解为两个子结构：(())和()()，每个子结构都是一个合法括号串。

如果考虑所有合法括号串的构成，我们发现它们可以由若干个基本结构（本原括号串）组成。每个基本结构都包含一对左右括号。我们可以通过递推方式计算Catalan数，其中初值条件为：C(0) = 1。

利用基本计数方法求解Catalan计数问题

我们可以通过考虑反面问题简化计数过程。合法括号串意味着左括号数量始终大于等于右括号数量。如果我们放宽这个条件，所有可能的括号排列数量可以通过组合数计算得出。然后，我们只需减去不合法的括号排列数量。

不合法的括号排列可以通过构造映射转换为合法排列，具体步骤如下。对于不合法的排列，存在一个最小位置使得前一部分左括号数量多于右括号。通过转换这个位置前后括号顺序，可以得到对应合法排列。

从Dyck路问题再看Catalan计数问题

我们可以将Catalan计数问题与Dyck路问题联系起来。Dyck路问题是寻找在方格中从起点到终点的路径，路径只向右或向上，且不穿越对角线。将路径中的右移对应左括号，上移对应右括号，Catalan计数问题便与Dyck路问题相关。

简单的生成函数理论

生成函数提供了一种将数列映射为函数的方法，简化了复杂计数问题的解决。本部分将介绍普通型生成函数的基础内容，包括生成函数的定义、运算以及与Catalan数的关系。

Catalan数的实际应用问题

Catalan数的应用广泛，从括号串到Dyck路问题，再到不相交的弦、凸多边形三角划分和出栈次序问题等。本文仅举几例，如：给定圆周上n个点，连接两两点之间不相交的弦；在凸多边形中，通过若干对角线划分成多个三角形的方案数。

更多Catalan数的应用可参考相关文献和资源。本文结束于后记，锐腾君因撰写本文耗时过长而感到疲劳。