[理工] [離散] 101成大 函數對應

[JacobSyu (JacobSyu)]

(1) If A={1,2,3,...,10}, the number of functions f:A->A satisfy
f^(1)({1,2,3})=empty set,f^(1)({4,5})={1,3,7}, and f^(1)({8,10})={8,10} is 7776.

101成大單選題2.(A): f^(1)是什麼意思? 7776怎麼求得?


(2) Let A={1,2,3,4,5} and B={u,v,w,x,y}. Determine the number of one-to-one
functions f:A->B where f(1)≠v, w,f(2)≠u, w,f(3)≠x, y and f(4)≠v,x,y

101成大計算題(2): 我用tree列舉應該是14種,有更好的方法?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.133.127.244
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419614749.A.351.html
推 mikeing27: (2)應該可以用排容做 再用城堡多項式求排容的係數
→ mikeing27: 但是我算的答案是12 我不知道是不是我算錯= =
推 mikeing27: (1)f^(1)的對法應該是把定義域和對應域都縮小的意思
→ mikeing27: 所以是(2^3)(2^2)(3^5)=7776
→ mikeing27: (2^3)是f^(1)({4,5})={1,3,7}的方法
→ mikeing27: (2^2)是f^(1)({8,10})={8,10}
→ mikeing27: (3^5)是剩下元素的對法
→ JacobSyu: 更正(2)有12種,列舉容易出錯..
→ JacobSyu: 感謝mikeing27大大,說明很清楚 thx
推 dpbdqb: 奇怪, (2)我用rook及列舉都算14
推 dpbdqb: (1)A選項我也不懂, 但題目是選錯的, 排除其它選項的答A
推 dpbdqb: 我算錯了, 那題D錯, 不過A還是不知道
→ JacobSyu: (1)我現在看又覺得怪怪的,mike大的算法,f^(1)如mike所說
→ JacobSyu: 7776指的是f,並非f^(1)
→ JacobSyu: (2^3)是f^(1)({4,5})={1,3,7},非3^2
→ JacobSyu: (2)應該是12種沒錯,沒學rook,所以用列舉
→ JacobSyu: 列舉我從5,4,3,2,1(限制少在較高level)
→ JacobSyu: 若分支複雜建議把subtree..獨立畫出  不然容易出錯
→ JacobSyu: ...不可以凌晨算題目,總共14總= =
→ JacobSyu: http://ppt.cc/VVtC
→ JacobSyu: (1)其他選項很簡單
推 mikeing27: (2)我算錯了 是14  (1) f^(-1) 應該是這個
→ winds24023: 剛翻到手邊詳解，（1）是f^（-1），1.3.7對到4.5、8.1
→ winds24023: 8.10對到8.10，2.4.5.6對到6.7.9，共7776種，答案是d
→ winds24023: 就是mike大那樣
推 dpbdqb: 原po可以查查rook polynomial
→ JacobSyu: 沒想花時間再去看rook...但排容&Catalan相關rook我會thx