avatar

目录
卡特兰数

我又双叒叕碰到卡特兰数啦!

本篇文章说一说我遇到的卡特兰数。

起因

在数据结构的作业中遇到了一道“求出栈序列的个数”的题目,穷举的话会很可怕,想了好久也没弄出来。在网上一查,嗯,确实是递推的问题,只是递推公式比较复杂。我仔细一瞧,嘿!这结果居然是卡特兰数!正巧最近没啥想法,不如趁机整理一下这方面的题目吧 !

卡特兰数的介绍

首先放一张卡特兰数规律的表格。

42
14 42
5 14 28
2 5 9 14
1 2 3 4 5
1 1 1 1 1 1

在对角线上的就是卡特兰数,1、1、2、5、14、42……(第零项第一项都是1)

这个玩意儿是组合数学中的一个经典的数列,很重要,我一个学CS的都已经第二次遇到它了,而且每次都没做出来

递推公式

$$
C_{n+1}=C_0C_n+C_1C_{n-1}+…+C_nC_0
$$

这个是最基本的递推关系,但有些复杂,下面是简化后的版本,但不太容易理解:
$$
C_n=C_n(4*n-2)/(n+1)
$$
解出来的结果是:
$$
C_n=C(2n,n)/(n+1)
$$

卡特兰数的应用

出栈序列的种类

一道数据结构的作业题,好难……

栈结构,后进先出,1到n共n个数进出栈,问有多少种出栈的顺序?

当时题目设置n为6,结果是132,穷举的话很难准确完成。

所以这里面一定有什么规律,或者说一定是有递推关系的。

我们要思考的是如何把“大问题”分解成一个个“小问题”。

  • n=1,1种。
  • n=2,2种;
  • n=3,5种。

从n=4开始,我们可以分析递推关系了。

两个方向:

  • 按照1的出栈位次分类
  • 按照第一个出栈的数分类

我毫不犹豫的选了第二种,然后什么关系也没弄出来。

下面对于n=4按照第一种方法分类:

如果1第一个出来,那么剩余3个数,f(3)。

如果1最后一个出来,那么前三个已经出来了,f(3)。

如果1第二个出来,那么前面那个先出来,f(1),后面还有两个,f(2),所以是f(1)*f(2)。(这里我们可能会忽略f(1)这一个因子,不过如果再分析一下n=5的情况就明白这里应该是f(1)了。)

如果1第三个出来,那么前面f(2),后面f(1)。

再对n=5一分析就能发现规律了!

得到的就是卡特兰数的基本递推公式。

凸多边形分割成三角形

将一个n条边的凸多边形区域分成三角形区域的方法数?

n条边,砍一刀,变成一个i+1条边,一个n-i+1条边。
$$
f(n)=f(3)*f(n-1)+f(4)*f(n-2)+f(5)*f(n-3)+…+f(n-1)*f(3)
$$

节点组成二叉树

给定n个节点,能构成多少种不同的二叉树?

对角线行走路线

想象一张正方形格子地图,从左下角走到右上角,不”穿过“这条对角线的行走方式有多少种?

这个是我刚才突然看到的熟悉的问题。

这应该是我第一次遇到卡特兰数的地方,在我高三做的排列组合题目时遇到的问题,当时在答案解析上看到”卡特兰数“这个名字,就觉得很厉害。

引申:汉克尔矩阵

n=4的汉克尔矩阵

1 1 2 5
1 2 5 14
2 5 14 42
5 14 42 132

无论n取多少,这个矩阵的行列式的值都为1。

进一步,移动一下。

n=4

1 2 5 14
2 5 14 42
5 14 42 132
14 42 132 429

它的行列式的值也是1。

很神奇吧!

卡特兰数的本质探究

Catalan 数出现在很多看似完全不同的计数问题中,证明方法亦有多种不同的角度。比如买票找零问题、格路径问题等多以通项公式证明,二叉树问题、凸多边形三角划分问题等多以递推公式证明等。————《卡特兰数的一种同构证明》上海机电学院 赵小玲

网上有大量的文章整理收集卡特兰数的应用,我就只提了四种,不充当分母了。

这里有一篇论文,卡特兰数的一种同构证明,我“摘录”其中的重要定理作为笔记。

  • 定理

n个+1和n个-1组成的2n项的序列
$$
a_1、a_2、a_3…a_{2n}
$$
若其部分和满足
$$
a_1+a_2+a_3…+a_k>=0
$$
则称之为可接受序列,则次序列的个数等于第n个卡特兰数。

(一针见血的指出了一部分问题的本质!)

格路径问题的证明:

非负整数n,从(0,0)到(n,n)的下对角线矩形格路径的条数等于第n个卡特兰数。

把向上设为+1,向右设为-1,于是问题巧妙转化为可接受序列的问题了。

借书还书问题:

图书馆排队,n人还同一本书,n人都要借同样的同一本书,整个过程图书馆没有缺书,问排队方式的种类?

还书+1,借书-1,于是问题又巧妙地……

进栈出栈问题:

进栈+1,出栈-1,出栈顺序等价于可接受序列的种类。

卖东西找零问题:

阿里有道题目,一个商品5元,8个人分别拿5元来买,又有8个人分别拿10元买1个,如果不出现无法找零的情况,有多少种排队方式?

别看5和10不相等,其实本质还是一样的。

5元就是+1,10元就要找零,就是-1。

所以这里也是同样的思路。

最后

看似毫不相关的几个问题,居然都指向了卡特兰数,数学是如此奇妙!

但深入讨论后不难发现,卡特兰数问题的本质便是“可接受序列的种类”的问题。

不要强行记忆那么多应用,而要找到本质,共同点,然后才能解决新问题。

最后,感谢这篇论文的作者,让我更加深入的理解卡特兰数。

打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论