Re: [理工] [離散] 99成大

[johnyne (close 醬)]

※ 引述《lsy77613 (鯨魚)》之銘言：
: 題目大意:
:          共有4個女生跟5個男生
:          1號女生不喜歡1或3或5號男生
:          2號女生不喜歡2或4號男生
:          3號女生不喜歡3或5號男生
:          4號女生不喜歡4號男生
: 請問有幾種方法可使這4個女生都找到合適的男生?
: 考慮過女生當箱子,男生當球的想法
: 但完全不知道這樣的解法x要取幾次方的係數才是所要的方法數
: 請高手指導這題該怎麼寫了,謝謝

想法是利用排容原理

將ai定義為第i個女生有限制

則可以推導答案為S-S1+S2-S3+S4
那S1~S4可以用暴力法或用小黃上課教過的"機車大連線"

這邊說明一下暴力法
S1定義為有一個女生選男生受到限制
example:1號女生必選1 3 5號男生 或是2號女生必選 2 4號男生
將全部的方法數加起來就是S1
所以S1=4*3*2*(3+2+2+1)
其中(4*3*2代表每一個女生受到限制之外的其他3個女生選男生方法數)

依此類推..

有錯請指教謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.193.164
※ 編輯: johnyne         來自: 1.161.193.164        (02/09 23:48)
推 lsy77613:感謝:)
→ johnyne:機車大連線就是城堡多項式~
推 annheilong:有能可以提供最後的數字嗎?
→ BenLinus:18?
→ dy957:18沒錯
推 weiyung:有人可以解釋一下城堡多項式嗎?上wiki看了 可是看不太懂
推 lsy77613:同感,有請高手解釋一下城堡多項式,謝謝~
推 xygod:http://ppt.cc/!bWV
→ xygod:小黃blog上看的例子。