图上不来。。。好烦。。。。
亲爱的小伙伴们晚上好哟！继昨天的仿射变换之后，今天又是讨论组合数学问题的时候了。今天我们要来看的是一个神奇的数列，为了纪念比利时数学家卡特兰而把它叫做卡特兰（catalan)数.这个数列是卡特兰在研究凸n边形的剖时得到的。凸n＋2边形用其n－1条对角线把此凸n＋2边形分割为互不重叠的三角形，这种分法的总数为Tn。据说有几十种看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。
那么我们首先来回到卡特兰的时代，看一看这个数列的通项是怎么求解出来的吧。
我们用几个例子开始阐述问题:
首先是三角形, 只有一种方法分成三角形..就是什么都不做。
然后是四边形:
两种方法可以把四边形分成三角形
然后是五边形:
五种方法可以分解一个五边形(把一个角作2条线出来分三角, 有5个角, 故5种分法)
那么n边形可以有几种方法分成三角呢?
我们可以用一种“填括号”的方式来说明这个问题。也就是一种“对应方法”。
我们可以把这n+2条边用1,2，...,n+2来编号。在分好的三角形中，先把连接相邻两个顶点的对角线找出来，那么他们相当于是把两条相邻的边连接起来，那么我们可以把这两条边对应的数字用括号括起来。括起来的目的是把这两条边看成一个整体，因为两条中的任意一条都无法与其他的边相连了。在图形上，我们可以这样操作：把括起来的两条边擦掉，然后把连接他们的对角线看成新的边，然后在这些边中继续上面的操作。
比如上面这张图就可以这样表示：
1(（（23 ) 4）(56))
那么从最后一个数（n+2）开始数起，数字的个数至少要比左括号（“（”）的个数多1：这是因为边之间连线为两个数字添一个括号，对角线与边连线相当于增加1个数字和增加一个括号。而我们知道n+2条边有n-1条对角线，我们如果把刚才的数字记成1（也就是边的个数），把刚才的左括号（注意我们不考虑右括号是因为左括号确定以后右括号的补法是唯一确定的，并且左括号的个数比对角线个数多1）记成-1，那么上面这种排列就成了
1 -1 -1 -1 1 1 1 -1 1 1
于是这个问题又变成了n个-1和n+2个1排列，并且从右边数1的个数始终多于-1的情况数。
慢着，我们先回顾一下：刚才我们在分三角形，最后怎么变成排-1和1了？这就是前文所说的“对应方法”：分三角形也好，填括号也好，排-1和1也好，这三种不同的情景实际上是同一个问题的边形，它们所有可能的情况数是一模一样的。
最后，我们把答案算出来：首先最右的两个一定是1（最右边两个位置只能放数字不能放左括号），所以不妨把它们看做一个整体。那么就变成了2n+1个数排列的问题，并且从右往左数1始终不少于-1的个数。先不管这个要求，并且我们不需要考虑最右边的那个1，那么相当于在左边2n个位子选出n个放-1，结果是；然后再考虑不符合要求的数目：如不符合要求，则这个数从右往左数的时候，存在一项，在这项右边的-1正好比1多1个.然后从这个数开始，把左边的1变成-1，-1变成1.那么-1的数量就变成了n+1个，1变成了n-1个（不算最右边的那个1）。
类似的，一个由n+1个-1，n-1个1组成的数，由于-1的总数比1多2，所以这些数排列好以后，一定存在某一项，使得其右边的-1正好比1多1。并且这一项左边（包括这项自己）中-1也比1多1.将这一项左边（包括这项自己）中所有数的1变成-1，-1变成1，于是又变成了n个1，n个-1，并且存在一项，在这项右边的-1正好比1多1个的排列。
绕这个圈子是想说明一件事：不符合要求的数目和n+1个-1，n-1个1的排列数是一样的。于是相当于2n个位子选出n+1个放-1结果是.
最终求出的卡特兰数列的通项就是Tn=
这是一个非常重要的数列，通项也不难记，小伙伴们可以小小地记忆一下噢
从刚刚的计算中，小伙伴们也发现了，这个数列可以是这么多不同情境下的计数问题的答案（并且这个数列和课上所讲的“折线法”也有千丝万缕的关系呢，小伙伴们你们发现了么？）。也许对于这个计算你还有疑问或者更好的方法，欢迎带着你的问题继续讨论！