2021-08-26 19:57 已编辑湖南大学 golang

关注

Catalan（卡特兰数）

Catalan（卡特兰数）证明

一、模型1证明

思路：直接用排列组合，强行证明

假设有n对左右括号,请求出合法的排列有多少个?
合法是指每一个括号都可以找到与之配对的括号,比如
n=1时,()是合法的,但是)(为不合法。

1）求总排列数

左括号数量为n ,右括号数量为n ,总排列数为 $C_{2n}^{n}$
解释1）因为每个(或)都是一样的，所以，我们只需要从2n个位置找出n个位置，放上(，其他的就只有一种情况，那就是全放上）
解释2）我们可以用高中排列组合来解释，我们假设每个(或)都不相同，我们先全排列 $A_{2n}^{n}$ ，也就是 $(2n)!$ 。然后，很显然，我们多算了n个（的全排列和n个）的全排列，所以还要在这个基础上除以 $(n!)$ * $(n!)$ 。
转换，也就是等价于 $C_{2n}^{n}$ （这种解释比较麻烦，非常不建议用）
PS：这种解释，我记得在《组合数学》第5版，Richard A.Brualadi书中，叫做多重集合排列。只是高中没有这种说法。

2）求不合法的排列数目

不合法的排列一定是出现了右括号比左括号多一个的前缀。
我们设

 （为1
 ）为-1

我们还要引入一种变化方式

（）））（（）

1 -1 -1 -1 1 1 -1

我们找到，第一次出现右括号比左括号多的时候，也就是1 -1 -1。变化方法，将1变-1，-1变1
这样，就会形成：
总体看来，将得到n+1个1，和n-1个-1组成的排列。

易知,每一个非法的排列通过如上的变换方式可以得到n+1个1和n-1个-1所组成的排列。
并且，

（	）	）	）	（	（	）
1	-1	-1	-1	1	1	-1

每一个非法排列《通过变换和变换的逆过程可（一一对应）》n+ 1个1和n-1个-1组成的排列

所以显然，所以不合法的排列数为
n+1个1和n-1个-1组成的排列数
也就是 $C_{2n}^{n+1}$

3）Catalan数（卡特兰数）

卡特兰数的第1个格式

卡特兰数的第1个格式： $C_{2n}^{n}-C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n}$

二、模型2证明

思路：借助“状态”，借助图形，观察规律，难道会有一些“动态规划”的意味？当然不是“动态规划”

游乐园的门票50元一张，每人限购一张.现在有10个小朋友排队购票，其中5个小朋友带了1张50元钞票，另外5个小朋友带了1张100元钞票.售票员没有准备零钱.问有多少种排队方法，使售票员总能找的开零钱?

定义状态(a, b)，表示前n个小朋友中有a个小朋友带了50元，有b个小朋友带了100元，其中n=a+b（a≥b）
显然：
1个小朋友的状态只有1种可能性: (1, 0);
2个小朋友的状态有2种可能性: (2, 0)或(1，1);
3个小朋友的状态有2种可能性: (3,0)或(2，1)
etc
到此，有人突发奇想，要是这么写比较麻烦，很不直观，所以想要将这个可视化。就想到了，将a和b映射到直角坐标系中去，也就有了下面这样的图形。
写博客到这，发现，要画这些图还需要弄“几何画板”，考完试再优化

图片说明

很显然，我们要求的就是从点（0，0）到（5，5）不超出直线方程y=x的这样的排列的个数。
我们将，到点（a,b)的方法数是如下图。

图片说明

这样问题就转换为“格路模型”，由《组合数学》第5版，Richard A.Brualadi中证明，显然是

卡特兰数的第1个格式： $C_{2n}^{n}-C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n}$

启发思路，还有https://www.bilibili.com/video/BV1tE411R7mw?from=search&seid=15340802308492660704这个视频的人的证明方式，用了类似于光的“反射”。

三、模型3证明

思路：计数原理-分类

求n个无差别的节点构成的二叉树有多少种不同的结构?
假设n个无差别的节点构成不同的结构数为f(n)
f(0)表示空树,所以规定种数为1种。
分类：

