[关闭]
@xzyxzy 2018-12-27T08:31:45.000000Z 字数 1585 阅读 653

Catalan&Stirling数

数学

作业部落

评论地址


Catalan数


定义式

一、递推公式

二、应用举例

第一类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个圆排列的方案数
定义式为(表示次上升幂)

二、递推式

两种证明:
1、将第个元素插入,那么可以新开一个圆,或者插入原来的圆中
2、通过这个式子得到

三、性质

dalao_blog
baike_baidu


可以做下这题: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个非空部分的方案数

二、递推式

意思为第个球可以新开一个盒子也可以放在原来的盒子中

三、计算式

也就是
把组合数给拆掉
化成了卷积的形式了,可以用时间内求得
原理是把n个有区别的球放入k个有区别的盒子里的方案数是,也是至少有0个空盒的方案数-至少有1个空盒的方案数+至少有两个空盒的方案数......属于组合数类型的容斥

四、拓展

1、把区别的球放入区别的盒子里不能有空盒的方案数
2、把区别的球放入区别的盒子里允许有空盒的方案数
前者是,表示盒子进行排列
后者是,相当于在中元素中取个作为允许重复的组合,可重组合公式见《组合数学》

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注