组合数学入门（2）：卡特兰数 卡特兰数是组合数学中最重要的数列之一。它们出现在许多表面上看起来完全不同的计数问题中，但实际上这些问题都具有相同的内在结构：平衡性、递归性以及“不交叉”约束。 在本文中，我们将介绍卡特兰数/Catalan，展示几个重要公式，并解释一些经典应用场景，特别是路径不能越过对角线的网格行走问题。 什么是卡特兰数？ 卡特兰数列如下： 第 n 个卡特兰数的一般公式为： 一个等价形式为： 这两个公式完全等价，在组合数学中都经常出现。 为什么卡特兰数很重要 卡特兰数用于计数许多具有递归结构或平衡结构的问题。它们通常出现在以下情形中： 对象必须以平衡方式构造， 路径必须保持在某个边界之内， 配对之间不能交叉， 结构可以被拆分为独立的左右部分。 因此，它们广泛出现在括号、树、网格、多边形以及栈操作等问题中。 一些重要的卡特兰公式 闭式公式 差分等价形式 递推公式 这个递推公式非常重要。它说明：如果一个规模为 n 的结构可以拆分为左侧大小为 i、右侧大小为 n-1-i 的两个部分，那么总数就是对所有可能拆分方式求和。 生成函数 渐近增长 …
组合简介（组合数学入门） 视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook 组合计数是在顺序不重要时选择项目的方式。我们从一个简单的格子行走示例出发建立直觉，介绍二项式记号，推导公式，解释递推关系 ，并把所有内容联系到帕斯卡三角。 格子行走示例 — 从左下到右上路径 想象你只能向右（R）或向上（U）移动。要从左下走到需要三次向右和两次向上的点，每一条最短路径都是由五步组成的序列，其中包含三个 R 和两个 U。 每条有效路径只是从五个位置中选择两个放 U（其余为 R）。所以这样的路径数就是“从 5 …
卡塔兰数(Catalan Numbers) 是个很神奇的数列. 高中信息学竞赛很喜欢出有关卡塔兰数的问题, 特别是在初赛(笔试)的时候, 经常会有一题真空题就是卡塔兰数的应用. 在组合数学中, 卡塔兰数有着许多应用, 卡塔兰数的前几个数字是: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, …
