作者XII (Mathkid)
看板Math
標題Re: [中學] 排列組合問題 (重複排列,但是....)
時間Thu Aug 25 11:24:10 2016
※ 引述《ronald736 (明天會更好)》之銘言:
: 問題描述:
: 現在有7種代號A++(7分)、A+(6分)、A(5分)、B++(4分)、B+(3分)、B(2分)、C(1分)
: 然後將這些代號中取出5個分數放入各科目(A B C D E),如圖
: http://imgur.com/a/cxV5z
: 例如總分是17 = A+ A B+ B C 這5種 也就是 6 + 5 + 3 + 2 + 1 = 17
: 我的問題如下:
: 我希望計算總分為17分的所有組合,但是順序對調的話,只能算同一種,例如:
: A+ A B+ B C 和 A A+ B+ B C 只能算1種 並非2種
: 我目前將它視為 X1 + X2 + X3 + X4 + X5 = 17 使用重複排列計算H的方法,然後限制
: 每個Xi,i從1~7(可包含7),如下:
: H(5,12)-C(5,1)*H(5,5)
: 想法: 用>=1 扣去 >=8 就會得到 1~7的所有重複組合 (1<=Xi<=7)
: 其中: H(5,12) 是指 每個Xi都>=1
: C(5,1)*H(5,5) >=8的狀況,因為5個位置都有可能所以乘上5,這部分要扣掉
: 所以得到 H(5,12) - C(5,1)*H(5,5)
: 但是這樣算出來的會將 6 5 3 2 1 和 5 6 3 2 1 算成2種
: 我的問題只能算1種而已,所以希望請教各位高手,怎麼去算呢?
原來你是總和5~35的都要算啊..
設 x_1+..+x_5=n, 0≦x_1≦..≦x_5≦6, 0≦n≦30 的整數解個數為 a(n)
=> Σ_{n} a(n) q^n = C(11,5)_q (binomial coefficient 的 q-analogue)
[11][10][9][8][7]
= ------------------- (其中 [k]=1+q+q^2+..+q^{k-1}, e.g. [3]=1+q+q^2)
[5][4][3][2][1]
= q^30+ q^29+ 2 q^28+ 3 q^27+ 5 q^26+ 7 q^25+ 10 q^24+ 12 q^23+ 16 q^22
+ 19 q^21+ 23 q^20+ 25 q^19 + 29 q^18+ 30 q^17+ 32 q^16+ 32 q^15
+ 32 q^14+ 30 q^13+ 29 q^12+ 25 q^11+ 23 q^10+ 19 q^9+ 16 q^8+ 12 q^7
+ 10 q^6+ 7 q^5+ 5 q^4+ 3 q^3+ 2 q^2+ q+ 1
總和為 n 的方法數有 a(n-5) (即 q^{n-5} 的係數)
e.g. 總和為 17 的方法數有 a(12)=29 (即 q^12 的係數)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.136.107
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1472095453.A.C47.html
※ 編輯: XII (140.122.136.107), 08/25/2016 11:24:54
推 Desperato : 傻眼啊wwwww 推推 08/25 11:51
※ 編輯: XII (140.122.136.107), 08/25/2016 11:51:56
→ Desperato : 去找了analog又想半天才確認這是對的 08/25 12:03
→ Desperato : X大為什麼會知道可以這樣算? 08/25 12:04
推 takeyourtime: 指定17分,列舉就好了 08/29 18:20