Catalan&Stirling数

数学

作业部落

评论地址

---

Catalan数

$1,1,2,5,14,42,132,429,1430,4862,16796,58786...$
定义式：

$$C[x+1]=C[0]C[x]+C[1]C[x-1]+C[2]C[x-2]...+C[x]C[0]$$

一、递推公式

$$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]$种，相当于钦定根之后左右子树有$0..n$中选择，用定义式解释）
• 售票处没有零钱，$n$个$5$元$n$个$10$元的人，多少种排列可以满足每次都可以给$10$元的找零？（$C[n]$种，出栈序列，用定义式解释）
• 在圆上选择$2n$个点,将这些点成对连接起来使得所得到的$n$条线段不相交的方法数？（$C[n]$种，相当于括号序列，左括号和右括号匹配，然后转化为出栈序列）

第一类Stirling数

此处只讨论无符号$Stirling$数

s[n][k])	k=0	k=1	k=2	k=3	k=4	k=5	k=6
n=0	1
n=1	0	1
n=2	0	1	1
n=3	0	2	3	1
n=4	0	6	11	6	1
n=5	0	24	50	35	10	1
n=6	0	120	274	225	85	15	1

一、定义

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数

S[n][k])	k=0	k=1	k=2	k=3	k=4	k=5	k=6
n=0	1
n=1	0	1
n=2	0	1	1
n=3	0	1	3	1
n=4	0	1	7	6	1
n=5	0	1	15	25	10	1
n=6	0	1	31	90	65	15	1

一、定义

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

二、递推式

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

三、计算式

$$S[n][k]=\frac{1}{k!}[k^n-C[k][1](k-1)^n+C[k][2](k-2)^n-...+(-1)^{k-1}C[k][k-1]1^n]$$ 也就是 $$S[n][k]=\frac{1}{k!}\sum_{i=1}^{k}(-1)^iC[k][i](k-i)^n$$ 把组合数给拆掉 $$S[n][k]=\sum_{i=1}^{k}\frac{(-1)^i(k-i)^n}{i!(k-i)!}$$ 就化成了卷积的形式了，可以用$NTT$在$O(nlogn)$时间内求得$S[n]$
原理是把n个有区别的球放入k个有区别的盒子里的方案数是$k!S[n][k]$，也是至少有0个空盒的方案数-至少有1个空盒的方案数+至少有两个空盒的方案数......属于组合数类型的容斥

四、拓展

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