發新話題
打印

重複組合之有上限問題

重複組合之有上限問題

想請教各位前輩,當重複組合問題遇到有上限的時候改怎麼辦呢?
例題1:
x₁+x₂+x₃+x₄+x₅=10
且x₁、x₂、x₃、x₄、x₅均為介於0~9之整數
答案:996
這題是先做H⁵₁₀-5,因為有五種不合的情況

例題2
x₁+x₂+x₃+x₄=16
且x₁、x₂、x₃、x₄均為介於0~5之整數
答案:35
這題則先做H⁴₁₆- C⁴₁  x  H⁴₁₀ + C⁴₂  x  H⁴₄=35
先算全部做法--其中一個先拿6個+其中2個先拿6+6共12個

例題3
x₁+x₂+x₃+x₄=16,滿足x₁≦4,x₂≦4,x₃≦5,x₄≦6之正整數解有幾組?
答案:20
這題我就不知道怎麼算比較好~~

再請益,這類問題有固定做法嗎
或者是說當總和更高時該怎麼辦?

TOP

回復 2# weiye的帖子

感謝瑋岳大詳細解說~~


在思考過您的例子之後
就我的例題2我自己是這樣解釋
令\( x_1+x_2+x_3+x_4=16\),且每一個括號總和為5
所以有\(x_1+y_1=5\)、\(x_2+y_2=5\)、\(x_3+y_3=5\)、\(x_4+y_4=5\)
這樣x、y會彼此限制,都不會超過5
因為\(x_1+y_1=5\) \( \Rightarrow \) \(y_1=5-x_1\)
所以題意等同問 \(y_1+y_2+y_3+y_4=16\),此時符合\(y_1\le5\)、\(y_2\le5\)、\(y_3\le5\)、\(y_4\le5\)
即\((5-x_1)+(5-x_2)+(5-x_3)+(5-x_4)=16 \Rightarrow  x_1+x_2+x_3+x_4=4\)即\(H^4_4\)

不知這樣是否正確?

再來還有一個小疑惑,我的例題3是求正整數,這樣不會有影響嗎??


骰子問題是這樣的:令\(x_1+x_2+x_3+x_4=20\)
其中\(x_1+y_1=7\)、\(x_2+y_2=7\)、\(x_3+y_3=7\)、\(x_4+y_4=7\)
\( \Rightarrow (x_1+x_2+x_3+x_4)+(y_1+y_2+y_3+y_4)=4x7\)
所以有\(y_1+y_2+y_3+y_4=8\)

TOP

請問...怎麼都會自己置中..........

TOP

回復 3# weiye的帖子

終於懂了~感謝老師不吝指教!!

TOP

回復 7# laylay 的帖子

感謝laylay老師的妙招~這後來我有思考過
但這方法不適用在我的例題一,因為H(5,35)會發生取球取到變負的~我想我之前應該就是在這轉換之間打結的

TOP

發新話題