斯特林数)第一类Stirling数第二类Stirling数"/>
Stirling数(斯特林数)第一类Stirling数第二类Stirling数
Stirling数(斯特林数)第一类Stirling&和第二类Stirling数
第一类Stirling数
-
定义
- 第一类Stirling数表示把 n n n个不同元素构成 m m m个圆的排列方案数,写作 s ( n , m ) s(n,m) s(n,m).
- 根据正负性分为无符号第一类Stirling数 s u ( n , m ) s_u(n,m) su(n,m)和带符号第一类Stirling数 s s ( n , m ) s_s(n,m) ss(n,m).
- 组合数学中的第一类Stirling数泛指无符号第一类Stirling数,在此,也只展开介绍无符号第一类Stirling数。
-
递推式
- 考虑 s u ( n , m ) s_u(n,m) su(n,m)可以由什么转移得到?
- 1、 s u ( n − 1 , m − 1 ) s_u(n-1,m-1) su(n−1,m−1),由 n − 1 n-1 n−1个不同元素构成了 m − 1 m-1 m−1个圆,则第 n n n个元素必须单独构成第 m m m圆。方案数:
s u ( n − 1 , m − 1 ) s_u(n-1,m-1) su(n−1,m−1) - 2、 s u ( n − 1 , m ) s_u(n-1,m) su(n−1,m),由 n − 1 n-1 n−1个不同元素已经构成了 m m m个圆,则第 n n n个元素可以放在前 n − 1 n-1 n−1个元素中任意一个前面。方案数:
s u ( n − 1 , m ) ∗ ( n − 1 ) s_u(n-1,m)*(n-1) su(n−1,m)∗(n−1) - 则可以得出递推式:
s u ( n , m ) = s u ( n − 1 , m − 1 ) + s u ( n − 1 , m ) ∗ ( n − 1 ) s_u(n,m)=s_u(n-1,m-1)+s_u(n-1,m)*(n-1) su(n,m)=su(n−1,m−1)+su(n−1,m)∗(n−1) -
三角形
n | s u ( n , m ) s_u(n,m) su(n,m) |
---|---|
0 | 1 |
1 | 0 1 |
2 | 0 1 1 |
3 | 0 2 3 1 |
4 | 0 6 11 6 1 |
5 | 0 24 50 35 10 1 |
… | … |
-
性质
- 通过观察以上的三角形可以得到:
- 1、 s u ( 0 , 0 ) = 1 s_u(0,0)=1 su(0,0)=1
- 2、 s u ( n , 0 ) = 0 s_u(n,0)=0 su(n,0)=0
- 3、 s u ( n , n ) = 1 s_u(n,n)=1 su(n,n)=1
- 4、 s u ( n , 1 ) = ( n − 1 ) ! s_u(n,1)=(n-1)! su(n,1)=(n−1)!
- 5、 s u ( n , n − 1 ) = C n 2 = n ( n − 1 ) 2 s_u(n,n-1)=C_{n}^{2}=\frac{n(n-1)}{2} su(n,n−1)=Cn2=2n(n−1)
- 更多请见百度百科
-
应用
- 经典仓库解锁问题:
- 1、有 n n n个仓库,每个仓库 2 2 2把钥匙,共 2 n 2n 2n把钥匙。又有 n n n位官员,如何放置钥匙才能使得每一位官员能打开每一个仓库?(不考虑官员手里的钥匙)共多少种方案?
- 只需把钥匙放成一个环形(仓库 1 1 1放钥匙 2 2 2,仓库 2 2 2放钥匙 3 3 3……仓库 n n n放钥匙 1 1 1),一共有 ( n − 1 ) ! (n-1)! (n−1)!种方案(不能自己放自己的钥匙)。
- 答案实质上是 s u ( n , 1 ) s_u(n,1) su(n,1), n n n个不同元素构成一个环的方案数。
- 2、如果把官员分成 m m m个部,每个部拥有自己的仓库,仓库和官员数量对应。如何放置钥匙才能使得每一位官员能打开自己部的所有仓库(不考虑官员和他们手里的钥匙),而无法打开其他的任何一个仓库?共有多少种方案?
- 分析一下就发现,只要把钥匙类似上一问,但放成 m m m个环即可,
- 这样的方案数正是 n n n个不同元素构成 m m m个环的方案数,
- 所以答案为 s u ( n , m ) s_u(n,m) su(n,m).
第二类Stirling数
-
定义
- 第二类Stirling数表示把 n n n个不同的数划分为 m m m个集合的方案数,要求不能为空集,写作 S ( n , m ) S(n,m) S(n,m).
- 和第一类Stirling数不同,划分集合不必考虑排列次序。
-
递推式
- 考虑 S ( n , m ) S(n,m) S(n,m)可以由什么转移得到?
- 1、 S ( n − 1 , m − 1 ) S(n-1,m-1) S(n−1,m−1),将 n − 1 n-1 n−1个不同元素划分为了 m − 1 m-1 m−1个集合,则第 n n n个元素必须单独放入第 m m m个集合。方案数:
S ( n − 1 , m − 1 ) S(n-1,m-1) S(n−1,m−1) - 2、 S ( n − 1 , m ) S(n-1,m) S(n−1,m),将 n − 1 n-1 n−1个不同元素已经划分为了 m m m个集合,则第 n n n个元素可以放在 m m m个集合中任意一个里面。方案数:
S ( n − 1 , m ) ∗ m S(n-1,m)*m S(n−1,m)∗m - 则可以得出递推式:
S ( n , m ) = S ( n − 1 , m − 1 ) + S ( n − 1 , m ) ∗ m S(n,m)=S(n-1,m-1)+S(n-1,m)*m S(n,m)=S(n−1,m−1)+S(n−1,m)∗m -
三角形
n | S ( n , m ) S(n,m) S(n,m) |
---|---|
0 | 1 |
1 | 0 1 |
2 | 0 1 1 |
3 | 0 1 3 1 |
4 | 0 1 7 6 1 |
5 | 0 1 15 25 10 1 |
… | … |
-
性质
- 通过观察以上的三角形可以得到:
- 1、 S ( 0 , 0 ) = 1 S(0,0)=1 S(0,0)=1
- 2、 S ( n , 0 ) = 0 S(n,0)=0 S(n,0)=0
- 3、 S ( n , 1 ) = 1 S(n,1)=1 S(n,1)=1
- 4、 S ( n , n ) = 1 S(n,n)=1 S(n,n)=1
- 5、 S ( n , 2 ) = 2 n − 1 − 1 S(n,2)=2^{n-1}-1 S(n,2)=2n−1−1
- 6、 S ( n , n − 1 ) = C n 2 = n ( n − 1 ) 2 S(n,n-1)=C_{n}^{2}=\frac{n(n-1)}{2} S(n,n−1)=Cn2=2n(n−1)
- 更多请见百度百科
-
应用
- 各种不同的盒子放球模型:
- 1、 n n n个不同的球放入 m m m个相同的盒子中,不允许盒子为空:
- 方案数 = S ( n , m ) =S(n,m) =S(n,m),正是第二类Stirling数的定义。
- 2、 n n n个不同的球放入 m m m个不同的盒子中,不允许盒子为空:
- 方案数 = S ( n , m ) ∗ m ! =S(n,m)*m! =S(n,m)∗m!,盒子有区别,乘上盒子所有排列即可。
- 3、 n n n个不同的球放入 m m m个相同的盒子中,允许盒子为空:
- 方案数 = ∑ i = 0 m S ( n , i ) =\sum_{i=0}^{m}S(n,i) =∑i=0mS(n,i),枚举非空盒子个数即可。
- 4、 n n n个不同的球放入 m m m个不同的盒子中,允许盒子为空:
- 方案数 = ∑ i = 0 m P ( m , i ) ∗ S ( n , i ) =\sum_{i=0}^{m}P(m,i)*S(n,i) =∑i=0mP(m,i)∗S(n,i),因为盒子不同,所以乘上排列数。
更多
第一类Stirling数(第一类斯特林数)
第二类Stirling数(第二类斯特林数)
更多推荐
Stirling数(斯特林数)第一类Stirling数第二类Stirling数
发布评论