卡特兰数 pufer序列 bsgs

卡特兰数

卡特兰数

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440......

设\(h(n)\)为\(catalan\)数的第\(n\)项

\(h(0)=1\),\(h(1)=1\)

\(h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n≥2)\)

\(h(n)=h(n-1)*(4*n-2)/(n+1)\)

\(h(n)=C(2n,n)/(n+1)\).................(1)

\(h(n)=C(2n,n) - C(2n,n-1)\)..................(2)

用图比较好理解

卡特兰数有一个很重要的意义就是：
\(C_n\)表示所有在\(n×n\)格点中不越过对角线的单调路径的个数（只向上向右走）

不考虑不越过对角线这个条件，有\(C_{2n}^n\)种方案，对每个越过对角线的不合法方案，一定经过\(y=x+1\)这条直线，从路径与该直线的第一个交点处开始，剩余路径进行镜像处理（关于直线对称），终点一定是\((n,n)\)关于直线的对称点\((n-1,n+1)\)每一条\((0,0)->(n-1,n+1)\)的路径，对应一条计数的非法路径，所以合法路径数为

\(C_{2n}^n-c_{2n}^{n-1}\)

得到公式\((2)\)，展开通分整理得到\((1)\)

例题

网格

用类似卡特兰数证明得到答案为

\(C_{n+m}^n-C_{n+m}^{n+1}\)

展开整理

\((n+m)!*(n-m+1)/(n+1)!m!\)

分解质因数约分，然后高精乘统计答案

有趣的数列

可以看成将长度为\(2n\)的排列分成两个排列，那么一共有\(C_{2n}^n\)种

考虑条件3，偶数位里面一个偶数要比前面的偶数位大，而这些数位又比和他们对应的奇数位大，所以我们可以得到：

对于任意偶数位，这里放的数都大于前面的所有数

换句话说，就算前面所有位置都放尽可能小的数，这个位置最小也就只能放跟它下标一样大的数了（位置4只能放大于等于4的值）

我们转换一下题意，变成1~2n一次放入这个数列里，对于每次放的数要么放在最前的奇数位，要么放在最前的偶数位。

联系前面的结论，我们可以知道：一个数列如果有偶数个数多于奇数个数的情况，就不可能满足条件了

放一个偶数看作坐标系中向上走一步，放一个奇数看作向右，可以得到卡特兰数

树屋阶梯

大佬的题解

每次放的钢块一定有一个阶梯角，考虑阶梯角在哪里的钢块覆盖了\((n,0)\)，然后余下部分记录方案，可以得到卡特兰数，具体过程图解大佬的博客讲的很清楚，蒟蒻就不多说了

pufer序列

pufer序列与无根树存在对应关系

\(n\)个点的无根树得到的pufer序列长度为\(n-2\)

如果令编号小的点优先，那么pufer序列与无根树唯一对应

由无根树得到pufer序列

• 找到编号最小的叶节点，将他的父亲加入pufer序列，删除该节点

• 重复操作至剩余两个节点

pufer序列转无根树

• 取出prufer序列最前面的元素x

• 取出在点集中的、且当前不在prufer序列中的最小元素y

• 在x,y之间连接一条边

• 最后在点集中剩下的两个点中连一条边

性质：

1. pufer序列与无根树一一对应

2. 度数为k的点在pufer序列中出现k-1次

3. 一个n个点的完全图的生成树的个数为\(n^{n-2}\)