推 chanlele : 謝謝！ 05/25 13:02
※ 引述《chanlele (長樂)》之銘言：
: 大家好～想向各位請教！
: 問題是這樣子的：
: 10元硬幣30枚，20元硬幣20枚，30元硬幣10枚，請問付出600元有多少種排列組合？
: 看到問題之後想的方向是x+2y+3z=60，在未知數各有限制的情況下窮舉，後來發現組合太
: 多了用電腦跑出所有可能性和篩選出符合的答案……
: 基本上高中後就很少碰數學了，想請問有沒有更「數學」的方法來解答這個問題呢？
: 謝謝！
: (Var1-3 是x y z
: https://i.imgur.com/oZUc4AV.jpg
: （如果分類或標題不對請再和我說，不清楚這是解未知數還是排列組合，我分不出來Q
10x+20y+30z = 600 => x+2y+3z = 60, 0≦x≦30, 0≦y≦20, 0≦z≦10
Consider the generating function:
(1+x+x^2+...+x^30)(1+x^2+x^4+...+x^40)
1-x^31 1-x^42
=-------- ---------
1-x 1-x^2
1-x^31-x^42+x^73
= ------------------
(1-x)^2(1+x)
∞ ∞
= (1-x^31-x^42+x^73)Σ(n+1)x^n Σ (-1)^n x^n
n=0 n=0
a_n = n+1, b_n = (-1)^n
z=0 => x+2y = 60 => 找generating function的x^60係數:
(i) 後面無窮級數乘積的x^60係數
60 60 60 30 29
Σa_nb_(60-n) = Σ(n+1)(-1)^(60-n) = Σ(n+1)(-1)^n = Σ(2n+1)-Σ(2n+2)
n=0 n=0 n=0 n=0 n=0
30 29
= Σ(2n+1) - Σ(2n+1) - 30
n=0 n=0
= 2*30+1-30
= 31
(ii) 後面無窮級數乘積的x^29係數
29 29 29 14 14
Σa_nb_(29-n) = Σ(n+1)(-1)^(29-n) = Σ(n+1)(-1)^(n+1) = -Σ(2n+1) + Σ(2n+2)
n=0 n=0 n=0 n=0 n=0
14 14
= -Σ(2n+1) + Σ(2n+1) + 15
n=0 n=0
= 15
(iii) 後面無窮級數乘積的x^18係數
18 18 18 9 8
Σa_nb_(18-n) = Σ(n+1)(-1)^(18-n) = Σ(n+1)(-1)^n = Σ(2n+1) - Σ(2n+2)
n=0 n=0 n=0 n=0 n=0
9 8
= Σ(2n+1) - Σ(2n+1) - 9
n=0 n=0
= 2*9+1-9
= 10
=> generating function的x^60項係數 = 31 - 15 - 10 = 6
z = 1 => x+2y = 57
找generating function的x^57項係數:
57 28 28
Σ(n+1)(-1)^(n+1) = -Σ (2n+1) + Σ(2n+2) = 29
n=0 n=0 n=0
26 13 12
Σ(n+1)(-1)^n = Σ(2n+1) - Σ(2n+2) = 27-13 = 14
n=0 n=0 n=0
15 7 7
Σ(n+1)(-1)^(n+1) = -Σ(2n+1) + Σ(2n+2) = 8
n=0 n=0 n=0
=> 係數 = 29 - 14 - 8 = 7
In general,
z = 2k => x+2y = 60-6k => 找generating function的x^(60-6k)係數
60-6k 60-6k 30-3k 29-3k
Σ (n+1)(-1)^(60-3k-n) = Σ (n+1)(-1)^n = Σ (2n+1) - Σ (2n+2)
n=0 n=0 n=0 n=0
= 2(30-3k)+1 - (30-3k)
= 31 - 3k, 0≦k≦5
29-6k 14-3k 14-3k
Σ (n+1)(-1)^(29-6k-n) = -Σ (2n+1) + Σ (2n+2) = 15-3k, 0≦k≦4
n=0 n=0 n=0
18-6k 18-6k 9-3k 8-3k
Σ (n+1)(-1)^(18-6k-n) = Σ (n+1)(-1)^n = Σ(2n+1) - Σ(2n+2)
n=0 n=0 n=0 n=0
=2(9-3k)+1 - (9-3k)
=10 - 3k, 0≦k≦3
=> x^(60-6k)項係數 = (31-3k) - (15-3k) - (10-3k) = 3k + 6, 0≦k≦3
= (31-3k) - (15-3k) = 16, k = 4
= 31-3k, k = 5
z = 2k+1 => x+2y = 60-3(2k+1) = 57-6k => 找generating function的x^(57-6k)係數
57-6k 57-6k 28-3k 28-3k
Σ (n+1)(-1)^(57-6k-n) = Σ (n+1)(-1)^n = -Σ (2n+1) + Σ (2n+2)
n=0 n=0 n=0 n=0
= 29-3k, 0≦k≦4
26-6k 26-6k 13-3k 12-3k
Σ (n+1)(-1)^(26-6k-n) = Σ (n+1)(-1)^n = Σ (2n+1)- Σ (2n+2)
n=0 n=0 n=0 n=0
= 2*(13-3k)+1 - (13-3k)
= 14-3k, 0≦k≦4
15-6k 15-6k 7-3k 7-3k
Σ (n+1)(-1)^(15-6k-n) = -Σ (n+1)(-1)^(n+1) = -Σ (2n+1) + Σ (2n+2)
n=0 n=0 n=0 n=0
= 8-3k, 0≦k≦2
=> x^(57-6k)項係數 = (29-3k) - (14-3k) - (8-3k) = 3k + 7, 0≦k≦2
= (29-3k) - (14-3k) = 15, 3≦k≦4
=> 把z=0~10的case都加起來:
2
Σ[(3k+6)+(3k+7)] + [(3*3+6)+15] + (16+15) + (31-3*5)
k=0
2
= Σ(6k+13) + 30 + 47
k=0
= (13+25)*3/2 + 77
= 57 + 77
= 134
所以有134種付法
Remark: 用程式驗算如下
#include <iostream>
using namespace std;
int main()
{
int x, y, z;
int count = 0;
for(z = 0; z <= 10; ++z){
for(y = 0; y <= 20; ++y){
for(x = 0; x <= 30; ++x){
if(x+2*y+3*z == 60){
++count;
cout << x << " " << y << " " << z << endl;
}
}
}
}
cout << count << endl;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.47.66.237 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1684169079.A.788.html
※ 編輯: yueayase (114.47.66.237 臺灣), 05/16/2023 00:45:53
※ 編輯: yueayase (114.47.66.237 臺灣), 05/16/2023 01:04:18