Find the number of possible functions from one set to another.?

Npride

2020-05-03 10:42 pm

Consider Sm = {1,2,3,...,m} and Sn = {1,2,3,...,n} with m,n ≥ 3.

(a) How many functions f are there from Sm to Sn such that f(x) = 1 for at least one x ∈ Sm?

(b) How many functions f are there from Sm to Sn such that f(x) ∈{1,2} for at least one x ∈ Sm?

(c) How many functions f are there from Sm to Sn such that f(x) = 1 for at least one x ∈ Sm and f(y) =/= 2 for any y ∈ Sm?

(d) How many functions f are there from Sm to Sn such that f(x) = 1 for at least one x ∈ Sm and f(y) = 2 for at least one y ∈ Sm?

回答 (1)

老怪物

2020-05-04 5:21 am

✔ 最佳答案

(a)
由 Sm 到 Sn 的函數, 對 Sm 的每一元素而言, 在
Sn 中有 n 種選擇. 因此共有 n^m 種選擇. 所以,
Sm 映至 Sn 的函數有 n^m 個, 其中不存在
f(x) = 1
結果的有 (n-1)^m 個. 因此, 至少有一個 x 在 Sm
中使 f(x) = 1 的函數個數為:
n^m - (n-1)^m

(b)
類似 (a), 把沒有 f(x) in {1,2} 的函數 (n-2)^m
從總數中扣除, 得:
n^m - (n-2)^m

(c)
至少存在一個 x 使 f(x) = 1; 並且不存在 y 使
f(y) = 2.
考慮後一條件而不理會前一個條件, 這種函數有
(n-1)^m 個; 其中 (n-2)^m 個既沒有 f(x) =1
也不存在 f(y) = 2. 所以: 既要存在 x 使 f(x)=1
又不能有 y 使 f(y) = 2, 這樣的函數有
(n-1)^m - (n-2)^m
個.

(d)
既要有 x 使 f(x) = 1, 又要有 y 使 f(y) = 2.
這可用 "取捨原理" 來計算:
n^m - 2(n-1)^m + (n-2)^m
上式的意思是從總數 n^m 中分別扣除不存在 f(x)=1
或 f(y) = 2 的; 但這樣會重複扣除 f(x) = 1 及
f(y) = 2 都不存在的函數個數, 所以再把它加回.

👍 3 👎 0