標題:
例題：排列組合，計算函數個數
[打印本頁]
作者:
weiye
時間:
2007-7-18 01:58
標題:
例題：排列組合，計算函數個數
引用:
己知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
歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)
論壇程式使用 Discuz! 6.1.0
