模板 - 数学 - 组合数学 - 第二类斯特林数

组合意义

记 \(S(n,m)\) 表示，把 \(n\) 个不同的小球，放在 \(m\) 个相同的盒子里，且每个盒子至少有 \(1\) 个球，的方法数。

记 \(S(n,m)\) 表示，把 \(n\) 个不同的元素，划分为 \(m\) 个非空集合的方法数。

显然 \(S(0,0)=1\) ，而 \(S(n,0)\) 当 \(n\geq 1\) 时显然是不合法的方案， \(S(0,m)\) 当 \(m\geq 1\) 时因为至少有 \(1\) 个空盒子所以也显然是不合法的方案。

递推

\(S(n,m)=S(n-1,m-1)+m*S(n-1,m)\)

含义是，多一个新的球，那么假如再新加一个盒子去装，显然是一种办法，否则要把这个球放在先前已有的 \(m\) 个盒子中的任意一个，由于新加的这个小球是全新的，所以这个和组合数的递推公式不一样。

通项

\(S(n,m)=\frac{1}{m!}(\sum\limits_{i=0}^{m}(-1)^i*C(m,i)*(m-i)^n)\)