斯特林数分为第一类斯特林数和第二类斯特林数。
第一类斯特林数:将 \(p\) 个球排列成 \(k\) 个非空的圆排列的方案数,两个圆排列之间没有顺序关系,记作 \(s(p,k)\)
第二类斯特林数:将 \(p\) 个球放到 \(k\) 个相同的盒子的方案数,记作 \(S(p,k)\)。
第一类斯特林数 \(s(p,k)\) 的求解方法:
a. 当前第 \(p\) 个球放到前 \(p-1\) 个球构成的 \(k\) 个圆排列中的一个,每个圆排列以顺时针为正方向,根据第 \(p\) 个球正方向上第一个遇到的球有 \(p-1\) 种,有 \((p-1)\cdot s(p-1,k)\) 种方案。
b. 当前第 \(p\) 个球单独成圆,方案就是 \(s(p-1,k-1)\) 种。
综上,\(s(p,k)=s(p-1,k-1)+(p-1)\cdot s(p-1,k)\)。
第二类斯特林数 \(S(p,k)\) 的求解方法:
a. 当前第 \(p\) 个球放到前 \(p-1\) 个球构成的 \(k\) 个盒子中的一个,根据第 \(p\) 个球放进的盒子有 \(k\) 种,有 \(k\cdot S(p-1,k)\) 种方案。
b. 当前第 \(p\) 个球单独成盒,方案就是 \(S(p-1,k-1)\) 种。
综上,\(S(p,k)=S(p-1,k-1)+k\cdot S(p-1,k)\)。
【例题】
那么实质就是枚举 \(k\) 并求 \(s(n,k)\) 之和。