习题14.3

[CSMsamuel]

习题14.3中T(n,k) 指数生成函数表达式不是显然的。此部分是该题的实际核心所在，而展开生成函数反而是简明的。请补充该部分的细节。

[CSMsamuel]

一个非生成的方法是这样的
第二类 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} $$