Re: [理工] 100清大計科離散第九題

看板Grad-ProbAsk作者a016258時間8年前 (2016/01/02 14:58)推噓3(3推 0噓 5→)

留言8則, 6人參與討論串2/2 (看更多)

半夜修改文章打好了， ptt 突然掛掉...= = 直接讀暫存貼上來了。作者: a016258 (憨) 看板: Grad-ProbAsk 標題: Re: [理工] 100清大計科離散第九題時間: Sat Jan 2 14:58:34 2016 ※ 引述《panda04056 (圓仔cross56)》之銘言： : 想請問b小題怎麼解，謝謝！ : http://i.imgur.com/IeKGWAZ.jpg

如果沒有限定要用什麼方法的話，提供一個簡易的想法。要求正整數， let x_i = y_i + 1 => y_1 + y_2 + y_3 + y_4 = 9 ( 0 ≦ y_i ≦ 3 ) 一種方法就是用重複組合直接算，但就是要扣掉一堆超過條件的 ( y_i = 4 , 5 .... 9 ) 解決的方法就是反過來算， let y_i = 3 - z_i => z_1 + z_2 + z_3 + z_4 = 3 ( 0 ≦ z_i ≦ 3 ) [ Ex : z ( 1 , 2 , 0 , 0 ) -> y( 2 , 1 , 3 , 3 ) ] => H(4,3) = 20 有錯還請不吝指正。 -- If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is. － John von Neumann -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.240.33.114 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1451717916.A.C41.html

推

panda04056

01/02 18:20, , 1^F

01/02 18:20, 1^F

→

odanaga

01/02 19:03, , 2^F

01/02 19:03, 2^F

假設 y_1 + y_2 + y_3 + y_4 = 9 ( 0 ≦ y_i ≦ 4 ) 如果直接算就要扣掉 5 6 7 8 9 y_i = 4 - z_i ( 0 ≦ z_i ≦ 4 ) => z_1 + z_2 + z_3 + z_4 = 7 這樣算就變成要扣 5 6 7 節省一些時間但就沒這麼快~

→

yaxauw

01/02 23:05, , 3^F

01/02 23:05, 3^F

生成函數在解一些複雜的題目很好用解這種相對簡單的題目就顯得有點殺雞焉用牛刀的感覺 (而且計算起來相對慢很多) 就像微方有些要求拉氏拉過去再拉回來遠比直接計算慢多了~ 回到此題如果熟練排組基本上可以直接看出答案 ( 正整數 => 13 - 4 = 9 , 反過來算最大是 3 => 4*3 - 9 = 3 => H(4,3) ) 如果是生成函數此題作法為 g(x) = x^4 * ( 1 - x^4 )^4 / ( 1 - x)^4 找 x^13 係數 => sum C(4,r) (-1)^r * x^(4r) * sum C(3+s,s) x^s r= 0~4 s=0..oo => (r,s) = (0,9) (1,5) (2,1) => C(12,9) + C(4,1)*(-1) * C(8,5) + C(4,2) * 1 *C(4,1) = 220 - 4 *56 + 6 * 4 = 220 - 224 + 24 = 20

推

goldflower

01/03 00:34, , 4^F

01/03 00:34, 4^F

→

goldflower

01/03 00:34, , 5^F

01/03 00:34, 5^F

推

pzoxic

01/03 11:49, , 6^F

01/03 11:49, 6^F

差點把此推文砍了XD ※ 編輯: a016258 (111.240.5.68), 01/03/2016 13:52:25

→

ningninghaha

01/03 15:04, , 7^F

01/03 15:04, 7^F

→

ningninghaha

01/03 15:05, , 8^F

01/03 15:05, 8^F

最後得到的算式還跟生成函數一樣...也沒比較快但也可能是 >= 的情況我較少遇到使用這算法還是先考慮了正整數，算 y_1 + y_2 + y_3 + y_4 = 9 ( 0 ≦ y_i ≦ 3 ) 全部可能 H(4,9) 一個 >=4 => y_1 + y_2 + y_3 <= 5 => H(4,5) 同理兩個 >=4 => H(4,1) => H(4,9) - C(4,1) H(4,5) + C(4,2) H(4,1) = C(12,9) - 4 * C(8,5) + 6 *C(4,1) http://i.imgur.com/BcEIxKr.jpg