作者yueayase (scrya)
看板Math
标题Re: [代数] 请问600元有多少种组合
时间Tue May 16 00:44:37 2023
※ 引述《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://webptt.com/cn.aspx?n=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
1F：推 chanlele : 谢谢！ 05/25 13:02