数学-Catalan数¶
参考《组合数学》布鲁迪的第八章——特殊计数序列
n个1和n个-1构成的2n项： $$ a_{1}, a_{2}, \cdots, a_{2 n} $$ 其部分和满足： $$ a_{1}+a_{2}+\cdots+a_{k} \geqslant 0, \quad(k=1,2, \cdots, 2 n) $$ 的数列的个数等于第n个Catalan数： $$ C_{n}=\frac{1}{n+1}\left(\begin{array}{l}{2 n} \ {n}\end{array}\right) \quad(n \geqslant 0) $$ 证明：
问题可以划分为两个部分，即满足（2）要求的序列（可接受的）和不满足（2）的序列（不可接受的）。设可接受的序列个数为A_n，不可接受的序列个数为U_n。显然A_n + U_n = C_{2n}^n。不妨尝试去求U_n的值。
考虑所有不可接受的序列中的任何一个，对于这个序列本身，我们可以找到下标k_1, k_2, k_3,\cdots，使部分和小于0，令k是此下表序列中最小的一个，我们可以得到两点性质： $$ a_{1}+a_{2}+\dots+a_{k-1}=0 \ a_k = -1 $$ 如果1的数量大于-1，若1的数量比-1的数量多1，则无论a_k取何值都将满足性质要求，与k使部分和不满足要求矛盾。
如果1的数量比-1的数量少1，则前k-1项就不满足性质，也就是说k并不是不满足性质的下标中最小的，与假设条件矛盾。所以数量只能相等。
把前k项中的每一项的符号都反过来，剩余保持不变。
给定（n+1）个+1和（n-1）个-1的序列，当+1的个数超过-1的个数的时候就存在第一个实例（因为+1的个数多于-1的个数）。把+1和-1符号倒过来，结果就得到n个+1和n个-1的不可接受的序列。这样，有多少（n+1）个+l和（n-l）个-1的序列就有多少个不可接受序列。具有（n+1）个+1和（n-1）个-1的序列的个数是具有一种类型的n+1个元素和另一种类型的n-1个元素的两种类型的元素排列。 $$ U_n = \frac{(2 n) !}{(n+1) !(n-1) !} \ \begin{aligned} A_{n} &=\frac{(2 n) !}{n ! n !}-\frac{(2 n) !}{(n+1) !(n-1) !} \ &=\frac{(2 n) !}{n !(n-1) !}\left(\frac{1}{n}-\frac{1}{n+1}\right) \ &=\frac{(2 n) !}{n !(n-1) !}\left(\frac{1}{n(n+1)}\right) \ &=\frac{1}{n+1}\left(\begin{array}{c}{2 n} \ {n}\end{array}\right) \end{aligned} $$ 定义拟-Catalan数： $$ C_{n}^{}=n ! C_{n-1} \ \begin{array}{l}{=n ! \frac{4 n-6}{n} C_{n-2}} \ {=(4 n-6)(n-1) ! C_{n-2}} \ {=(4 n-6) C_{n-1}}\end{array} \ \begin{array}{l}{C_{n}^{}=(4 n-6) C_{n-1}^{} \quad(n \geqslant 2)} \ {C_{1}^{}=1}\end{array} $$
典型例子¶
- 有2n个人排成一行进入剧场。人场费50美分。2n个人中的n个人有50分一个的分币，n个人有一美元的纸币，剧院售票处相当草率地用一个空的现金收录机开始售票。有多少种列队方法使得只要有1美元的人买票，售票处就有50分币找零？
如果人看成不可区分的，那么就是Catalan数，如果看成可区分的，则：
$$
(n !)(n !) \frac{1}{n+1}\left(\begin{array}{c}{2 n} \ {n}\end{array}\right)=\frac{(2 n) !}{n+1}
$$
- 区分在对角线的左上方还是右下方，结果使Catalan数的两倍。
- 矩阵链乘： P=a_1×a_2×a_3×……×a_n，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
- 出栈次序问题。 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
类似： (1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) (2)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。 5. 多边行划分为三角形问题。 将一个凸多边形区域分成三角形区域的方法数?
类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 6. .给顶节点组成二叉树的问题。 给定N个节点，能构成多少种形状不同的二叉树？ 先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)* h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)（能构成h(N)个）
https://blog.csdn.net/wu_tongtong/article/details/78161211
典型题目：
- Leetcode 96 Unique Binary Search Tree