一分钟数学——卡特兰数(中)

 

卡特兰数这次我们主要讲上期的解答(点击此处→→卡特兰数←←查看上期图文内容)。切割三角形把一个凸六边形分割成...

卡特兰数
这次我们主要讲上期的解答(点击此处→→卡特兰数←←查看上期图文内容)。

把一个凸六边形分割成若干个的三角形(必须全都是三角形),一共有几种方法?如果是凸N边形呢?
下图是将正六边形切割成若干个三角形的全部方法


卡特兰数是有递归(←←点此查看 一分钟算法——递归 的内容)的思想的,将凸六边形的六个点都标上编号V1到V6,随后我们要以V1和V6为三角形的底边找出另外一个顶点Vk,来组成一个三角形。这个k是从2到5的,每一种对应的就是左半部分和右半部分分别的情况数,这同样都是凸多边形,所以可以是递归。把左右两边的情况数相乘,因为是乘法原理,就可以得到k的一个结果,将所有k的结果相加即可。设F(N)为凸N边形分割成三角形的情况数,列出的递归关系式就是:F(N)=F(0)*F(N-1)+F(1)*F(N-2)+……+F(N-1)*F(0)。

那么对于其它三道题来说,都是同一种类型的,就是走网格(也就是第四题)。买水的可以看作在每个时刻,有一元钱的必须不少于有两元钱的。添括号的同样,就是左括号和右括号而已。
下图是5×5的网格的最短路径(不超过对角线)的所有情况
那如何计算总方案数呢?如上图,把它看作是在一个坐标系上的,从(0,0)点到(N,N)点。画出对角线(直线y=x,表示x轴上的坐标和y轴上的坐标相等),思路就是用总的方案数(无限制条件)减去超过对角线的。总方案数就是一共走2N条边,其中N条向上,N条向右,就是从2N中选N个。如果超过对角线,设为到达点P,然后观察一下每一个过对角线一格(同点P一样)的点,发现它们都在直线y=x+1上。这样就可以把超出对角线的路径沿直线y=x+1进行映射,得到一条新的路径,是从A'(-1,1)到B(N,N)。而我们发现,任何一条从A'(-1,1)到B(N,N)的路径必然都会经过直线y=x+1,也就可以得到一条映射回去的过直线y=x的路径。来求从A'(-1,1)到B(N,N)的路径数,也是2N条边,不过是N-1条向上的,N+1条向右的,因此是从2N里选N-1,或是2N里选N+1。总数就是C(2N,N)-C(2N,N-1)。这种问题也称为Dyck Path,其实这个最短路径的最终结果和之前的递归结果是相同的,只是推导过程很复杂,这里就不细说了。

再说说二叉树(←←点击查看 一分钟算法——二叉树 的内容)吧,有N个点,分布在二叉树上,问有多少种不同的放法?(不规定是完全二叉树)也是和卡特兰数有关的哦,想想上述几个例子到底为什么和卡特兰数有关呢?这是一个怎样的序列呢?敬请期待下期!
如果想了解本文中引用到的、我以前的文章,请点击以下链接:
一分钟数学——卡特兰数(上)
一分钟算法——递归
一分钟算法——二叉树



    关注 无忧公主的数学时间


微信扫一扫关注公众号

0 个评论

要回复文章请先登录注册

卡特兰数 相关文章