Catalan 数

Catalan 结构共同的核心不是表面形状，而是“第一次返回”或“根节点左右分裂”产生的唯一分解。唯一性保证不会重复计数，左右部分的独立性产生卷积，边界约束则把所有无约束对象中的越界部分恰好剔除。因而看到 $C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}$ 时，应寻找的是一个可定位的首个切口，而不是机械套公式。

$C_0,C_1,C_2,C_3,C_4=1,1,2,5,14$。长度 $2n$ 的括号序列需每个前缀左括号不少于右括号，不能只要求总数相等；反射原理从中央二项式系数中减去越界路径。并非所有“树”都由 Catalan 数计数，必须明确平面次序、根和节点度数等约定。公式中的平方根是形式幂级数分支；作为解析函数时其收敛半径为 $1/4$。不同 Catalan 对象之间的双射通常保留递归分解。

长度为 $6$ 的正确括号串有五个，例如 ()(()) 与 (()())。把首个左括号与其匹配右括号之间放入含 $2i$ 个符号的正确串，外侧放入含 $2(n-1-i)$ 个符号的正确串，便得到 $C_i{C}_{n-1-i}$。边界上，若只要求左右括号总数相同，则 ())(() 也被计入；前缀非负条件正是 Dyck 路径不得跌到横轴下方的几何约束。

递推关系公理库递推关系Recurrence relation用先前项规定序列当前项的关系。给出 Catalan 卷积，普通生成函数公理库普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。把它化为代数方程 $C(x)=1+xC(x{)}^2$，二项式系数公理库二项式系数Binomial coefficientn 元集合的 k 元子集数，记作 C(n,k)。再给出闭式。通过双射，同一序列同时计数平面二叉树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。、多边形三角剖分和栈可排序结构；应用前必须核对根、平面次序与标号是否与 Catalan 模型一致。