映射个数问题

已知A是包含m个元素的集合,B是包含n个元素的集合,考虑从AB的映射个数,单射个数以及满射个数.


分析与解 显然映射个数为nm,单射个数为Amn(m),下面考虑当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)=1S(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)=1s(n,0)=0s(n,n)=1

此条目发表在解题展示分类目录。将固定链接加入收藏夹。

发表回复