推 recipro :謝謝! 05/03 08:44
※ 引述《XII (Mathkid)》之銘言：
: ※ 引述《recipro (FIFA13勒?????)》之銘言：
: : 最近在算一些東西,
: : 要一直解
: : x_1+x_2+...+x_n=k
: : 0<=x_1,x_2,...,x_n<=m
: : 的整數解組數.
: : 可是我只會使用排容方法來加加減減,
: : 因此想問問大家這種解有上限的問題是否有較為"簡化"的方法?
: [x^k](1+x+..+x^m)^n
: 然後交給電腦算係數吧>"<
: 若 k > mn/2, 可將 k 換成 mn-k, 整數解個數相同
: 同樣的方法可以算 x_1+..+x_n=k, L_i≦x_i≦U_i, i=1,..,n 的整數解
---
(1+...+x^m)^n
[1 - x^(m+1)]^n
= ────────
(1-x)^n
n n i (m+1)i ∞ n j
= { Σ C *(-1) * x } * { Σ H x }
i=0 i j=0 j
i n n
所以 x^k 係數 = Σ (-1) *H C
(i,j) j i
(m+1)i+j=k
= H(n,k) - H(n,k-m-1)*C(n,1) + H(n,k-2m-2)*C(n,2) - ...
這個答案型態其實跟直接用 排容原理 (duel form) 得到的結論是一樣的
====
我是覺得能寫出這樣的答案已經算 "很簡化了"
排列組合的很多問題都是 NP-complete / -hard
您想寫出一個簡單的 alg. 來計算都還不見得辦的到
能用一個 for-loop , 甚至是 explicit sol. 得解只能說你很 lucky
不要被高中的排列組合題目而影響對 computing 的 scope
高中的題目都是有經過設計的
不然就是事件情境單純許多 or 事件的數量級小到不行
例如對 linear diophantine eq. 加上 x_i < x_j 這類 constrain
手算就只能用 "土法煉鋼"
====
回到原問題，那一串很醜的答案有沒有辦法整理出一個 closed form ?
我覺得可以，但需要分段討論
用訊號的角度來看，考慮一個離散訊號:
x[i] = ┌ 1 if 0 <= i <= m
└ 0 others
原問題其實就是將方波訊號，自我 convolution n次:
y[i] := y_n[i] = x[i]‧x[i] ‧... ‧x[i] (conv n times)
則 y[k] 即為所求
例如 y_2[i] = ┌ 1+i if 0 <= i <= m
│ 2m+1-i if m < i <= 2m
└ 0 others
不難預期，每多做一次 conv, 訊號分段數會越來越多
若把它從 distrete -> continuous
convolution 等同於不斷地計算曲面下的面積
算到最後，每段都有屬於自己的 closed form
但若把這些分段的結果 "組合" 成一個 final form (意即無須分段討論)
那最後的 form 應該會跟排容原理的結論一樣
(ps: 上面那句話是個人純屬猜測 )
舉個例子, 考慮 H(n,k) - H(n,k-3)*C(n,1) + H(n,k-6)*C(n,2) - ...
用上面的概念，你可以將之化簡，但代價就是需分段討論
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.82.125
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1399039466.A.C4E.html
※ 編輯: doom8199 (210.61.82.125), 05/02/2014 22:14:53