Re: [中學] 排列組合一問
: =============================
: 假設手上有50,10,5,1元可以使用
: 今天有i元要付錢 總共有n個方法
: 試求出i與n的關係式
: =============================
先考慮沒有50塊的情形：
10a+5b+c = i
=> 10a+5b ≦ i (∵c≧0)
=> 2a+b ≦ [i/5] (∵a,b為整數)
let k = [i/5]
k => a,b ,n (所有的a,b組合，下面說明用p,q表示)
0 => 0,0 1 (00)
1 => 0,1 2 (01/00) +1
2 => 1,0 4 (10/02/01/00) +2
3 => 1,1 6 (11/10/03/02/01/00) +2
4 => 2,0 9 (20/12/11/10/04/03/02/01/00) +3
5 => 2,1 12 (21/20/13/12/11/10/05/04/03/02/01/00) +3
6 => 3,0 16 (30/22/21/20/14/13/12/11/10/06/05/04/03/02/01/00) +4
7 => 3,1 20 (31/30/23/22/21/20/15/14/13/12/11/10/07/06/05/04/03/02/01/00) +4
仔細觀察上面的規律，你會發現：
若 k +1 使 (a,0) 變 (a,1) 時 ： 所有的 0≦p≦a 都會多出一組新的 p,q 組合(q+1)
若 k +1 使 (a,1) 變 (a+1,0) 時： 所有的 0≦p≦a 都會多出一組新的 p,q 組合(q+1)
且還會多一組 (a+1,0) 的組合
因此當 i = 10a+5b+c，
且a+b+c的值最小時：
n = 2*(1+2+...+a)+(a+1)*(b+1) (b=0再加1次a+1；b=1則再加2次a+1)
= 2*a(a+1)/2 + (a+1)*(b+1)
= a(a+1) + (a+1)*(b+1)
n = (a+1)(a+b+1)
接下來考慮有50塊的情況：
50x+10a+5b+c = i
=> 50x+10a+5b ≦ i (∵c≧0)
=> 10x+2a+b ≦ [i/5] (∵x,a,b為整數)
x = 0 時：
情況跟前面一樣，
n = (a+1)(a+b+1)
x = 1 時：
n = (a+1)(a+b+1) + (a'+1)(a'+b+1)
其中 a'=5+a ；即分成 x=1 (1,a,b) 和 x=0 (0,5+a,b) 兩種情況相加
= (a+1)(a+b+1) + (5+a+1)(5+a+b+1)
= (a+1)(a+b+1) + 5^2 + 5(a+1+a+b+1) + (a+1)(a+b+1)
= 2(a+1)(a+b+1) + 5(2a+b+2) + 5^2
x = 2 時：
n = (a+1)(a+b+1) + (a'+1)(a'+b+1) + (a"+1)(a"+b+1)
其中 a'=5+a 且 a"=10+a ； 即分成 x=2,x=1,x=0 三種情況相加
= 2(a+1)(a+b+1) + 5(2a+b+2) + 5^2
+ 10^2 + 10(a+1+a+b+1) + (a+1)(a+b+1)
= (2+1)(a+1)(a+b+1) + 5(1+2)(2a+b+2) + 5^2*(1^2+2^2)
x = 3 時：
n = (2+1)(a+1)(a+b+1) + 5(2a+b+2)(1+2) + 5^2*(1^2+2^2)
+ 15^2 + 15(a+1+a+b+1) + (a+1)(a+b+1)
= (3+1)(a+1)(a+b+1) + 5(2a+b+2)(1+2+3) + 25(1^2+2^2+3^2)
因此對任意 (x,a,b) ：
n = (x+1)(a+1)(a+b+1) + 5(2a+b+2)(1+2+3+...+x) + 25(1^2+2^2+3^2+...+x^2)
n = (x+1)(a+1)(a+b+1) + 5x(x+1)(2a+b+2)/2 + 25x(x+1)(2x+1)/6
式子簡化我就不整理了......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.89.133
→
10/12 20:01, , 1F
10/12 20:01, 1F
→
10/12 20:03, , 2F
10/12 20:03, 2F
※ 編輯: ckchi 來自: 140.116.89.133 (10/12 20:11)
→
10/12 20:12, , 3F
10/12 20:12, 3F
推
10/12 21:44, , 4F
10/12 21:44, 4F
推
10/12 21:47, , 5F
10/12 21:47, 5F
※ 編輯: ckchi 來自: 140.116.89.133 (10/14 16:20)
→
10/14 16:20, , 6F
10/14 16:20, 6F
→
10/14 16:21, , 7F
10/14 16:21, 7F
討論串 (同標題文章)
