發新話題
打印

例題:排列組合,計算函數個數

推到噗浪
推到臉書

例題:排列組合,計算函數個數

引用:
己知f是由{1,2,3,4}映至{1,2,3,4}的函數。

如果 f 滿足 f(f(x))=f(x),則這樣的函數有幾種?


答案是41種。
若 y0 = f(x0) 則 f(y0)=y0 ,

則 (y0,f(y0))=(y0,y0) 為固定點

也就是經函數一次映射之後,會映到固定點


若有一個固定點,函數有 C(4,1) * 1^3 = 4 種

若有二個固定點,函數有  C(4,2) * 2^2 = 24 種

若有三個固定點,函數有  C(4,3) * 3^1 = 12 種

若有四個固定點,函數有  C(4,4) = 1 種


共有 4+24+12+1 = 41 種








詳細版:

1,2,3,4 經 f 映射之後的如果是 a 的話,一定會滿足 f(a)=a 。

所以只要討論,定義域裡面的每個元素 1,2,3,4 到底有多少個會滿足 f(a)=a <再怎嚜被 f 函數映射也不會改變值>

case i : 如果{ 1,2,3,4 }裡面恰只有一個元素會滿足 f(a)=a

那光這個 a 的可能性就有 C(4,1) 種,

不失一般性,假設 f(1)=1 ,然後來看 2,3,4 會經 f 映射到哪裡去,

因為 f( f(2) ) = f(2), f(f(3)) = f(3), f( f(4) ) = f(4)

所以 f(2),f(3),f(4) 都滿足 f(蝦咪碗糕)=蝦咪碗糕

可是由上面綠色的那兩句知道 蝦咪碗糕 只有一種選擇性,那就是 1 ,

所以 f(2),f(3),f(4) 只能選擇 f(2)=1,f(3)=1,f(4)= 1

所以 case i ,只有 C(4,1) * 1^3 種。



case ii : 如果{ 1,2,3,4 }裡面恰只有兩個元素會滿足 f(a)=a, f(b)=b

那光這個 a, b (不計順序)的可能性就有 C(4,2) 種,

不失一般性,假設 f(1)=1, f(2)=2 ,然後來看 3,4 會經 f 映射到哪裡去,

因為 f(f(3)) = f(3), f( f(4) ) = f(4)

所以 f(3),f(4) 都滿足 f(蝦咪碗糕)=蝦咪碗糕

可是由上面綠色的那兩句知道 蝦咪碗糕 只有兩種選擇性,那就是 1,2,

所以 f(3),f(4) 只能選擇 1 or 2 二選一,

f(3)=1 or 2 搭配 f(4)= 1 or 2 共 2*2 種可能性

所以 case ii ,只有 C(4,2) * 2^2 種。






case iii : 如果{ 1,2,3,4 }裡面恰只有三個元素會滿足 f(a)=a, f(b)=b, f(c)=c

那光這個 a, b,c (不計順序)的可能性就有 C(4,3) 種,

不失一般性,假設 f(1)=1, f(2)=2, f(3)=3 ,然後來看 4 會經 f 映射到哪裡去,

因為 f( f(4) ) = f(4)

所以 f(4) 滿足 f(蝦咪碗糕)=蝦咪碗糕

可是由上面綠色的那兩句知道 蝦咪碗糕 有三種選擇性,那就是 1,2,3

所以 f(4) 可以選擇 1, 2, or 3 三選一,

所以 case iii ,只有 C(4,3) * 3種。









case iv : 如果{ 1,2,3,4 }裡面恰只有四個元素會滿足 f(a)=a, f(b)=b, f(c)=c, f(d)=d

那光這個 a, b, c, d (不計順序)的可能性就有 C(4,4)=1 種

這一種就是 f(1)=1, f(2)=2, f(3)=3, f(4)=4




所以,由 case i, ii, iii, iv 共計有 4+24+12+1 = 41 種






^________^







原討論串: http://forum.nta.org.tw/examservice/showthread.php?t=28185

TOP

發新話題