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.