斯特林数和斯特林反演

传统美德
斯特林数,斯特林反演初探

一些补充:

ij=(ij)j!i^{\underline j}=\binom{i}{j}j!

其实就是要构造出i!(ij)!\frac{i!}{(i-j)!}

和组合恒等式:(ni)(ij)=(nj)(njij)\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-j}{i-j}

证明显然

快速计算$\sum_{i=0}^{n} i^{k}\left(\begin{array}{l}

n \
i
\end{array}\right)$

i=0nik(ni)=i=0n(ni)j=0k{kj}ij=i=0n(ni)j=0k{kj}(ij)j!=i=0n(ni)j=0k{kj}(ij)j!\sum_{i=0}^{n} i^{k}\left(\begin{array}{l} n \\ i \end{array}\right)\\ \begin{aligned} =&\sum_{i=0}^{n} \binom{n}{i}\sum_{j=0}^{k}\left\{\begin{array}{l} k \\ j \end{array}\right\} i^{\underline j}\\ =&\sum_{i=0}^{n} \binom{n}{i}\sum_{j=0}^{k}\left\{\begin{array}{l} k \\ j \end{array}\right\} \binom{i}{j}j!\\ =&\sum_{i=0}^{n} \binom{n}{i}\sum_{j=0}^{k}\left\{\begin{array}{l} k \\ j \end{array}\right\} \binom{i}{j}j!\\ \end{aligned}

先咕咕咕一会