※ 引述《MOONY135 (柳生劍影)》之銘言：
: let m and n be positive integers with m大於等於n
: then there are
: n^m-C(n,1)(n-1)^m+C(n,2)(n-2)^m-C(n,3)(n-3)^m-......(-1)^(n-1)C(n,n-1)*1^m
: onto functions from a set with m element to a set with n element
不失一般性，命 M = {1,2,3,...,m}, N = {1,2,3,...,n} 分別是二個正整數集合.
欲證從集合 M 映至集合 N 的映成函數 f 個數如題所述, 即證明滿足 f(M) = N 的
函數 f 個數如題所述.
首先， f(M) 包含於 N 是函數的定義：
因為每個 f(i) 皆有 1,2,...,n 共 n 個選法 (i in M), 故共有 n^m 種選法
(相當於, m 個空格, 每個空格可重覆填入 n 個數字的填法)
接下來考慮 N 包含於 f(M), 即
對於每個 j in N = f(M), 皆有 i in M 使得 f(i) = j.
其反面是存在 j in N 使得對於所有 i in M, f(i) 皆不等於 j.
也就是排除 (至少有一個 j in N 使得 f(i) 不等於 j, i in M) 的情形
寫出來就是：
n^m - {(恰有 1 個 j 使 f 映不到) + (恰有 2 個 j 使 f 映不到) + ... +
(恰有 n-1 個 j 使 f 映不到)}
展開為所求. 如果用集合的語言來看： 可以這樣想，命 A_j 表示 j in N 無法
被 f 映到的情形所成的集合. 則所求 =
全部可能性 - (A_1 ∪ A_2 ∪ ... ∪ A_n)的情形數.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.219.121.67
※ 編輯: armopen 來自: 61.219.121.67 (06/05 09:28)