卡特兰数列 我们记为卡特兰数列，满足也被称为第个卡特兰数.
卡特兰数列是组合数学中一个非常重要的数列，其一个重要的原因同时也是卡特兰模型核心与本质的式子是
.
为了更加清晰地认识这件事，我们引入一个经典的卡特兰模型.
Dyck path 一个长度为的Dyck path是一个由向量与构成，从点到，且不经过轴下方的路径.记所有长度为的Dyck path构成的集合为. 以下是n=3时的全部Dyck path.
Fig 1. 时的全部Dyck path.
证明的证明方法非常经典.
考虑所有不同的由向量与构成，从点到的路径，其数量为.
不失一般性，考虑任意一条不满足要求的路径，其必与有交点，将其第一次与相交之前的部分沿对称，得到一条新的从点到的路径.
Fig 2. 一个上述对应的例子.
因为每一条不满足要求的路径都与有交点，而每一条从点到的路径也都与有交点，故可以简单证明这是一个一一对应.从而
然而实际上，正如文章开头所说，卡特兰模型最本质与核心的性质依然是它的递推式 ， 这个表达式告诉我们卡特兰模型是如何“生成”的.
.
实际上，让我们将按照出发后第一次碰到的横坐标分类.一般而言，对于第一次碰到的横坐标为的Dyck path，共有种可能的.这是因为前半段是由向量与构成，从到且不经过下方的路径，显然共有种可能（沿平移）；后半段是由向量与构成，从到且不经过轴下方的路径，显然共有种可能（沿平移.）.对遍历，我们就得到了
.
Fig 3. 第一次碰到的横坐标为的Dyck path .
Fig 4. 中所有第一次碰到的横坐标为的Dyck path.
231-回避 排列 对于，若不存在整数，使得，则称为长度为的231-回避排列.将所有长度为的231-回避排列构成的集合记为.
Table 1. 时的全部231-回避排列按的取值分类.
既然我们在这里介绍231-回避排列，大概也是因为231-回避排列也是卡特兰模型.
去证明一个数列是卡特兰数列，主要有三种方法.
①一一对应
如果我们能找到该数列的组合意义与已知某卡特兰模型具有一个有组合意义的一一对应，则可证明其为卡特兰数列.
②递推式
如果我们能找到该数列的递推式，其恰好与卡特兰数的递推式一致，且数列前几项相等，则可证明其为卡特兰数列.
③通项公式
当然，若我们直接能够证明其通项公式与卡特兰数列相同，当然可证明其为卡特兰数列.
类似Dyck path讨论的那样，我们也可以讨论231-回避排列是如何生成的，即，如何满足递推式.当然，这看起来也是非常显然的，因为毕竟我们刚刚已经把它按照正确的方式分类了——按照首个数字.（值得指出两点，首先首数字是很显然的可以纳入考虑的分类标准，其次实际上我们可以观察到，一个正确的分类标准必然可以将分为四类，即四类.这其实暗涵着对应的这类其实是从时的种生成的.那么中哪个是一组实际上是易于观察的.虽然这里实际上按照的位置分类也是合理的.）
一般来说，对于长为的首个数字是的231-回避排列，其第至第个位置必然是数字至，而第位至第位则必然是数字至.这是因为如果至的某个数字出现在第至第个位置，则必然会导致其大于某一个第位至第位的数字，从而出现231-子列.
Fig 5. 首位为的231-回避排列.
那么接下来就可以开始我们真正的主题了.既然大家都是卡特兰模型，那么Dyck path与231-回避排列之间有没有具有组合意义的一一对应关系呢？答案显然是有的.那么就等我下一篇文章介绍这个一一对应关系以及更多的卡特兰模型吧.
作者介绍
于睿元，七年数学竞赛教学经验，明诚外国语学校首届竞赛班教练之一，首届实验班数学老师.曾在北京省队做省队培训.在北斗学友、学为、学大伟业等机构做全国竞赛讲座，曾任三帆中学、十一学校分校、济南天山实验学校等学校外聘竞赛教练.多次在《中等数学》发表文章与模拟题.多次参与全国数学竞赛命题研讨会并发言.四年杜克大学数学竞赛中国区学术负责人，负责命题、讲座等.为学而思与爱尖子等机构与比赛提供竞赛试题.
一些说明
总而言之还是打算重新捡起来做一做公众号，一方面似乎是职业生涯一条可选的发展路径，另一方面确实写写东西还挺有意思的.
目前大体没什么计划，未来大约写一个卡特兰数相对比较长的专题，然后写一些原创题、赛题、杂题之类的，不过大约还是想写什么写什么，以计数组合与竞赛组合为主.会努力讲好一个问题是如何思考与分析得到而非单纯写解答.
阅读人群大约还是数学竞赛教练以及那些想在组合上进步的同学吧，原则上来说至少基本计数原理、各类基础方法如归纳、染色、抽屉、算两次等基本掌握，至少已经是冲刺一等奖水平再来阅读是比较有价值的.
