[理工] 離散_無序分割求係數的方法

作者: fmtshk (fmtshk)   2019-07-12 10:43:15
https://i.imgur.com/MmF6mKN.jpg
請問大佬,關於整數無序分割的方法數,由書上的Farrar's graph得知
[正整數8分割成4個部份] 方法數是5
如果要用[求某項係數]的方式得出答案
列出生成函數後,有什麼公式可以比較快找到x^8的係數?
翻了前面求係數的類題,它是用取的
https://i.imgur.com/b7j0E2e.jpg
這題也只能這樣做嗎?
https://i.imgur.com/OtXepYX.jpg
例如我這樣把數列列出之後,有沒有什麼比較快的方法,找出F4(x)和F3(x)中x^8的係數?
作者: Ricestone (麥飯石)   2019-07-12 11:37:00
你先算G=F4-F3,會發現G是X^4*F4,這樣好算很多上次有說過,生成函數主要是提供有條理的計數方式,保證一定有辦法土法煉鋼出東西,但是能不能發現到小技巧來加速又是另一回事了
作者: mistel (Mistel)   2019-07-12 11:40:00
i+2j+3p+4t=8 解解看 不知道這樣可不可以
作者: fmtshk (fmtshk)   2019-07-12 13:23:00
謝謝回答,我剛嘗試直接乘開,因為X超過8的項都可無視,發現沒想像中慢

Links booklink

Contact Us: admin [ a t ] ucptt.com