上下框架 网站,怎么做自动跳转网站,上海网络推广团队,六图网引入 今天听学长讲了卡特兰数列后对其有了更深的认识#xff0c;在此完善了一下之前的博客加以总结。 首先用一个经典的例子来描述一下Catalan数列#xff0c;我们有一个1~n的数列和一个大小为n的栈#xff0c;我们有如下两种操作#xff1a; 当未入栈序列不为空时#xf…引入 今天听学长讲了卡特兰数列后对其有了更深的认识在此完善了一下之前的博客加以总结。 首先用一个经典的例子来描述一下Catalan数列我们有一个1~n的数列和一个大小为n的栈我们有如下两种操作 当未入栈序列不为空时使序列的第一个元素入栈。当栈不为空时使栈顶元素出栈。 我们可以显然地发现如果我们选择操作的顺序不同我们最后所形成的出栈序列也不相同那么有多少种出栈序列呢 而这个数列中的Cn就是我们所定义的Catalan数列。 如果我们把所有每一次的操作都写出来可以得到一个关于1和2的操作序列这个序列有以下性质 共有2n项且n项为1n项为2。从左往右1的个数永远不少于2的个数。 定义 通项公式 通项公式推导 方法1数学方法摘自某大老的PPT表示不是很了解在此向各位大佬请教。 即注意他证明过程中的初值是 方法2:组合数证明法 我们设定一个情景假设一个点从A0,0出发走到Bnn我们定义两种走的方法 往右走。往上走。 我们从A走到B一共要走2n步其中n步为1,n步为2这样我们从A走到B的方案也就可以转化为一个1和2的序列了而所有的1和2的序列构成的排列即为从A走到B的方案数 相较之于引言中所提到的序列要使通过这种情景生成的序列是满足Catalan的数列的方案序列我们需要的充要条件是从左往右1的个数永远比2的个数少即向上走过的次数不少于向右走过的次数即所走的路径只存在于紫线的上部而这个条件等价于所形成的路径与绿线没有交点。我们已经知道了所有的方案数我们只需要求出不满足条件的方案数就可以了。 举出一个反例红线我们把这条线与绿线的第一个交点之后的部分都关于绿线对称得到蓝线部分加上前面的部分与之形成的路径构成了一条从A00走向Cn1n-1的路径我们可以发现这样的蓝线有以下三条性质 蓝线只向上走和向右走且重点为Cn1n-1。对于每一条符合性质1的蓝色路径都有且只有一条不合法的红色路径与之对应。对于每一条不合法的红色路径有且只有一条满足性质1的蓝色路径与之对应。 由此我们可以发现不合法的红色路径与满足上述性质的蓝色路径一一对应所以不合法路径数就是蓝色路径数为 所以所有合法的路径数为即Catalan的第n个数为 推论 n个左括号和n个右括号组成的合法括号序列的数量为Catn。1,2···n经过一个栈形成的合法出栈序列的数量为Catn。n个结点构成的不同二叉树的数量为Catn。在平面直角坐标系上每一步只能向右或向上走从0,0走到nn并且除两个端点外不接触直线 y x的路线数量为Catn。 推广在平面直角坐标系上每一步只能向右或上走一步从0,0走到nmn ≥m并且除两个点外不接触直线 y x 的路线的数量为转载于:https://www.cnblogs.com/2020pengxiyue/p/9291476.html
