卡特兰数

内容纲要

卡特兰数是组合数学中非常有趣且引用广泛的数列,其延伸问题可以应用于各种奇怪的组合问题上

我们用一个实例来引入卡特兰数

file

在如图的坐标网格中,规定我们在任意一点(x, y)只能向右或者向上移动,则我们从A点(0, 0)走到B点(5, 5)的路径中,不跨过红色对角线(即不触碰绿线)的走法有多少种?

我们抛去限制,如果在一个如图的网格中,从A到B的走法种类应该是

10 \choose 5

分析不难发现,一共需要走十步,其中五步向上,五步向右
这是一个排列问题,我们只需让这十步中任意五步向上,剩余的五步便可向右,所以走法种类有10选5种

当我们加入了红色对角线,方案数就被削减了一部分,我们希望求出被削减的那一部分方案数,则可以通过他间接求出符合题目要求的剩余方案数

画出绿色线后,我们得到了B(5, 5)关于不可触摸的绿线的对称点B’(4, 6)

此时对于任意一条非法的红色路径,我们可以将路径触摸绿色线后的部分关于绿线做轴对称,得到蓝色路径

根据对称关系,我们不难得知任意一条非法到达B点的路径都可以找到对应一条到达B’的蓝色路径。也就是说,非法到达B点的路径和到达B’点的路径是一一对应的,所以两者个数相同

此时到达B点的合法路径数自然是所有路径减去非法路径

{10 \choose 5} - {10 \choose 4}

上式经过简单化简可以得到

{2n \choose n} \cdot \frac{1}{n + 1}

在上例中,n = 5

订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论