推 panda04056: 謝謝大大提供的方法！ 01/02 18:20
→ odanaga: 如果yi範圍變0~4 好像不能這樣算? 01/02 19:03
假設 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
生成函數在解一些複雜的題目很好用
解這種相對簡單的題目 就顯得有點 殺雞焉用牛刀的感覺 (而且計算起來 相對慢很多)
就像微方 有些要求拉氏 拉過去再拉回來 遠比直接計算慢多了~
回到此題 如果熟練排組 基本上可以直接看出答案
( 正整數 => 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
→ goldflower: 不過生成函數比較省腦力XD 01/03 00:34
差點把此推文砍了XD
※ 編輯: a016258 (111.240.5.68), 01/03/2016 13:52:25
→ ningninghaha: 推薦使用排容 快又直觀 01/03 15:04
→ ningninghaha: 全部可能 - 4取1 * 一個>= 4 + 4取2 *兩個>=4 = 20 01/03 15:05
最後得到的算式還跟生成函數一樣...也沒比較快
但也可能是 >= 的情況 我較少遇到使用
這算法還是先考慮了正整數， 算 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
青菜蘿蔔各有所好 能解出題目的都是個方法
至於哪個解題速度較快
就交由各位看官自己決定了
※ 編輯: a016258 (111.240.5.68), 01/03/2016 15:55:53