n元一次不定方程 x1+x2+…+x璶= m 非负整数解的个数

崔达开 李茹 许湘津

【摘要】本文用建立两个集合一一对应的方法得出了n元一次不定方程x1+x2+…+xn= m非负整数解的个数，在此基础上得到了正整数解的个数，进而还得到了该方程的泛方程相应解的个数.

【关键词】不定方程;非负整数解;一一对应

【基金项目】云南省教育厅教育教学改革研究项目（JG2018260）

引言

今讨论形如

x1+x2+…+xn=m（1）

的n元一次不定方程非负整数解的个数，其中整数n≥2，m为非负整数.我们用集合一一对应的方法予以结论的证明，即

如果两个集合之间一一对应，那么这两个集合的元素个数是相同的.（2）

1其数学描述

若n个有序非负整数（x1，x2，…，xn）满足（1），则称它是（1）的一个解.（1）的解集合以S记之.显然S非空，因（m，0，…，0）∈S.

另外，令J是含有m+n-1个元素的集合，其元素分别记为 1，2，…，m+n-1，即J={1，2，…，m+n-1}.

今从J中取出n-1个元素视为一组，以这样的组为元素构成的集合以T记之，显然T的元素个数，即组合数：

Cn-1m+n-1=m+n-1n-1=（m+n-1）！m！（n-1）！（3）

2寻求一个T到S的一一对应

首先对于T中的一元，即从J中取出的n-1个元素形成的一组{k1，k2，…，kn-1}，不妨假定k1

