卡特兰数
(最开始一直搞不清楚卡特兰数到底是什么,公式也不知道是用来算什么的)
后来看懂卡特兰数是通过 求带限制条件的路径条数 这个典型例子,所以这次就从这个例子来说
(图片来源与*)
问题:在n x n的网格里从左下角走到右上角的不经过y = x 这条线的单调路径的条数,即只能向上或向右走
如果没有限制条件,那么就是n步向上,n步向右,所以条数为
加上限制条件后,画图发现所有不合法的路都会经过 y = x + 1 这条线,那么把不合法的方案中第一个经过 y = x + 1 的点为对称点,把之后的路径关于 y = x + 1 对称,画下图就可以发现,原来到(n,n)的路径,现在都是到(n - 1,n + 1),同时可以发现不合法路径与这样的路径是一一对应的
所以不合法的路径条数就是从左下角到(n - 1,n + 1),所以条数为,即
那么合法的路径条数就是
这就是卡特兰数的通项公式了
还有其他的公式
递推公式1:
递推公式2:
典型应用:
1.求带限制条件的路径条数
2.求合法的括号序列的个数
3.出栈次序
4.买票找票问题 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其 它钞票,问有多少种方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元 入栈,持10元者到达视作使栈中某5元出栈)
5.排队问题 现在有 2n 个人,他们身高互不相同,他们要成两排,每一排有 nn 个人,并且满足每一排必须是从矮到高, 且后一排的人要比前一排对应的人要高,问有多少种排法
还有一些没仔细研究的,先记下来
6.凸多边形三角划分 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘 上输入凸多边形的边数n,求不同划分的方案数f(n)
7.给定节点构成二叉搜索树