成都科技网站建设电话多少,人力资源公司经营范围有哪些,做网站需要哪些东西和步骤,ps教程自学网新手教程详细步骤卡特兰数的引入与n边形分成三角形的个数有关#xff1a;
我们令f[n]表示n边形可以分成的三角形的个数#xff0c;特殊的#xff0c;令f[2]1
我们考虑以顶点1顶点的一个三角形#xff0c;假设用的是n边形的k-k1边#xff0c;那么这种情况的方案数就是f[k]∗f[n−k1]f[k]*…卡特兰数的引入与n边形分成三角形的个数有关
我们令f[n]表示n边形可以分成的三角形的个数特殊的令f[2]1
我们考虑以顶点1顶点的一个三角形假设用的是n边形的k-k1边那么这种情况的方案数就是f[k]∗f[n−k1]f[k]*f[n-k1]f[k]∗f[n−k1]这个边可以变化从1-2到n-1-n所以f[n]f[2]∗f[n−1]f[3]∗f[n−2]...f[n−1]∗f[2]f[n]f[2] *f[n-1]f[3] *f[n-2]...f[n-1]*f[2]f[n]f[2]∗f[n−1]f[3]∗f[n−2]...f[n−1]∗f[2]我们考虑从某个顶点发出的对角线将这个n边形分成两部分考虑这种情况下共有f[3]∗f[n−1]f[4]∗f[n−1]...f[n−1]∗f[3]f[3]*f[n-1]f[4]*f[n-1]...f[n-1]*f[3]f[3]∗f[n−1]f[4]∗f[n−1]...f[n−1]∗f[3]种情况共有n个顶点所以还要乘上n,可是这样显然重复的很多的情况。考虑每种情况共有n-3条对角线每个对角线的两个顶点都会计算一次这样的情况所以最后还要除以2*(n-3)
这样我们就得到了两个递推式: 1.f[n]f[2]∗f[n−1]f[3]∗f[n−2]...f[n−1]∗f[2]1.f[n]f[2]*f[n-1]f[3]*f[n-2]...f[n-1]*f[2]1.f[n]f[2]∗f[n−1]f[3]∗f[n−2]...f[n−1]∗f[2] 2.f[n]n∗f[3]∗f[n−1]f[4]∗f[n−2]...f[n−1]∗f[3]/(2∗n−6)2.f[n]n*f[3]*f[n-1]f[4]*f[n-2]...f[n-1]*f[3]/(2*n-6)2.f[n]n∗f[3]∗f[n−1]f[4]∗f[n−2]...f[n−1]∗f[3]/(2∗n−6) 我们将一式往前递推一项再结合二式就可以得到递推式 f[n1]f[2]∗f[n]f[3]∗f[n−1]...f[n]∗f[2]2∗f[2]∗f[n](2∗n−6)/n∗f[n](4∗n−6)∗f[n]f[n1]f[2]*f[n]f[3]*f[n-1]...f[n]*f[2]2*f[2]*f[n](2*n-6)/n*f[n](4*n-6)*f[n]f[n1]f[2]∗f[n]f[3]∗f[n−1]...f[n]∗f[2]2∗f[2]∗f[n](2∗n−6)/n∗f[n](4∗n−6)∗f[n] 这样我们就能递推的求解卡特兰数。
将这个数字的应用推广这类数字的根本是第一个递推式我们不妨从0开始算起忽略卡特兰数的几何意义仅仅当作一个特殊的递推公式
f[n]f[0]∗f[n−1]f[1]∗f[n−2]...f[n−1]∗f[0]其中f[0]1f[n]f[0]*f[n-1]f[1]*f[n-2]...f[n-1]*f[0]其中f[0]1f[n]f[0]∗f[n−1]f[1]∗f[n−2]...f[n−1]∗f[0]其中f[0]1
即所有满足这种关系的数字都是卡特兰数在这种定义下我们同样可以求得递推式
f[n](4∗n−2)/(n1)∗f[n−1]f[n](4*n-2)/(n1)*f[n-1]f[n](4∗n−2)/(n1)∗f[n−1]结合上面的推法应该可以推出来但是我还没有尝试f[n]C(n,2n)/n1C(n,2n)−C(n−1,2n)f[n]C(n,2n)/n1C(n,2n)-C(n-1,2n)f[n]C(n,2n)/n1C(n,2n)−C(n−1,2n)
应用只要符合上面那种递推式的都是卡特兰数
已知一颗二叉树有n个结点问该二叉树能组成多少种不同的形态 问题的关键是找到递推式我们要想办法将问题转换成子问题对于这个问题我们就可以思考左子树和右子树不同的问题有不同的结构我们要分析问题的模式找到将问题分解的方法。我们用f[n]表示n个节点的数可以形成多少子树不难想到f[n]满足上面的递推式是卡特兰数有n个A和n个B排成一排从第1个位置开始到任何位置B的个数不能超过A的个数问这样的排列有多少种 分析一下问题关键是B的个数不能超过A的个数所以一旦前2*k个位置中A和B相等对后面就不会产生影响相当与后面2 *n-2 *k个位置是独立的可以重新进行思考。
