Re: [理工] [離散]台大電機 生成函數

作者: mi981027 (呱呱竹)   2019-12-03 03:48:29
首先先了解F_3(x) - F_2(x)這套解法的想法是甚麼
https://i.imgur.com/icjskyy.jpg
簡單來說,10個相同物放入3個相同箱,不允許空箱的方法數,等同於:
分割整數10,"恰"使用3個整數來分割的方法數。也等同於:
分割整數10,最大只能使用3來分割,且一定要用到3的方法數
(使用Ferrers diagram作轉置來思考)
那就可以用生成函數來列式了,因為現在限制最大只能使用3來分割
所以生成函數裡就只需要考慮1出現次數的GF, 2出現次數的GF, 3出現次數的GF
這就是F_3(x)
可是現在規定一定要用到3
那就必須扣掉只出現1或2的情況,也就是F_2(x)
https://i.imgur.com/VSAAz0h.jpg
所以第一個問題是你的F_3(x) - F_2(x)列式列錯了
第二個問題是箭頭指的地方化簡錯了,所以讓你以為這個解法可以往下做
事實上整數分割的問題(應該)是沒辦法用生成函數求係數的方法做出來的
(有錯還請指正><)
因為根本無法化簡生成函數的式子
記得小黃也有提到,這樣的問題頂多就是要你寫出生成函數,不太可能去求個數
那這題還是要求個數怎麼辦??
其實就是爆開了,這題爆開只有8個,絕對比求生成函數快多了><
作者: mistel (Mistel)   2019-12-03 08:52:00
半夜也照著把生成函數列出來結果邊想著這樣不是還要暴力討論係數嗎結果迷迷糊糊睡著了... 感謝mi大

Links booklink

Contact Us: admin [ a t ] ucptt.com