无处不在的卡特兰数
亲爱的小伙伴们晚上好哟!继昨天的仿射变换之后,今天又是讨论组合数学问题的时候了。今天我们要来看的是一个神奇的数列,为了纪念比利时数学家卡特兰而把它叫做卡特兰(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,那么上面这种排列就成了