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(n1)+h(1)h(n2)+....+h(n2)h(1)+h(n1)h(0),h(0)=h(1)=1h(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

通项公式为

h(n)=1n+1(2nn)h(n)=\frac{1}{n+1}{\binom{2n}{n}}

另外还有

h(n)=h(1)h(n1)+h(2)h(n2)+...+h(n2)h(2)+h(n1)h(1),h(1)=1h(n)=h(1)h(n-1)+h(2)h(n-2)\\+...\\+h(n-2)h(2)+h(n-1)h(1),\\h(1)=1

其通项公式为

h(n)=1n(2n2n1)h(n)=\frac{1}{n}{\binom{2n-2}{n-1}}

首先是括号问题,很多问题都能转换为括号匹配问题,即在任何位置,左括号的数目都要大于等于右括号的数目。然后问你给n个左括号和n个右括号,共有多少种放置方法。具体解法为:

分析:

把左括号看作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)。由此得出

输出序列的总数目=

(2nn)(2nn+1)=n+11(2nn){\binom{2n}{n}}-{\binom{2n}{n+1}}=\frac{n+1}{1}{\binom{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(2n2)+h(2)h(2n4)+...+h(2n4)h(2)+h(2n2)h(0)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(n1)+f(1)f(n2)+...=1n+1(2nn)h(n)=f(0)f(n-1)+f(1)f(n-2)+...\\=\frac{1}{n+1}{\binom{2n}{n}}

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

  1. 矩阵连乘即a1*a2*a3...*an这样的矩阵加括号表示成对共有多少种方法。首先可以选取某个矩阵作为起始矩阵,在这个矩阵上加括号,例如a2为起始矩阵,然后就变为a1(a2)a3...。然后如果a2与a3相乘则a1((a2)a3)...。看出来括号是否和刚才那个左右括号匹配的问题一样?所以这里共有2n个括号,然后求放置正确括号位置的种类有多少。因为最初的一对括号无用,所以这里其实有2n-2个括号,立即得到结果为:

1n(2n2n1)\frac{1}{n}{\binom{2n-2}{n-1}}

其实就是

g(n)=f(2n2)=h(n1)g(n)=f(2n-2)=h(n-1)

带入即可。

  1. 下面是问n个数出入栈,共有多少种出入栈的方式?进栈看作左括号,出栈看作右括号,然后瞬间变为左右括号匹配问题。结果依旧是

1n+1(2nn)\frac{1}{n+1}{\binom{2n}{n}}

因为第一个括号对就决定了结果的顺序,所以是2n个括号,这个与问题1有所不同。

  1. 然后是人过2n个街区工作,看作方格子,即左右走向n个街区,南北走向n个街区,但是这个家伙不会穿越但是可以碰到家到办公室的对角线,问有多少种可能的道路走法。这里因为没有通过对角线,所以走了k个左右走向的街区,最多只能再走k个南北走向的街区,否则就会穿越对角线。所以可以看作是栈问题,塞进去k个数只能弹出k个数。所以结果同2.
  2. 凸多边形区域划分三角形的方法数有多少?划分的三角形不能重叠(除三边可以重叠外)。首先选一条基边(因为划分必然要用到基边),一个顶点。图1中选中一条基边,一个顶点后,左边剩余1条基边(红色),右边剩余n-2条;图二中左边剩余两条基边,右边剩余n-3条。其中n为凸多边形顶点数。则有

f(n)=f(1)f(n2)+f(2)f(n3)+....+f(n2)f(1)f(n)=f(1)f(n-2)+f(2)f(n-3)\\+....\\+f(n-2)f(1)

  1. 圆上选择2n个点,将这些点对连接起来,且所得n条线段不相交,求可行方法数。首先选择两个点,左边剩余0个点,右边剩余2n-2个点继续这样连接。下一次选择,左边剩余两个点,右边剩余2n-4继续选择…

f(2n)=f(0)f(2n2)+f(2)f(2n4)+...f(2n)=f(0)f(2n-2)+f(2)f(2n-4)+...

f(2n)=h(n)f(2n)=h(n)

f(2n)=h(0)h(n1)+h(1)h(n2)+...=1n+1(2nn)f(2n)=h(0)h(n-1)+h(1)h(n-2)+...\\=\frac{1}{n+1}{\binom{2n}{n}}

  1. n个节点构造多少种不同的二叉树。这个问题可以转换为括号问题,与连乘不同的是,它的第一对括号决定了它的树根。当选择一个节点,左边可以有0个,右边有n-1个;左边有1个,右边n-2个…所以

g(n)=f(2n)=h(n)=1n+1(2nn)g(n)=f(2n)=h(n)=\frac{1}{n+1}{\binom{2n}{n}}

下面转载冷笑话:

从前有棵树,叫高数,树上挂了很多人
很久很久以前,在拉格朗日照耀下,有几座城:分别是常微分方城和偏微分方城这两座兄弟城,还有数理方程、随机过城。从这几座城里流出了几条溪,比较著名的 有:柯溪、数学分溪、泛函分溪、回归分溪、时间序列分溪等。其中某几条溪和支流汇聚在一起,形成了解析几河、微分几河、黎曼几河三条大河。

河边有座古老的海森堡,里面生活着亥霍母子,穿着德布罗衣、卢瑟服、门捷列服,这样就不会被开尔蚊骚扰,被河里的薛定鳄咬伤。城堡门口两边摆放着牛墩和道 尔墩,出去便是鲍林。鲍林里面的树非常多:有高等代树、抽象代树、线性代树、实变函树、复变函树、数值代树等,还有长满了傅立叶,开满了范德花的级 树…人们专门在这些树边放了许多的盖(概)桶,高桶,这是用来放尸体的,因为,挂在上面的人,太多了,太多了…

这些人死后就葬在微积坟,坟的后面是一片广阔的麦克劳林,林子里有一只费马,它喜欢在柯溪喝水,溪里撒着用高丝做成的ε-网,有时可以捕捉到二次剩鱼。
后来,芬斯勒几河改道,几河不能同调,工程师李群不得不微分流形,调河分溪。几河分溪以后,水量大涨,建了个测渡也没有效果,还是挂了很多人,连非交换代树都挂满了,不得不弄到动力系桶里扔掉。
有些人不想挂在树上,索性投入了数值逼井(近)。结果投井的人发现井下生活着线性回龟和非线性回龟两种龟:前一种最为常见的是简单线性回龟和多元线性回龟,它们都喜欢吃最小二橙。

柯溪经过不等市,渐近县和极县,这里房子的屋顶都是用伽罗瓦盖的,人们的主食是无穷小粮。

极县旁有一座道观叫线性无观,线性无观里有很多道士叫做多项士,道长比较二,也叫二项士。线性无观旁有一座庙叫做香寺,长老叫做满志,排出咀阵,守卫着一座塔方。一天二项士拎着马尔可夫链来踢馆,满志曰:“正定!正定!吾级数太低,愿以郑太求和,道友合同否?”二项士惊呼:“特真值啊!”立退。不料满志此人置信度太低,不以郑太求和,却要郑太回归。二项式大怒在密度函树下展开标准分布,布里包了两个钗钗,分别是标准钗和方钗。满志见状央(鞅)求饶命。二项式将其关到希尔伯特空间,命巴纳赫看守。后来,巴纳赫让其付饭钱,满志念已缴钱便贪多吃,结果在无参树下被噎死(贝叶斯)。