第二类斯特林数

组合意义

将 \(n\) 个元素划分到 \(k\) 个非空集合中的方案数，记作 \(\displaystyle {n\brace k}\) 或 \(S(n,k)\)。

特殊地，定义 \(\displaystyle {n\brace 0}=[n=0],{n\brace n}=1\)。

重要恒等式

Formula 1.1：

\[{n\brace k}={n-1\brace{k-1}}+k{n-1\brace{k}},n\ge 1 \]

证明：若将第 \(n\) 个元素单独划分入一个集合，那么需要将前 \(n-1\) 个元素划分到 \(k-1\) 个非空集合中；若不单独将第 \(n\) 个元素划分入一个集合，那么需要将前 \(n-1\) 个元素划分到 \(k\) 个非空集合中，并将第 \(n\) 个元素划入这 \(k\) 个集合中的任意一个，根据加法原理与乘法原理可知 Formula 1.1 成立。

Formula 1.2：

\[{n\brace k}=\frac{1}{k!}\sum_{i=0}^{k}{k\choose i}(-1)^{k-i}i^n \]

证明：考虑用两种不同的方式计数将 \(n\) 个元素划分到 \(k\) 个有标号且可以为空的集合的方案数。

• 每个元素都可以划入 \(k\) 个集合中的任意一个，根据乘法原理，方案数为 \(n^k\)。

• 钦定不为空的集合有 \(i\) 个，再将 \(n\) 个元素划分入这 \(i\) 个非空集合中，根据第二类斯特林数的定义及乘法原理，方案数为 \(\displaystyle \sum_{i=0}^{k}{k\choose i}{n\brace i}i!\)

故有

\[n^k=\sum_{i=0}^{k}{k\choose i}{n\brace i}i! \]

二项式反演得

\[{n\brace k}k!=\sum_{i=0}^k{k\choose i}(-1)^{k-i}i^n\iff{n\brace k}=\frac{1}{k!}\sum_{i=0}^{k}{k\choose i}(-1)^{k-i}i^n \]

未完待续，明天初赛加油！