映射个数问题

已知$A$是包含$m$个元素的集合，$B$是包含$n$个元素的集合，考虑从$A$到$B$的映射个数，单射个数以及满射个数．

---

分析与解　显然映射个数为$n^m$，单射个数为${\rm A}_n^m$($m\leqslant n$)，下面考虑当$m\geqslant n$时的满射个数．

设$S(m,n)$是把$m$个元素划分成$n$个非空子集的方法，考虑这些非空子集分别对应$B$中的各个元素，那么容易得到满射个数为$n!\cdot S(m,n)$．因此问题的关键是求$S(m,n)$．

将$m$个元素的集合划分为$n$个非空子集有两种方式：
方式一　最后一个元素单独构成一个集合，此时方法数为$S(m-1,n-1)\cdot 1$；
方式二　最后一个元素不单独构成一个集合，此时方法数为$S(m-1,n)\cdot n$．

这样我们就得到了递推公式

$$S(m,n)=S(m-1,n-1)+nS(m-1,n),$$ 且容易得到递推的初值$S(m,1)=1$，$S(m,m)=1$．这样就得到了 $$S(m,n)=\dfrac{1}{n!}\sum_{k=0}^n(-1)^k{\rm C}_n^k(n-k)^m.$$

思考与总结　题中的$S(m,n)$即第二类Stirling数，并没有显式的表达式；第一类Stirling数是$m$个不同的元素构成$n$个圆排列的数目，记作$s(m,n)$，其递推公式为

$$s(m,n)=s(m-1,n-1)+(n-1)s(m-1,n),$$ 初值为$s(0,0)=1$，$s(n,0)=0$，$s(n,n)=1$．