题目

关于从A到B的满映射的个数,排列组合
集合A有元素m个,集合B有元素n个,关于从A到B的映射有n^m.
当n>=m时,单映射有几个?我想了想应该是A (n, m)
但当m>=n时,满映射有几个?我实在不知道怎么做.求大神帮忙.

提问时间：2020-10-26

答案

当m>=n时,满射的组合数.
先说结果吧,结果是：n!S(m,n)
其中,S(m,n) 是第2类Stirling数.
先介绍一下第2类Stirling数：S(m,n).
S(m,n) 是把一个有m个元素的集合,划分成n个非空子集的方法数.
用到我们这个问题中,先把定义域中m个元素划分为n个非空子集,每个子集对应值域中的一个数,这样就构成一个映射.那么,第1步划分成n个非空子集有S(m,n)种方法,第2步将每个子集对应到一个值有n!种方法.所以,一共有映射：n!S(m,n) 种.
第2类Stirling数没有显式表达式,最简单的方法就是递推.
递推公式为：
S(m,n) = S(m-1,n-1) + n S(m-1,n)
这个公式这么理
将m个元素的集合,划分成n个子集,有2种情形：
(1) 最后一个元素单独成为一个集合.这时就等价于：前 m-1 个元素划分为 n-1 个子集的方法数.于是,就是 S(m-1,n-1).
(2) 最后一个元素不单独成为一个集合,而是与其它某些元素一起组成集合.这时就等价于：前 m-1 个元素划分成 n 个子集,然后最后一个元素挑一个子集放进去.于是,就是 n S(m-1,n).
递推的初始值：
S(m,1) = 1
S(m,m) = 1
BTW：你可以放心大胆的把这个结果写给别人,不用担心别人抱怨它不是显式的结果,因为这是组合数学最基本的结论之一,任何一本组合数学的书里都是这么写的.