Re: [理工] ［離散］台大電機 生成函數
首先先了解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個，絕對比求生成函數快多了><
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.128.185 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1575316114.A.155.html
※ 編輯: mi981027 (114.136.254.112 臺灣), 12/03/2019 05:46:37
推
12/03 08:52,
6年前
, 1F
12/03 08:52, 1F
→
12/03 08:52,
6年前
, 2F
12/03 08:52, 2F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
