1.城堡多項式問題
不知道城堡多項式那個式子該如何使用，例如下題：
我知道該怎麼畫，也知道r(C,x)該怎麼求，但我不清楚最下面排容式子和它有什麼關係？
2.利用排容原理求質數個數
我是想用N=110去算，可是結果錯誤，看了解答後，
發現他帶S0=N=109算，但為什麼S1那邊全部都要減1呢？
如果要扣掉"1"，不是只要整除的才要減嗎？
還有，他都是用＂110＂去除，為什麼呢？
是因為先扣掉"1"不是質數，所以才用S0=109嗎？
3.排容問題
我不懂重複字母為什麼是IN,NI,IO,OI,NO,ON
為什麼不用II,NN,OO去想呢~?
謝謝助教囉!!!
2 則留言:
1.兩者應該是係數的關係。當我們將之繪成表格時、左上角和右下角兩區塊就會獨立、故將兩區塊的多項式相乘、係數剛好會符合我們所要求的。
(6*5*4*3)、(5*4*3)、(4*3)...這些是我們知道的、我們只是不知道他們的係數分別為何，所以才用城堡多項式來解這個問題。
2.僅僅只是猜想、除了1不是質數、0是否也不是質數呢？
110/2會不會把0也算進去了？
不過題目上面假設a1,a2,a3,a4是「大於」2,3,5,7、這點我也很納悶、應該要包含才是啊？
3.我認為是因為若出現II、就沒有第二個II可以跟第一個II重複出現了。
ININFORMATO、類似這樣，IN這個組合就出現了兩次。
但若要考慮連續兩個一樣的letter的話：
III.....至少要三個一樣的letter才可以、但此題中最多只有兩個一樣的letter(I、N、O)
(題目要求的是連續letter的組合出現超過一次、不是連續一樣的letter出現超過一次)。
以上淺見..
1. 其實只要了解rook polynomial和排容有甚麼關係, 你就會發現它應該沒有你想像中的複雜, 因為它其實和我們以往學的排容概念是一模一樣的, 只是在想法上多加了利用整理表格的方式來方便我們去計算排容而已
以此題為例, 假設你把rook polynomial通通忘掉不要看, 看最後的結果就好了, 其中
(1) 第一項那個6!/2!指的就是全部的分配方式
(2) 第二項的9*(5!/2!)指的則是有一個男生配到了他不該配的女生, 其他的隨便配, 因為圖裡有 9 個黑色框框, 所以這樣總共會有 9 種不該配對的組合, 然後5!/2!指的就是剩下的隨便配
(3) 第三項同理就是有兩個男生都配到了不該配的女生, 如果你用暴力法來算, 就可以算出有27種這樣的組合, 然後剩下的4b2g隨便配共會有4!/2!種可能
看到這你可以再回去體會一下r(C,x)是怎麼寫出來的, 後面我就不列給你看了, 我主要想說的是, 如果你考試時真的忘記rook polynomial要怎麼列, 那麼你用暴力法直接做排容, 不用花很久的時間應該也可以算的出來, 因為他通常不會給你一個很大的棋盤
2. 是的, 是因為1不是質數的關係, 因為你在找2,3,5,7的所有倍數時, 不會找到1, 所以全部的可能還得扣掉這一個才行
To 月戀星辰: 要大於才行, 不可以包含, 因為2,3,5,7都是質數, 如果你把1倍的也給扣掉了, 那就會少算這4個質數
3. 語意的問題, 他寫pair of consecutive letters, 指的就是連在一起出現的字母, 而不是相同的字母
張貼留言