Board logo

標題: 重複組合之有上限問題 [打印本頁]
作者: kggj5220    時間: 2018-4-3 21:46     標題: 重複組合之有上限問題

想請教各位前輩，當重複組合問題遇到有上限的時候改怎麼辦呢？
例題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
這題我就不知道怎麼算比較好~~

再請益，這類問題有固定做法嗎
或者是說當總和更高時該怎麼辦？
作者: weiye    時間: 2018-4-3 23:08     標題: 回復 1# kggj5220 的帖子

例題1 → 如例題1及例題2你寫的方法。其實就是排容原理。

例題2

\(x_1+x_2+x_3+x_4 = 16 \Rightarrow \left(5-x_1\right)+\left(5-x_2\right)+\left(5-x_3\right)+\left(5-x_4\right) = 4\)

令 \(y_1 = 5-x_1\) ， \(y_2 = 5-x_2\) ， \(y_3 = 5-x_3\) ， \(y_4 = 5-x_4\)

則原題目等同於

求 \(y_1+y_2+y_3+y_4 = 4\) 的非負整數解有多少組，其中 \(y_1, y_2, y_3, y_4\) 均為介於 \(0\) ~ \(5\)之整數

所以答案就是 \(H_4^4 = 35\)


例題3，原理同上， \(x_1+x_2+x_3+x_4 = 16 \Rightarrow \left(4-x_1\right)+\left(4-x_2\right)+\left(5-x_3\right)+\left(6-x_4\right) = 3\)

所以答案就是 \(H_3^4 = 20\)


教到這部分，我喜歡問學生： "四顆骰子放在桌面上，已知桌面上看去四顆點數和為 \(20\)，那這四顆骰子與桌面相貼在一起的那四面，點數和又是多少？" 並提示學生，骰子對面的兩個點數和為 \(7\)，也就是抽任一顆骰子來看看，都會發現 \(1\) 的對面是 \(6\)，\(2\) 的對面是 \(5\)，\(3\) 的對面是 \(4\)。
作者: kggj5220    時間: 2018-4-4 21:10     標題: 回復 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\)
作者: kggj5220    時間: 2018-4-4 21:14

請問...怎麼都會自己置中..........
作者: weiye    時間: 2018-4-4 22:13


顯示出來就是位在行內的數學式： \(x^2\)


顯示出來就是單獨一行且置中的數學式： \[x^2\]

----------------------------------------------------------------

例題3：

\(1\leq x_1 \leq4 \Rightarrow 0\leq4-x_1\leq3\)

\(1\leq x_2 \leq4 \Rightarrow 0\leq4-x_2\leq3\)

\(1\leq x_3 \leq5 \Rightarrow 0\leq5-x_3\leq4\)

\(1\leq x_4 \leq6 \Rightarrow 0\leq6-x_4\leq5\)

然而 \(\left(4-x_1\right)+\left(4-x_2\right)+\left(5-x_3\right)+\left(6-x_4\right) = 3\)

所以 \(\left(4-x_1\right), \left(4-x_2\right), \left(5-x_3\right), \left(6-x_4\right)\) 都不會超過三，

因此不會有影響。


----------------------------------------------------------------

例題2：你回覆的數學式子地方，有打字上的小錯誤， 第一個方程式多打 \(y_1\) 到 \(y_4\) 了。

圖片附件: a1.png (2018-4-4 22:13, 2.46 KB) / 該附件被下載次數 4969
https://math.pro/db/attachment.php?aid=4343&k=c7fc02995e50b65e47c51ade1b0d0005&t=1732233185



圖片附件: a2.png (2018-4-4 22:13, 2.21 KB) / 該附件被下載次數 5086
https://math.pro/db/attachment.php?aid=4344&k=bc55ddf01d9974e363e4ef5399896482&t=1732233185

作者: kggj5220    時間: 2018-4-5 20:10     標題: 回復 3# weiye的帖子

終於懂了~感謝老師不吝指教!!
作者: laylay    時間: 2018-4-19 12:35     標題: 回復 1# kggj5220 的帖子

先當做4個箱子都放滿共4+4+5+6=19 球, 再在4個箱子取出3 球=H(4,3) 即可
作者: kggj5220    時間: 2018-4-19 17:43     標題: 回復 7# laylay 的帖子

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



歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0