卡特兰数 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\)格点中不越过对角线的单调路径的个数(只向上向右走)

image

image

不考虑不越过对角线这个条件,有\(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}\)

文章标题:卡特兰数 pufer序列 bsgs
文章链接:https://www.dianjilingqu.com/50847.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>