以第1个节点为头时,结构数为f(0)*f(n-1)//左子树是空树，右子树是n-1个点组成的子树
以第2个节点为头时,结构数为f(1)*f(n-2)//左子树是1个点组成的子树，右子树是n-1个点组成的子树
以3节点为头时,结构数为f(2)*f(n-3)
以4节点为头时,结构数为f(3)*f(n-4)
以5节点为头时,结构数为f(4)*f(n-5)
etc.

卡特兰数的第2个格式

f(0)=1,f(1)=1,f(2)=2,f(3)=5时

卡特兰数的第2个格式： $f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+... f(n-1)*f(0)=\frac{1}{n+1}C_{2n}^{n}$

证明： $f(n)=f(0)\*f(n-1)+f(1)\*f(n-2)+... f(n-1)\*f(0)$
$=\sum_{i=0}^{n-1} f(i)f(n-1-i)$
令 $n=n+1$
$f(n+1)=f(0)\*f(n)+f(1)\*f(n-1)+... f(n)\*f(0)$
$=\sum_{i=0}^{n} f(i)f(n-i)$
（1）
构造生成函数
设 $g(x)=f(0)\*x^0+f(1)\*x^1+... f(n)\*x^n$
$=\sum_{n=0}^{\infty} f(n)\*x^n$
（2）
So $[g(x)]^2=(f(0)\*x^0+f(1)\*x^1+...)\*(f(0)\*x^0+f(1)\*x^1+...)$
$=\sum_{n=0}^{\infty}$ $[\sum_{i=0}^{n} f(i)f(n-i)] x^n$
由（1）知 $g(x)=\sum_{n=0}^{\infty}f(n+1)x^n$
（3）
由（2）和（3）知 $x*[g(x)]^2+f(0)x^0=g(x)$
至此，应为 $n->{\infty}$ 极限状态，方程才成立
但Catalan需要离散化
离散化
Because $f(0)=1$
So $x*[g(x)]^2-g(x)+1=0$
So $g(x)=\frac{-b \frac{+}{-} \sqrt(deta)}{2a}$
$g(x)=\frac{1 \frac{+}{-} \sqrt(1-4x)}{2}$
Because
（2）式易知 $g(0)=0$
So $g(x)=\frac{1 - \sqrt(1-4x)}{2}$
令 $K(x)=\sqrt(1-4x)$
我们将它于x₀=0处进行泰勒展开
可以容易知道

系数	展开项
$ $K(x)=(1-4x)^{ \frac{1}{2}}$ $	$\frac{1}{0!}x^0$
$ $K'(x)=(-2)*(1-4x)^{ -\frac{1}{2}}$ $	$\frac{1}{1!}x^1$
$ $K''(x)= (-2)* \frac{2*1}{1!} (1-4x)^{ -\frac{3}{2} }$ $	$\frac{1}{(1+1)*1!}x^2$
$ $K'''(x)= (-2)* \frac{4\3\2\1} {21} (1-4x)^{ -\frac{5}{2} }$ $	$\frac{1}{(3+1)*3!}x^4$
省略	省略
$ $K^(more)(x)= (-2)* \frac{(2n-2)!} {(n-1)!} (1-4x)^{ \frac{-2n+1}{2} }$ $	$\frac{1}{((n-1)+1)*(n-1))!}x^n$

将展开式代入知道 $g(x)$ 表达式，比对系数知道 $f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+... f(n-1)*f(0)=\frac{1}{n+1}C_{2n}^{n}$ 证毕

这样，弄出了递推公式，还可以写代码

#include <stdio.h>
int main()
{
    int f[100]={0};
    int i,j;
    f[0]=1;
    f[1]=1;
    f[2]=2;
    f[3]=5;
    for(i=4; i<=100; i++) 
    {
        for(j=0; j<=i-1; j++)
            f[i]+=f[j]*f[i-1-j];
    }
    printf("%d",f[100]);
    return 0;
}

四、卡特兰数的第3个格式

由 $f(n)=\frac{1}{n+1}C_{2n}^{n}$ 用通项公式相除，易导出

卡特兰数的第3个格式： $f(n)=f(n-1)* \frac{2(2n-1)}{n+1}=f(n-1)* \frac{4*n-2}{n+1}$

五、其他应用

1）在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？
2）圆桌周围有2n个人，他们两两握手，但没有交叉的方案数为f(n)
3）求一个凸多边形区域划分成三角形区域的方法数？
4）10个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问有多少种排列方式?
5)出栈次序问题
6）遇到再补充