[理工] [離散] 遞迴用生成函數解

[a76126 (123)]

這是小黃離散書上的一個範例

Suppose that we have n dollars and each day we buy either orange($1),

apple($2), or pear($2).

If R(n) is the number of ways of spending all the money,

what is R(10)?

Order is taken into account. For example, R(4) = 11 since there are 11 ways to

spend four dollars : AP, PA, OOOO, OOA, OOP, OAO, OPO, AOO, POO, AA, PP.

書上是用遞迴的方式解 但我想說看能不能用指數生成函數的方式解解看

就設定 O + 2A + 2P = 10

A(X) = e^x * [ (e^x + e^-x)/2 ]^2 求 x^10/10!的係數

但好像不太對 請問是哪裡弄錯了嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.184.151.170
※ 編輯: a76126          來自: 111.184.151.170      (07/20 14:09)
推 AIdrifter:你應該把錢當作相同 也就是相同錢放入相異箱
→ AIdrifter:你這樣解是EGF也就是相異球放入相異箱
→ AIdrifter:1/(1-x)*(1/(1-x^2))^2   find[x^10] 但是這樣並不好算
→ a76126:我也想過用GF解 但最後R(4)=6  會少掉5種排列法
※ 編輯: a76126          來自: 111.184.151.170      (07/20 18:24)
→ a76126:用EGF R(4)=21 又多出10種
→ a76126:我想應該是這些排列法不能單純用生成函數做吧
推 AIdrifter:抱歉 我剛注意到英文是each day 所以PA!=AP
→ AIdrifter:用EGF解是代表錢是相異 但是並無法解決這問題
推 AIdrifter:例如只考慮2A+2P=4 你A可以放相異球12 13 14 23 24 34
→ AIdrifter:方法數是6 但是實際上我們知道只有兩種就是PA和AP
→ AIdrifter:而GF不能用是因為他PA!=AP
→ sneak: 1/(1-x)*(1/ https://daxiv.com