Re: [中學] 排列組合一問

[ckchi (飄)]

: =============================
: 假設手上有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
→ ckchi       :結論是50塊一放進去瞬間變很醜...
→ ckchi       :等等 後面好像有錯 我再想一下
※ 編輯: ckchi           來自: 140.116.89.133       (10/12 20:11)
→ ckchi       :50塊 變 10塊 應該是 1個換5個 修正這點
推 tropical72  :c 大太有心了, 大推大推 !!
推 wa007123456 :大推
※ 編輯: ckchi           來自: 140.116.89.133       (10/14 16:20)
→ ckchi       :抱歉 修兩個小錯誤
→ ckchi       :(∵a≧0) => (∵c≧0)