例題：排列組合，計算函數個數
[quote]己知f是由{1,2,3,4}映至{1,2,3,4}的函數。如果 f 滿足 f(f(x))=f(x)，則這樣的函數有幾種？
答案是41種。[/quote]
若 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 映射之後的[color=blue]值[/color]如果是 [color=blue]a[/color] 的話，一定會滿足 f(a)=a 。
所以只要討論，定義域裡面的每個元素 1,2,3,4 到底有多少個會滿足 f(a)=a [color=sienna]<再怎嚜被 f 函數映射也不會改變值>[/color]
case i : [color=darkgreen]如果{ 1,2,3,4 }裡面恰只有一個元素會滿足 f(a)=a[/color] ，
那光這個 a 的可能性就有 C(4,1) 種，
[color=darkgreen]不失一般性，假設 f(1)=1[/color] ，然後來看 2,3,4 會經 f 映射到哪裡去，
因為 f( [color=red]f(2) [/color]) = [color=red]f(2)[/color], f([color=red]f(3)[/color]) = [color=red]f(3)[/color], f( [color=red]f(4) [/color]) = [color=red]f(4)[/color]
所以 [color=red]f(2),f(3),f(4)[/color] 都滿足 f([color=red]蝦咪碗糕[/color])=[color=red]蝦咪碗糕[/color]
可是由上面[color=darkgreen]綠色[/color]的那兩句知道 [color=#ff0000]蝦咪碗糕[/color] 只有一種選擇性，那就是 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 : [color=darkgreen]如果{ 1,2,3,4 }裡面恰只有兩個元素會滿足 f(a)=a, f(b)=b[/color] ，
那光這個 a, b (不計順序)的可能性就有 C(4,2) 種，
[color=darkgreen]不失一般性，假設 f(1)=1, f(2)=2[/color] ，然後來看 3,4 會經 f 映射到哪裡去，
因為 f([color=red]f(3)[/color]) = [color=red]f(3)[/color], f( [color=red]f(4) [/color]) = [color=red]f(4)[/color]
所以 [color=red]f(3),f(4)[/color] 都滿足 f([color=red]蝦咪碗糕[/color])=[color=red]蝦咪碗糕[/color]
可是由上面[color=darkgreen]綠色[/color]的那兩句知道 [color=#ff0000]蝦咪碗糕[/color] 只有兩種選擇性，那就是 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 : [color=darkgreen]如果{ 1,2,3,4 }裡面恰只有三個元素會滿足 f(a)=a, f(b)=b, f(c)=c[/color] ，
那光這個 a, b,c (不計順序)的可能性就有 C(4,3) 種，
[color=darkgreen]不失一般性，假設 f(1)=1, f(2)=2, f(3)=3[/color] ，然後來看 4 會經 f 映射到哪裡去，
因為 f( [color=red]f(4) [/color]) = [color=red]f(4)[/color]
所以 [color=red]f(4)[/color] 滿足 f([color=red]蝦咪碗糕[/color])=[color=red]蝦咪碗糕[/color]
可是由上面[color=darkgreen]綠色[/color]的那兩句知道 [color=#ff0000]蝦咪碗糕[/color] 有三種選擇性，那就是 1,2,3
所以 f(4) 可以選擇 1, 2, or 3 三選一，
所以 case iii ，只有 C(4,3) * 3種。
case iv : [color=darkgreen]如果{ 1,2,3,4 }裡面恰只有四個元素會滿足 f(a)=a, f(b)=b, f(c)=c, f(d)=d[/color] ，
那光這個 a, b, c, d (不計順序)的可能性就有 C(4,4)=1 種
[color=darkgreen]這一種就是 f(1)=1, f(2)=2, f(3)=3, f(4)=4[/color]
所以，由 case i, ii, iii, iv 共計有 4+24+12+1 = 41 種
^________^
原討論串： [url=http://forum.nta.org.tw/examservice/showthread.php?t=28185]http://forum.nta.org.tw/examservice/showthread.php?t=28185[/url]
頁:
[1]