作者Tangut (七下擋象)
看板Math
標題[其他] 非負整數解數目（遞增）
時間Tue Feb 1 22:21:49 2022
X1+X2+X3+…+Xn=M
且 X1<=X2 <=X3 .... <=Xn 求非負整數解數目
在近代物理講統計物理的章節中看到的，書中提到的例子是X1+X2+X3+…+X6=8，一共有20
組解，書上是用列舉得到的，想試著用排列組合寫出通解式子，想了很久還是寫不出來，
麻煩解惑了，謝謝
_____________________________________________________________________________
XII的解答：
令[k]=(1-q^k)/(1-q)=1+q+q^2+...+q^(k-1) (共k項)
[n取r]={[n][n-1]...[n-r+1]}/{[r][r-1]...[1]}
(就是把一般計算C(n,r)={n(n-1)...(n-r+1)}/{r(r-1)..1}的每一項k都換成[k])
Thm
x1+...+xn=m 且滿足 x1<=x2<=...<=xn 的非負整數解個數為 [n+m取n] 的q^m係數.
Eg.x1+....+x6=8 且 x1<=...<=x6 的非負整數解個數=?
[14取8]=[14取6]={[14][13][12][11][10][9]}/{[6][5][4][3][2][1]}=
q^48 + q^47 + 2*q^46 + 3*q^45 + 5*q^44 + 7*q^43 + 11*q^42 + 14*q^41 + 20*q^40
+ 25*q^39 + 33*q^38 + 40*q^37 + 51*q^36 + 59*q^35 + 71*q^34 + 81*q^33 +
94*q^32 + 103*q^31 + 116*q^30 + 123*q^29 + 134*q^28 + 139*q^27 + 146*q^26 +
147*q^25 + 151*q^24 + 147*q^23 + 146*q^22 + 139*q^21 + 134*q^20 + 123*q^19 +
116*q^18 + 103*q^17 + 94*q^16 + 81*q^15 + 71*q^14 + 59*q^13 + 51*q^12 +
40*q^11 + 33*q^10 + 25*q^9 + 20*q^8 + 14*q^7 + 11*q^6 + 7*q^5 + 5*q^4 + 3*q^3
+ 2*q^2 + q + 1
其中 q^8 係數為 20
Ref.
A Course in Enumeration by M. Aigner
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.17.120 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1643725311.A.B79.html
1F：推 j0958322080 : 高中的重複組合阿，H^m_n = C^(m+n+1)_n02/01 22:22
2F：→ Tangut : 要x1<=x2<=x3…，還有這個條件，不知為啥原文沒顯02/01 22:32
3F：→ Tangut : 示02/01 22:32
補上了
※ 編輯: Tangut (223.138.17.120 臺灣), 02/01/2022 22:37:23
4F：→ XII : [n+M 取 n]的q-analogue的q^M的係數 02/01 22:38
5F：→ Tangut : 感謝XII大，咕狗了一下，背景知識太少，還是看不太 02/01 22:47
6F：→ Tangut : 懂，有推薦的書或是網頁嗎？謝謝 02/01 22:47
沒學過離散數學，只有高中排列組合的程度QQ，
應該是強人所難，能夠以高中生能理解的程度來解釋這個公式嗎?
Q-analogue的公式要如何代入書中的例子能得到解?謝謝
※ 編輯: Tangut (1.174.88.201 臺灣), 02/02/2022 11:15:57
7F：推 XII : 已回信,我比較好奇的是什麼地方會用到這個?02/02 11:34
8F：→ XII : 至少要有一點生成函數和遞迴關係的概念02/02 11:35
非常感謝，我將回信附在原文
書中的例子是在解釋BOSE-EINSTEIN分布，假設總能量固定下，能夠對應到幾種粒子能量
分布?X1-X6代表六顆粒子(玻色子)，每個粒子能夠帶的能量有可能是1,2,3...,8，
因為玻色子不可分辨，所以(8,0,0,0,0,0)跟(0,8,0,0,0,0)會是一樣的解，
所以我才想到用非負整數且遞增的解來求解的數目
※ 編輯: Tangut (1.174.88.201 臺灣), 02/02/2022 11:58:55
9F：推 arrenwu : 這是你要的通解嗎？ 還是你是想要一個不是窮舉的02/02 12:21
10F：→ arrenwu : 算法？02/02 12:21
11F：→ samuel30214 : 去瞭解generating function 02/02 13:57
12F：→ XII : 粒子能帶的能量有上限嗎?有的話也可用Burnside來解 02/02 16:28
13F：推 Vulpix : 無上限也無所謂吧，畢竟總能量有限，在粒子能量有 02/02 17:29
14F：→ Vulpix : 下限0的情況下，自然會有個不能越過的能量上界。02/02 17:29
to arr大：是想要的，但確實是跟預期通解長的樣子不太一樣，也學到了一個新方法
to XII 大：是有上限，帶的不能超過總能量，如同Vulpix大寫的
※ 編輯: Tangut (223.139.252.141 臺灣), 02/03/2022 23:05:30
15F：推 Vulpix : 如果是要公式，那就再補個inverse z transform吧。 02/04 14:03