第二类斯特林数
介绍
有 n n n个不同的小球，要放在 m m m个相同的盒子中，且每个盒子不能为空，问有多少种方案。
第二类斯特林数就是这类问题的答案，其表示方法为 S ( n , m ) S(n,m) S(n,m)。
一些公式
我们考虑如何求 S ( n , m ) S(n,m) S(n,m)。
首先， S ( 0 , 0 ) = S ( 1 , 1 ) = 1 S(0,0)=S(1,1)=1 S(0,0)=S(1,1)=1， S ( 1 , m ) = 0 S(1,m)=0 S(1,m)=0，其中 m > 1 m>1 m>1。
考虑当前放第 n n n个小球，它可以和前面的小球放在一个盒子里，也可以新开一个盒子，那么
S ( n , m ) = m × S ( n − 1 , m ) + S ( n − 1 , m − 1 ) S(n,m)=m\times S(n-1,m)+S(n-1,m-1) S(n,m)=m×S(n−1,m)+S(n−1,m−1)
因为空了就不合法，所以可以用容斥来推通项公式
S ( n , m ) = 1 m ! ∑ i = 0 m ( − 1 ) i C m i ( m − i ) n S(n,m)=\dfrac{1}{m!}\sum\limits_{i=0}^m(-1)^i C_m^i(m-i)^n S(n,m)=m!1i=0∑m(−1)iCmi(m−i)n
我们先把盒子看作互不相同，其中 i i i表示至少有 i i i个盒子为空， ( − 1 ) i (-1)^i (−1)i是容斥系数， C m i C_m^i Cmi表示在 m m m个盒子中选 i i i个为空， n n n个球任意放在剩下 ( m − i ) (m-i) (m−i)个盒子中的方案数为 ( m − i ) n (m-i)^n (m−i)n。因为盒子相同，而先前我们把盒子看作互不相同，所以要乘上 1 m ! \dfrac{1}{m!} m!1。
还有一个比较常见的公式
m n = ∑ k = 0 n S ( n , k ) × C m k × k ! m^n=\sum\limits_{k=0}^nS(n,k)\times C_m^k\times k! mn=k=0∑nS(n,k)×Cmk×k!
m n m^n mn其实就是把 n n n个小球任意地放在 m m m个不同的盒子中，每个小球有 m m m种选法，盒子可以为空。而 k k k枚举的就是非空盒子的个数， C n k C_n^k Cnk表示在 n n n个盒子中选 k k k个为空。因为 S ( n , k ) S(n,k) S(n,k)表示将 n n n个不同的球放在 k k k个相同的盒子中，再乘上 k ! k! k!表示放在 k k k个不同的盒子中。方案数相同，所以相等。
为了好看一些，我们也可以将 m , n m,n m,n的定义互换，得到
n m = ∑ k = 0 m S ( m , k ) × C n k × k ! n^m=\sum\limits_{k=0}^mS(m,k)\times C_n^k\times k! nm=k=0∑mS(m,k)×Cnk×k!