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$$

通项公式为

$$h(n)=\frac{1}{n+1}{\binom{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$$

其通项公式为

$$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)。由此得出

输出序列的总数目=

$${\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(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)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个括号，立即得到结果为：

$$\frac{1}{n}{\binom{2n-2}{n-1}}$$

其实就是

$$g(n)=f(2n-2)=h(n-1)$$

带入即可。

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

$$\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(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(2n-2)+f(2)f(2n-4)+...$$

令

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

则

$$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)=\frac{1}{n+1}{\binom{2n}{n}}$$

下面转载冷笑话：

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

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

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

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

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