[其他] 非負整數解數目（遞增）

看板Math作者 (七下擋象)時間2年前 (2022/02/01 22:21), 2年前編輯推噓5(5推 0噓 10→)
留言15則, 6人參與, 2年前最新討論串1/1
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://www.ptt.cc/bbs/Math/M.1643725311.A.B79.html
推
02/01 22:22, 2年前 , 1F
高中的重複組合阿，H^m_n = C^(m+n+1)_n
02/01 22:22, 1F
→
02/01 22:32, 2年前 , 2F
要x1<=x2<=x3…，還有這個條件，不知為啥原文沒顯
02/01 22:32, 2F
→
02/01 22:32, 2年前 , 3F
示
02/01 22:32, 3F
補上了 ※ 編輯: Tangut (223.138.17.120 臺灣), 02/01/2022 22:37:23
→
02/01 22:38, 2年前 , 4F
[n+M 取 n]的q-analogue的q^M的係數
02/01 22:38, 4F
→
02/01 22:47, 2年前 , 5F
感謝XII大，咕狗了一下，背景知識太少，還是看不太
02/01 22:47, 5F
→
02/01 22:47, 2年前 , 6F
懂，有推薦的書或是網頁嗎？謝謝
02/01 22:47, 6F
沒學過離散數學，只有高中排列組合的程度QQ， 應該是強人所難，能夠以高中生能理解的程度來解釋這個公式嗎? Q-analogue的公式要如何代入書中的例子能得到解?謝謝 ※ 編輯: Tangut (1.174.88.201 臺灣), 02/02/2022 11:15:57
推
02/02 11:34, 2年前 , 7F
已回信,我比較好奇的是什麼地方會用到這個?
02/02 11:34, 7F
→
02/02 11:35, 2年前 , 8F
至少要有一點生成函數和遞迴關係的概念
02/02 11:35, 8F
非常感謝，我將回信附在原文 書中的例子是在解釋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
推
02/02 12:21, 2年前 , 9F
這是你要的通解嗎？ 還是你是想要一個不是窮舉的
02/02 12:21, 9F
→
02/02 12:21, 2年前 , 10F
算法？
02/02 12:21, 10F
→
02/02 13:57, 2年前 , 11F
去瞭解generating function
02/02 13:57, 11F
→
02/02 16:28, 2年前 , 12F
粒子能帶的能量有上限嗎?有的話也可用Burnside來解
02/02 16:28, 12F
推
02/02 17:29, 2年前 , 13F
無上限也無所謂吧，畢竟總能量有限，在粒子能量有
02/02 17:29, 13F
→
02/02 17:29, 2年前 , 14F
下限0的情況下，自然會有個不能越過的能量上界。
02/02 17:29, 14F
to arr大：是想要的，但確實是跟預期通解長的樣子不太一樣，也學到了一個新方法 to XII 大：是有上限，帶的不能超過總能量，如同Vulpix大寫的 ※ 編輯: Tangut (223.139.252.141 臺灣), 02/03/2022 23:05:30
推
02/04 14:03, 2年前 , 15F
如果是要公式，那就再補個inverse z transform吧。
02/04 14:03, 15F
‣ 更多 Tangut 的文章
文章代碼(AID): #1X-K7_jv (Math)