帐前卒专栏

Without software, we are nothing.

吊死在catalan树上

Hi all,I should write this article in Chinese. Because there are many special Math words here. Maybe I will translate this article later.

首先是啥米叫[[catalan]]数,h(n) = h(0)h(n-1)+ h(1)h(n-2)+….+h(n-2)h(1)+h(n-1)h(0) ,h(0) = h(1) = 1通项公式为$latex h(n) = \frac{1}{n+1}{C{2n}}{n} $另外还有h(n) = h(1)h(n-1)+h(2)h(n-2)+…+h(n-2)h(2)+h(n-1)*h(1),h(1) = 1其通项公式为$latex h(n) = \frac{1}{n}{C{2n-2}}{n-1} $

首先是括号问题,很多问题都能转换为括号匹配问题,即在任何位置,左括号的数目都要大于等于右括号的数目。然后问你给n个左括号和n个右括号,共有多少种放置方法。分析方法转载:http://blog.csdn.net/dlyme/archive/2008/06/10/2532831.aspx具体解法为:

分析:把左括号看作0,将右括号看作1,n个1和n个0组成的2n 位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1 和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。在2n位二进制数中填入n个1的方案数为c(2n,n),不 填 1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计 数)的方案数即为所求。不符合要求的数的特征是 由左 而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有 n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的 2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。反过来,任何一个由n+1个0和n-1个1组成的2n位 二 进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累 计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。显然,不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。

当然也可以看作第一对括号出现在什么位置,如果出现在1,2位置,则为h(0)h(2n-2),出现在3,4位置为h(2)h(2n-4),当然这里不可能出现在2,3位置,否则,左边h(1)是错误状态,不可以再递归做下去。所以原方程为h(n) = h(0)h(2n-2)+h(2)h(2n-4)+…+h(2n-4)h(2)+h(2n-2)h(0),这里将h(n)->f(n/2),即 h(n) = f(0)f(n-1)+f(1)h(n-2)+… = $latex \frac{1}{n+1}{n}} $

另外矩阵连乘,出入栈,人过街区问题和这个解法类似。

  1. 矩阵连乘即a1*a2*a3…*an这样的矩阵加括号表示成对共有多少种方法。首先可以选取某个矩阵作为起始矩阵,在这个矩阵上加括号,例如a2为起始矩阵,然后就变为 a1*(a2)*a3…然后如果a2与a3相乘则a1*((a2)*a3)…看出来括号是否和刚才那个左右括号匹配的问题一样?所以这里共有2n个括号,然后求放置正确括号位置的种类有多少。因为最初的一对括号无用,所以这里其实有2n-2个括号,结果秒杀为$latex \frac{1}{n}^{n-1}} $ 其实就是g(n)=f(2n-2)=h(n-1),带入即可。
  2. 下面是问n个数出入栈,共有多少种出入栈的方式?进栈看作左括号,出栈看作右括号,然后瞬间变为左右括号匹配问题。结果依旧是$latex \frac{1}{n+1}^{n}} $ 因为第一个括号对就决定了结果的顺序,所以是2n个括号,这个与问题1有所不同。
  3. 然后是人过2n个街区工作,看作方格子,即左右走向n个街区,南北走向n个街区,但是这个家伙不会穿越但是可以碰到家到办公室的对角线,问有多少种可能的道路走法。这里因为没有通过对角线,所以走了k个左右走向的街区,最多只能再走k个南北走向的街区,否则就会穿越对角线。所以可以看作是栈问题,塞进去k个数只能弹出k个数。所以结果同2.
  4. 凸多边形区域划分三角形的方法数有多少?划分的三角形不能重叠(除三边可以重叠外)。首先选一条基边(因为划分必然要用到基边),一个顶点。图1中选中一条基边,一个顶点后,左边剩余1条基边(红色),右边剩余n-2条;图二中左边剩余两条基边,右边剩余n-3条。其中n为凸多边形顶点数。则有f(n) = f(1)*f(n-2)+f(2)*f(n-3)+….+f(n-2)*f(1)。
  5. 圆上选择2n个点,将这些点对连接起来,且所得n条线段不相交,求可行方法数。首先选择两个点,左边剩余0个点,右边剩余2n-2个点继续这样连接。下一次选择,左边剩余两个点,右边剩余2n-4继续选择..f(2n) = f(0)*f(2n-2)+f(2)*f(2n-4)+…, 令f(2n) = h(n), f(2n) = h(0)*h(n-1)+h(1)*h(n-2)+…=$latex \frac{1}{n+1}C(2n,n) $.
  6. n个节点构造多少种不同的二叉树。这个问题可以转换为括号问题,与连乘不同的是,它的第一对括号决定了它的树根。当选择一个节点,左边可以有0个,右边有n-1个;左边有1个,右边n-2个….所以g(n) = f(2n) = h(n) =$latex \frac{1}{n+1}C(2n,n) $.

下面转载冷笑话:

从前有棵树,叫高数,树上挂了很多人 很久很久以前,在拉格朗日照耀下,有几座城:分别是常微分方城和偏微分方城这两座兄弟城,还有数理方程、随机过城。从这几座城里流出了几条溪,比较著名的 有:柯溪、数学分溪、泛函分溪、回归分溪、时间序列分溪等。其中某几条溪和支流汇聚在一起,形成了解析几河、微分几河、黎曼几河三条大河。 河边有座古老的海森堡,里面生活着亥霍母子,穿着德布罗衣、卢瑟服、门捷列服,这样就不会被开尔蚊骚扰,被河里的薛定鳄咬伤。城堡门口两边摆放着牛墩和道 尔墩,出去便是鲍林。鲍林里面的树非常多:有高等代树、抽象代树、线性代树、实变函树、复变函树、数值代树等,还有长满了傅立叶,开满了范德花的级 树…人们专门在这些树边放了许多的盖(概)桶,高桶,这是用来放尸体的,因为,挂在上面的人,太多了,太多了… 这些人死后就葬在微积坟,坟的后面是一片广阔的麦克劳林,林子里有一只费马,它喜欢在柯溪喝水,溪里撒着用高丝做成的ε-网,有时可以捕捉到二次剩鱼。 后来,芬斯勒几河改道,几河不能同调,工程师李群不得不微分流形,调河分溪。几河分溪以后,水量大涨,建了个测渡也没有效果,还是挂了很多人,连非交换代 树都挂满了,不得不弄到动力系桶里扔掉。 有些人不想挂在树上,索性投入了数值逼井(近)。结果投井的人发现井下生活着线性回龟和非线性回龟两种龟:前一种最为常见的是简单线性回龟和多元线性回 龟,它们都喜欢吃最小二橙。 柯溪经过不等市,渐近县和极县,这里房子的屋顶都是用伽罗瓦盖的,人们的主食是无穷小粮。 极县旁有一座道观叫线性无观,线性无观里有很多道士叫做多项士,道长比较二,也叫二项士。线性无观旁有一座庙叫做香寺,长老叫做满志,排出咀阵,守卫着一 座塔方。一天二项士拎着马尔可夫链来踢馆,满志曰:“正定!正定!吾级数太低,愿以郑太求和,道友合同否?”二项士惊呼:“特真值啊!”立退。不料满志此 人置信度太低,不以郑太求和,却要郑太回归。二项式大怒在密度函树下展开标准分布,布里包了两个钗钗,分别是标准钗和方钗。满志见状央(鞅)求饶命。二项 式将其关到希尔伯特空间,命巴纳赫看守。后来,巴纳赫让其付饭钱,满志念已缴钱便贪多吃,结果在无参树下被噎死(贝叶斯)。

Comments