脚本宝典收集整理的这篇文章主要介绍了[数学]卡特兰数，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

前言

卡特兰数是初赛中比较重要的数学知识，所以写篇博客总结一下。

定义

用 (C_n) 表示从 ((0,0)) 出发，每次只能向右或向上走 1 步，且 (x) 轴的值始终不小于 (y) 轴的值，到 ((n,n))的方案种数。

通项+证明

证明：

不考虑越过线的情况的话显然有 (left(begin{matrix}2n \ nend{matrix}right)) 种情况。

考虑非法的情况，令直线 (l:y=x+1)，那么每一个非法的方案都与 (l) 有至少 1 个交点。

对于每一个方案，我们取 (x) 值最小且在 (l) 上的点记为 (p(x_1,y_1))，将 (x>x_1,yleq x) 的点沿 (l) 对称，那么就变为从 ((0,0)) 到 ((n-1,n+1)) 的路径了，显然是一个映射，所以有 (left(begin{matrix}2n \ {n-1}end{matrix}right)) 种非法方案。

所以 (C_n=left(begin{matrix}2n \ nend{matrix}right) - left(begin{matrix}2n \ {n-1}end{matrix}right))。

化简

应用

1. (n) 对括号的合法配对方案书
2. (n) 个节点的二叉树的形态数
3. (n+1) 个叶子（(n) 个非叶节点）的满二叉树的形态数, 走到左儿子 (+1),走到 右儿子 (-1),类似于括号匹配(大致同2)
4. (n) 个数入栈后出栈的排列总数
5. 对凸 (n+2) 边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)
6. (n) 层的阶梯切割为 (n) 个矩形的切法数

转自 https://www.cnblogs.COM/linzhengmin/p/11298140.htML。

脚本宝典总结

以上是脚本宝典为你收集整理的[数学]卡特兰数全部内容，希望文章能够帮你解决[数学]卡特兰数所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。