看板 Math 關於我們 聯絡資訊
最近在算一些東西, 要一直解 x_1+x_2+...+x_n=k 0<=x_1,x_2,...,x_n<=m 的整數解組數. 可是我只會使用排容方法來加加減減, 因此想問問大家這種解有上限的問題是否有較為"簡化"的方法? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.28.223 ※ 文章網址: http://www.ptt.cc/bbs/Math/M.1399004632.A.65D.html
j0958322080 :重複組合 05/02 12:26
recipro :嗯 我就是把全部的情形算出來, 然後扣掉不符合的聯集 05/02 12:34
recipro :問題在聯集的部份是一堆東西的總和 還是有快速的想法 05/02 12:35
wayn2008 :假設是2顆骰子點數和=9 =>x+y=9 =>x+y=7 H(2,7) 05/02 12:42
wayn2008 :扣掉 (7,0) H(2,2) 05/02 12:43
wayn2008 :有(7,0)(0,7)兩種 =>H(2,7)-2*H(2,2) 05/02 12:44
wayn2008 :不對...應該說是(7,1)(1,7)兩種 變成H(2,1) 05/02 12:45
wayn2008 :有(7,1)(1,7)兩種 =>H(2,7)-2*H(2,1) 05/02 12:46
wayn2008 :考慮一個情況超過 其他在最底限 骰子就用(7,1,...,1) 05/02 12:49
wayn2008 :不過這種算法在某種情況有風險 可以試著自己想想:) 05/02 12:50
唔, 舉例來說好了. 像a+b+c+d+e+f=30, a,b,c,d,e,f為0~8的整數解組數, 目前只會用 H(6,30)-C(6,1)H(6,21)+C(6,2)H(6,12)-C(6,3)H(6,3) 來算, 所以一般來說 a_1+a_2+...+a_m=n, a_i限制在0~k之間, 則解數為 H(m,n)-C(m,1)H(m,n-(k+1))+C(m,2)H(m,n-2(k+1))-... 可是式子乘開後不知道怎麼整理 :p 所以想問問是否有其他的角度可以切入這個問題... <(_ _)>
wayn2008 :個人覺得這樣已經比全部都列出來還快了...還要挑剔? 05/02 13:39
wayn2008 :而且實際上依照現在課綱 是不容許有過度複雜的題型.. 05/02 13:41
哈哈, 也不算挑剔啦, 只是想將一個數列的遞迴式跟一般式找出來, 或許這問題對應到某個特徵多項式也不一定~ 翻遍手邊組合學的書也沒有相關問題...(思考)
wayn2008 :話說 那串式子算出來好像是 -17268...wolfram算的 05/02 13:59
ohoh~~ 最後一個H(6,9)應該是H(6,3), 已修正 ※ 編輯: recipro (39.10.28.223), 05/02/2014 14:09:46
sneak : 扣掉 (7,0) H( https://noxiv.com 01/02 15:45
muxiv : 有(7,0)(0,7) https://moxox.com 07/07 12:05