推 supyou5566 :感謝，先推再看! 11/05 20:36
推 supyou5566 :解法跟老師的其實有點類似 真是高手! 11/05 20:59
※ 引述《supyou5566 (❺❺❻❻)》之銘言：
: 一題課本習題，老師說課本的答案他覺得是錯的，但他自己也不確定
: 所以來這裡發問
: Find a generating function for an , the number of partitions of n into
: three parts in which no part is larger than the sum of the other two.
: (其實就是問分成三角形的三個邊)
: 課本答案： (x^3 + x^6) / (1-x^3)(1-x^4)(1-x^6)
: 老師的答案： x^3 / (1-x^2)(1-x^3)(1-x^4)
: 因為老師說他不是100%確定答案，所以想問這裡的各位，
: 有沒有人可以算出哪個答案是正確的或是有其他答案
: 感恩!!
找一個一對一的方法
現在對每一個n : 分成三個部份 a >= b >= c
且滿足 b + c >= a (*)
則 每一數對(a,b,c)可1-1對應到一組(2,3,4)組成之遞增數列且滿足總和為n
來看怎麼對應: (<=)
舉例來看比較快
ex 數列:2 3 4
-> 3 3 3
4 4 4
4 2
2
-> 對應到的(a,b,c)=(4,3,2)
ex 數列:2 2 2 3 4 4 4 4
-> 3 3 3
4 4 4
4 4 4
4 4 4
4 4 4
4 2
4 2
4 2
4
2
2
2
-> 對應到的(a,b,c)=(12,8,5)
一般情況則是 先設a=b=c=0 每看到一個2 a,b加1 每看到一個3 a,b,c加1
每看到一個4 a加2且b,c加1 容易驗證這樣的對應必滿足
a+b+c=n 且(*)
(=>) 則由上面可知
取a-b個4 取c-(a-b)個3 及b-(a-b)-(c-a+b) (=b-c)個2即可
易看出 a=2(a-b)+(c-a+b)+(b-c) b=(a-b)+(c-a+b)+(b-c) c=(a-b)+(c-a+b)
且 n=a+b+c=4(a-b)+3(c-a+b)+2(b-c)
所以知道對應為1-1
那麼計算數量就很簡單
應為 1/(1-x^2)(1-x^3)(1-x^4) - 1/(1-x^2)
其中後面的減項是因為 不能出現c為0的狀況要扣除
注意到(*)如果變成b+c>a 即三角形情況
那麼應為 1/(1-x^2)(1-x^3)(1-x^4) - 1/(1-x^2)(1-x^4)
= x^3/1/(1-x^2)(1-x^3)(1-x^4)
為老師的解
原因很簡單 要扣除掉只有2跟4組成的數列 因為這樣的數列總使得b+c=a
--
^^
('') ~我是可愛的兔子
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.169.217