當m>=n時,滿射的組合數(shù).
先說結(jié)果吧,結(jié)果是：n!S(m,n)
其中,S(m,n) 是第2類Stirling數(shù).
先介紹一下第2類Stirling數(shù)：S(m,n).
S(m,n) 是把一個有m個元素的集合,劃分成n個非空子集的方法數(shù).
用到我們這個問題中,先把定義域中m個元素劃分為n個非空子集,每個子集對應(yīng)值域中的一個數(shù),這樣就構(gòu)成一個映射.那么,第1步劃分成n個非空子集有S(m,n)種方法,第2步將每個子集對應(yīng)到一個值有n!種方法.所以,一共有映射：n!S(m,n) 種.
第2類Stirling數(shù)沒有顯式表達式,最簡單的方法就是遞推.
遞推公式為：
S(m,n) = S(m-1,n-1) + n S(m-1,n)
這個公式這么理
將m個元素的集合,劃分成n個子集,有2種情形：
(1) 最后一個元素單獨成為一個集合.這時就等價于：前 m-1 個元素劃分為 n-1 個子集的方法數(shù).于是,就是 S(m-1,n-1).
(2) 最后一個元素不單獨成為一個集合,而是與其它某些元素一起組成集合.這時就等價于：前 m-1 個元素劃分成 n 個子集,然后最后一個元素挑一個子集放進去.于是,就是 n S(m-1,n).
遞推的初始值：
S(m,1) = 1
S(m,m) = 1
BTW：你可以放心大膽的把這個結(jié)果寫給別人,不用擔心別人抱怨它不是顯式的結(jié)果,因為這是組合數(shù)學(xué)最基本的結(jié)論之一,任何一本組合數(shù)學(xué)的書里都是這么寫的.