作者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/cn.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