卡特兰数是组合数学中非常有趣且引用广泛的数列，其延伸问题可以应用于各种奇怪的组合问题上
我们用一个实例来引入卡特兰数
在如图的坐标网格中，规定我们在任意一点(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