已知 $A$ 是包含 $m$ 个元素的集合，$B$ 是包含 $n$ 个元素的集合，考虑从 $A$ 到 $B$ 的映射个数，单射个数以及满射个数．
【难度】
【出处】
无
【标注】
【答案】
映射个数为 $n^m$，当 $m\leqslant n$ 时，单射个数为 ${\rm A}_n^m$；当 $m\geqslant n$ 时，满射个数为 $\dfrac{1}{n!}\sum_{k=0}^n(-1)^k{\rm C}_n^k(n-k)^m$
【解析】
显然映射个数为 $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)$ 是把 $m$ 个元素划分成 $n$ 个非空子集的方法，考虑这些非空子集分别对应 $B$ 中的各个元素，那么容易得到满射个数为 $n!\cdot S(m,n)$．因此问题的关键是求 $S(m,n)$．
将 $m$ 个元素的集合划分为 $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.$$
答案
解析
备注
