Catalan&Stirling数

Tags:数学

作业部落链接：https://www.zybuluo.com/xzyxzy/note/1195372

Catalan数

\(1,1,2,5,14,42,132,429,1430,4862,16796,58786...\)

一、递推公式

\[C[n]=\frac{C[n-1]*(4*n-2)}{n+1}\]\[C[n]=\frac{C(2n,n)}{n+1}\]\[C[n]=C(2n,n)-C(2n,n-1)\]

二、应用举例

• 给定\(N\)个节点，能构成多少种不同的二叉搜索树？（\(C[N]\)种）
• 售票处没有零钱，\(n\)个\(5\)元\(n\)个\(10\)元的人，多少种排列可以满足每次都可以给\(10\)元的找零？（\(C[n]\)种，出栈序列）
• 在圆上选择\(2n\)个点,将这些点成对连接起来使得所得到的\(n\)条线段不相交的方法数？（\(C[n]\)种）

第一类Stirling数

此处只讨论无符号\(Stirling\)数

一、定义

s[n][k]表示将n个不同的元素构成k个圆排列的方案数
定义式为（\(x^{n↑}\)表示\(x\)的\(n\)次上升幂）\[x^{n↑} =x(x+1)(x+2)...(x+n-1)\\ =s[n][0]+s[n][1]*x+s[n][2]*x^2+...+s[n][n]*x^n\]

二、递推式

\[s[n][k]=s[n-1][k-1]+(n-1)*s[n-1][k]\]两种证明：
1、将第\(n+1\)个元素插入，那么可以新开一个圆\(+s[n][k-1]\)，或者插入原来的圆中\(+n*s[n][k]\)
2、\(x^{(n+1)↑}=x^{n↑}*(x+n)\)通过这个式子得到

三、性质

dalao_blog
baike_baidu
\[s[1][1]=1,s[n][0]=s[n][k]=0,(n>0,k>n)\]\[s[n][1]=(n-1)!\]\[\sum_{k=0}^{n}s[n][k]=n!\]
可以做下这题：HN2018省队集训 6.25T2

第二类Stirling数

一、定义

表示n个有区别的球放入k个相同的盒子中的方案数
也就是将n个数拆成k个非空部分的方案数

二、递推式

\[S[n][k]=S[n-1][k-1]+k*S[n-1][k]\]意思为第\(n\)个球可以新开一个盒子也可以放在原来的盒子中

三、拓展

1、把\(n\)个有区别的球放入\(k\)个有区别的盒子里不能有空盒的方案数
2、把\(n\)个无区别的球放入\(k\)个有区别的盒子里允许有空盒的方案数
前者是\(k!*S[n][k]\)，表示盒子进行排列
后者是\(C(n+k-1,n)\)，相当于在\(k\)中元素中取\(n\)个作为允许重复的组合，可重组合公式见《组合数学》\(P20\)

Catalan&Stirling数

原文：https://www.cnblogs.com/xzyxzy/p/9251029.html