外星人源码论坛 首页 编程经验 卡特兰数与算法

卡特兰数与算法

2018-3-5 06:34
原作者: 外星人源码网 来自: 外星人源码网 收藏 分享 邀请

1. 来源:LeetCode 96 - Unique Binary Search Trees Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example,

1. 来源:LeetCode 96 - Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

2. 分析

假设有$n$个node,排序后的序列为($x_1, x_2, \dots, x_n$)。假设其可构造成$f(n)$个不同的BST。

若$n=0$,唯一解为空树,即$f(0)=1$

若$n>0$,一共有n种情况:

选$x_1$做root,使其左子树为空,右子树为剩下$n-1$个node的构造BST,问题转换为$n-1$个node的构造BST有多少个解,即$f(1)=f(0) f(n-1)$; 选$x_2$做root,使其左子树为$x_1$,右子树为剩下$n-2$个node的构造BST,问题转换为$n-1$个node的构造BST有多少个解,即$f(2)=f(1)f(n-2)$; 选$x_k(1\leq k \leq n)$做root,其左子树共有$f(k-1)$种可能,右子树有$f(n-k)$种可能,即$f(k)=f(k-1)f(n-k),(k > 0)$。

由此得到

$$ f(n) = \begin{cases} 1, & n=0 \\ f(0)f(n-1) + \dots + f(n-1)f(0) = \sum_{k=1}^n f(k-1)f(n-k), & n>0 \end{cases} \tag{1} $$

3. 递推公式

令生成函数

$$ \begin{equation} \begin{split} g(x)&= \sum_{k=1}^{\infty}f(k-1)x^k\\ &=f(0)x + f(1)x^2 + f(2)x^3 + \dots + f(n-1)x^n + \dots \end{split} \tag{2} \end{equation} $$

$$ \begin{split} [g(x)]^2 &= f^2(0)x^2 \\ &+ [f(0)f(1) + f(1)f(0)]x^3 \\ &+ [f(0)f(2) + f^2(1) + f(2)f(0)]x^4 \\ &+ \dots \\ &+ [f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)]x^n \\ &+ \dots \end{split} $$

代入$f(0) = 1$,$f(1) = 1$和$f(n)$的递推公式,得到

$$ \begin{equation} \begin{split} [g(x)]^2 &= x^2 + f_2x^3 + f_3x^4 + ... + f_{n-1}x^n \\ &= g(x) - x \end{split} \tag{3} \end{equation} $$

解这个方程,其两个根为

$$ g_1(x)=\frac{1 + \sqrt{1-4x}}{2}, g_2(x)=\frac{1 - \sqrt{1-4x}}{2} $$

由于$g(0)=0$,验证得仅$g_2(x)$成立,所以

$$ g(x)=g_2(x)=\frac{1}{2} - \frac{1}{2}(1-4x)^{\frac{1}{2}} \tag{4} $$

4. 牛顿二项式展开

根据牛顿二项式定理

$$ (x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k},其中\binom{n}{k}=\frac{n!}{k!(n-k)!} \tag{5} $$

当$n$不是正整数时, $k$无法正好求和到$n$, 因此将一直求和至正无穷, 这样形式上就得到了广义二项式定理:

$$ (x+y)^{\alpha} = \sum_{k=0}^{\infty}\binom{\alpha}{k}x^{\alpha-k}y^k \tag{6} $$

其中

$$ \binom{\alpha}{k}=\frac{\alpha(\alpha-1)\dots(\alpha-k+1)}{k!} \tag{7} $$

是形式上的组合数。实际上广义二项式定理并非总是成立, 因为等式右边不一定收敛。

其常见形式为

$$ \begin{equation} \begin{split} (1+z)^{\alpha} &= \sum_{k=0}^{\infty}\binom{\alpha}{k}z^{k} \\ & = 1+ \sum_{k=1}^{\infty}\binom{\alpha}{k}z^{k}, (|z|<1) \end{split} \tag{8} \end{equation} $$

现考察$\alpha=\frac{1}{2}$的情况,有

$$ \begin{equation} \begin{split} \binom{\alpha}{k}&=\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\dots(\frac{1}{2}-k+1)}{k!} \\ & = \frac{(-1)^{k-1}}{2^k}\frac{1 \times 3 \times 5 \times \dots \times (2k-3)}{k!} \\ & = \frac{(-1)^{k-1}}{2^k}\frac{1 \times 2 \times 3 \times \dots \times(2k-3) \times (2k-2)}{2 \times 4 \times \dots \times (2k-2) \times k! } \\ & = \frac{(-1)^{k-1}}{2^k}\frac{(2k-2)!}{2^{k-1}(k-1)!k!} \\ & = \frac{(-1)^{k-1}}{k \times 2^{2k-1}} \frac{(2k-2)!}{[(k-1)!]^2} \\ & = \frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}, (k > 0) \end{split} \tag{9} \end{equation} $$

因此,

$$ (1+z)^{\alpha} = 1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}z^{k}, (|z|<1) \tag{10} $$

5. 回到$g(x)$

令上式中的$z=-4x$,即得到

$$ \begin{equation} \begin{split} g(x)&=\frac{1}{2} - \frac{1}{2}(1-4x)^{1/2} \\ &=\frac{1}{2}-\frac{1}{2}[1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k \times 2^{2k-1}} \binom{2k-2}{k-1}(-4x)^{k}] \\ &=\sum_{k=1}^{\infty}\frac{1}{k}\binom{2k-2}{k-1}x^k, (|x|<\frac{1}{4}) \end{split} \tag{11} \end{equation} $$

又因为按照定义$g(x)= \sum_{k=1}^{\infty}f(k-1)x^k$,所以

$$ \begin{equation} \begin{split} f(n-1)&=\frac{1}{n}\binom{2n-2}{n-1}, n>1 \end{split} \end{equation} $$

或写为

$$ \begin{equation} \begin{split} f(n)&=\frac{1}{n+1}\binom{2n}{n}, n>0 \end{split} \tag{12} \end{equation} $$

此即卡特兰数(Catalan Number)的通项公式。递归计算时可采用

$$ f(n+1) = \frac{2(2n+1)}{n+2}f(n) \tag{13} $$

6. 卡特兰数的应用

括号化问题。矩阵链乘: $P=A1×A2×A3×\dots×An$,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数?类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

出栈次序问题。

一个栈(无穷大)的进栈序列为1,2,3,...,n,有多少个不同的出栈序列? 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈) 一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

粉丝 阅读70 回复0
上一篇:
Web前端开发代码规范(基础)发布时间:2018-03-05
下一篇:
使用Node.js开发一个小爬虫发布时间:2018-03-05
推荐资讯
阅读排行
国内最专业的源码技术交流社区
全国免费热线电话

0373-5171417

周一至周日9:00-23:00

反馈建议

admin@eenot.com 在线QQ咨询

扫描二维码关注我们