习题14.3 about statistical-learning-method-solutions-manual HOT 1 OPEN

一个非生成的方法是这样的
第二类 Stirling 数 $S\left( n,k \right)$. 即将 n 个可区分小球放入 k 个不可区分盒子的方法数（不允许盒子为空）.

我们记 $A_{i}=\left{ 第i个盒子为空 \right}$，则

$$
k!S\left( n,k \right)=\left| \bar{A}{1}\cap\cdots\cap \bar{A}{k} \right|=\left| S \right|-\left| A_{1}\cup\cdots\cup A_{k} \right|
$$

由于 $\left| A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{s}} \right|=\left( k-s \right)^{n}$，则由容斥原理即得

$$ \begin{aligned} k!S\left( n,k \right)&=k^{n}-\sum\limits_{i=1}^{k-1}\left( k-i \right)^{n}\binom{k}{i}\left( -1 \right)^{i-1}\\ &=\sum\limits_{i=0}^{k}\left( -1 \right)^{i}\binom{k}{i}\left( k-i \right)^{n}\\ &=\sum\limits_{i=0}^{k}\left( -1 \right)^{k-i}\binom{k}{i}i^{n} \end{aligned} $$

from statistical-learning-method-solutions-manual.