打印

重複組合之有上限問題

kggj5220

發私訊
加為好友
目前離線

1^# 大中小發表於 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
這題我就不知道怎麼算比較好~~

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

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

2^# 大中小發表於 2018-4-3 23:08 只看該作者

回復 1# kggj5220 的帖子

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

例題2

x1+x2+x3+x4=16

5−x1

+

5−x2

+

5−x3

+

5−x4

=4

令 y1=5−x1 ， y2=5−x2 ， y3=5−x3 ， y4=5−x4

則原題目等同於

求 y1+y2+y3+y4=4 的非負整數解有多少組，其中 y1

y2

y3

y4 均為介於 0 ~ 5之整數

所以答案就是 H44=35

例題3，原理同上， x1+x2+x3+x4=16

4−x1

+

4−x2

+

5−x3

+

6−x4

=3

所以答案就是 H34=20

教到這部分，我喜歡問學生： "四顆骰子放在桌面上，已知桌面上看去四顆點數和為 20，那這四顆骰子與桌面相貼在一起的那四面，點數和又是多少？" 並提示學生，骰子對面的兩個點數和為 7，也就是抽任一顆骰子來看看，都會發現 1 的對面是 6，2 的對面是 5，3 的對面是 4。

多喝水。

TOP

kggj5220

發私訊
加為好友
目前離線

3^# 大中小發表於 2018-4-4 21:10 只看該作者

回復 2# weiye的帖子

感謝瑋岳大詳細解說~~

在思考過您的例子之後
就我的例題2我自己是這樣解釋
令x1+x2+x3+x4=16，且每一個括號總和為5
所以有x1+y1=5、x2+y2=5、x3+y3=5、x4+y4=5
這樣x、y會彼此限制，都不會超過5
因為x1+y1=5

y1=5−x1
所以題意等同問 y1+y2+y3+y4=16，此時符合y1

5、y2

5、y3

5、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

kggj5220

發私訊
加為好友
目前離線

4^# 大中小發表於 2018-4-4 21:14 只看該作者

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

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

5^# 大中小發表於 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 了。

多喝水。