令 x1=集合{j∈J：j

x2=集合{j∈J：k1

……

xn-1=集合{j∈J：kn-2

xn=集合{j∈J：kn-1

显然，xi≥0，i=1，2，…，n.

因集合J含有m+n-1个元，所以

（x1+1）+（x2+1）+…+（xn-1+1）+xn=m+n-1.

進而x1+x2+…+xn=m，即（x1，x2，…，xn）∈S.

从而我们建立了T到S的一个对应（映射）：

f：{k1，k2，…，kn-1}→（x1，x2，…，xn）.

不难看出，T的不同元在f下的像也不同.

最后我们看，对任意（x1，x2，…，xn）∈S，能否找到T中的一元，使其在f下的像正好是（x1，x2，…，xn）.

因x1+x2+…+xn=m，此时令k1=x1+1

k2=k1+x2+1=x1+x2+2，

k3=k2+x3+1=x1+x2+x3+3，

……

kn-1=kn-2+xn-1+1=x1+x2+…+xn-1+n-1=m+n-1-xn.

所以1≤k1

从而f是T到S的一一对应（映射）.由（2）（3）知，S的元素个数，即

（1）的非负整数解的个数为Cn-1m+n-1.（5）

3求解

以上不仅给出了（1）的解的个数，而且原则上还给出了求（1）的解之方法.

比如，当n=5，m=4时，（1）为x1+x2+x3+x4+x5=4，m+n-1=8，n-1=4.对于{k1，k2，k3，k4}={1，2，5，7}∈T，如表1所示：

由（4）得，x1=0，x2=0，x3=2，x4=1，x5=1，即（0，0，2，1，1）∈S.

再如，当n=4，m=5时，（1）为x1+x2+x3+x4=5，m+n-1=8，n-1=3;

对于{k1，k2，k3}={2，4，8}∈T，如表2所示：

由（4）得，x1=1，x2=1，x3=3，x4=0，即（1，1，3，0）∈S.

4应用举例

例1求x1+x2+…+x5=6的非负整数解的个数.

解此时n=5，m=6，m+n-1=10，n-1=4，

由（5），此方程解的个数为C410=10！6！4！=210.

例2将n个相同的小球，随机投入编号为 1，2，…，N 的N个盒中，n≥N.用古典概型，求没有空盒的概率.（参阅[1]）

解设xi是将n个球随机投入N个盒中，投毕后，编号为i的盒落入的球的个数，i=1，2，…，N.

该随机试验的样本空间所含的基本事件数为：

x1+x2+…+xN=n

的非负整数解的个数.由（5）可知为CN-1n+N-1.

根据题设“没有空盒”，即xi≥1，i=1，2，…，N.

将 xi=yi+1，i=1，2，…，N 代入上式得

y1+y2+…+yN=n-N，

∵n≥N，∴n-N是非负整数，

而“没有空盒”所含基本事件数是此方程非负整数解的个数，由（5）可知为CN-1（n-N）+N-1=CN-1n-1.

最后，该随机事件概率为 CN-1n-1CN-1n+N-1.

例3探讨三元不定方程

x+2y+3z=m（6）

的非负整数解的个数p3（m），其中m为非负整数.

解令x1=x，x2=2y，x3=3z，（7）

从而（6）为x1+x2+x3=m（8）

由（5）可知，（8）的非负整数解的个数为

C2m+2=（m+2）！m！2！=（m+2）（m+1）2.

从（8）的全部解中，找出满足（7）的非负整数解（x，y，z），即（6）的全部解，其个数为p3（m），如m=5时，（6）的非负整数解的个数为p3（5）=5，其解（x，y，z）为（0，1，1），（1，2，0），（2，0，1），（3，1，0），（5，0，0）.

5泛方程（1）

下面的方程（1）′称为泛方程（1）：

x1p1+…+xKpK+xK+1…+xn=m其中K=1，2，…，n整数pi≥1，i=1，2，…，K并且p1，p2，…，pK两两互素（1）′

今证：

（1）′的非负整数解的个数与（1）的相同，即为Cn-1m+n-1个.（9）

我们分以下几步来证（9）.

第一步，首先引入α∈R（实数集）的函数[α].[α]为不超过α的最大整数，所以 α=[α]+β，β满足0≤β<1.特别，当p为正整数，x为非负整数时，有

xp=xp+rp，整数r满足0≤r

显然，xp是非负整数xp的充要条件为r=0.

第二步，若x1，…，xK，xK+1，…，xn是（1）′的一个非负整数解，则xipi=xipi，i=1，2，…，K.

即  xipi 均为非负整数.②

证明：用反证法.假设②不成立，不失一般性，存在k=1，2，…，K，使得

xipi≠xipi，i=1，…，k=xipi，i=k+1，…，K，即xipi=xipi+ripi，整数ri满足0

当k=1时，将③代入（1）′，得

r1p1=m-∑Ki=1xipi-∑ni=K+1xi>0

所以，r1p1是正整数，这与整数r1满足0

当k=2，3，…，K时，将③代入（1），得

r1p1+r2p2+…+rkpk=m-∑Ki=1xipi-∑ni=K+1xi>0

所以，上式左边为一正整数，令其为q，即 r1p1+r2p2+…+rkpk=q，更有

p2p3…pkr1+p1p3…pkr2+…+p1p2…pk-1rk=qp1p2…pk，所以，p2p3…pkr1=p1（qp2…pk-p3…pkr2-…-p2…pk-1rk）.從而 p1整除p2p3…pkr1，又因p1，p2，…，pk两两互素，

∴ p1整除r1，这与0

第三步，（9）的证明.

由（5），n元一次不定方程

x′1+…+x′K+xK+1…+xn=m其中K=1，2，…，n④

的非负整数解的个数为Cn-1m+n-1.

由②，令xipi=x′i，i=1，2，…，K，所以（1）′的非负整数解的个数也为Cn-1m+n-1.

至此，（9）得证.

以下是（1）′的两种特殊情形：

ⅰ）K=1时，（1）′为

x1p1+x2+…+xn=m，整数p1>1，

此时可视为p2=p3=…=pn=1，∴p1，p2，…，pn两两互素.

ⅱ）K=n时，（1）′为

x1p1+x2p2+…+xnpn=m，整数pi>1，i=1，…，n，且p1，p2，…，pn两两互素.

不难看出，（1）′的一般形式为：

x1p1+x2p2+…+xnpn=m（1）″

（p1，p2，…，pn为两两互素的正整数）

其非负整数解的个数为Cn-1m+n-1.特别，当p1=p2=…=pn=1时，即为（1）.

事实上，（1）″也是n元一次不定方程，这由对（1）″的两边同乘p1p2…pn，立即得知.

注：令④的非负整数解的集合为A，（1）″的非负整数解的集合为B，由上述的证明过程可知，（1）″与④的非负整数解可以相互表示：

x′1，…，x′K，xK+1，…，xn∈A，则（p1x′1，…，pKx′K，xK+1，…，xn）∈B;

反之，（x1，…，xK，xK+1，…，xn）∈B，则x1p1，…，xKpK，xK+1，…，xn∈A.

例4已知 x′1+x2+x′3+x4+x′5=6 的一个非负整数解为（2，0，0，3，1），请用此解求

x125+x2+x37+x4+x512=6

的一个非负整数解.

解因为（x′1，x2，x′3，x4，x′5）=（2，0，0，3，1），后者的一个非负整数解为：

（x1，x2，x3，x4，x5）=（25×2，0，7×0，3，12×1）=（50，0，0，3，12）

例5求下式非负整数解的个数：

x16+x23+x3=2⑤

解由（5），x′1+x′2+x3=2，⑥

的非负整数解的个数为C3-12+3-1=C24=6.

又⑥的任意解x′1，x′2，x3，对应⑤的一个解（x1，x2，x3）=6x′1，3x′2，x3，这样得到了⑤的6个解;

此处，当x16≠x16且x23≠x23时，也可以得到⑤的非负整数解（x1，x2，x3），分别为：（2，2，1），（4，1，1），（8，2，0），（2，5，0），（10，1，0），（4，4，0）.从而，⑤的非负整数解为12个，故（9）不成立.

事实上，p1，p2，…，pn两两互素是（1）″的必要条件，即在（1）″中，m≥1，若非负整数解的个数为Cn-1m+n-1，则p1，p2，…，pn两两互素.（证明，略）

6一点启示

由例2可知，当m≥n时，方程（1）的正整数解的个数为Cn-1m-1.（10）

证法与例2相同，不赘述.

【参考文献】

[1]王梓坤.概率论基础及应用[M].北京：科学出版社，1976，7：8-15，35.

[2]闵嗣鹤，严士健.初等数论[M].第三版.北京：高等教育出版社，2003，7：4-33.

[3]华罗庚.数论导引[M].北京：科学出版社，1975：1-5，203-204.

[4]李高.关于一次不定方程x1+x2+…+xm=n正整数解的新解法[J].河北北方学院学报（自然科学版），2017，33（09）：26-28.