構(gòu)建不定方程模型解決計數(shù)問題

石向陽

許多組合問題看似與方程無關，若能去偽存真，轉(zhuǎn)換思維角度，轉(zhuǎn)化為不定方程整數(shù)解的模型，則往往能化繁為簡、柳暗花明.1不定方程整數(shù)解的有關結(jié)論

定理1不定方程x1+x2+…+xk=n（k，n∈N+）的非負整數(shù)解的個數(shù)為Cnn+k-1.

證法1將不定方程x1+x2+…+xk=n的任意一組非負整數(shù)解（x1，x2，…，xk）對應于一個由n個圓圈“○”和k-1個“+”組成的如圖○…○x1個+○…○x2個+…+○…○xk個所示的排列，每段圓圈“○”的個數(shù)即為原方程的一組非負整數(shù)解，易證對應關系是一對一的.

所以不定方程x1+x2+…+xk=n的非負整數(shù)解的個數(shù)就是n個圓圈“○”和k-1個“+”組成的直線排列數(shù)，即在n+k-1個位置中選k-1放置“+”（或選n個位置放置圓圈“○”），因此共有不同的排法種數(shù)為Ck-1n+k-1=Cnn+k-1.

證法2對不定方程x1+x2+…+xk=n的任意一組非負整數(shù)解（x1，x2，…，xk），令y1=x1+1，y2=x1+x2+2，…，yk=x1+x2+…+xk+k，則1≤y1

定理2不定方程x1+x2+…+xk=n（k≥2，n≥2，k≤n）的正整數(shù)解的個數(shù)為Ck-1n-1.

證法1設想將n個1排成一排，這n個1之間有n-1個空檔，從n-1個空檔中選k-1個放入k-1個“+”，共有Ck-1n-1種放法，這k-1個“+”把n個1分成k段，各段1的個數(shù)即為原方程的一組正整數(shù)解，這樣“+”的每一種放法就對應著原不定方程的一組正整數(shù)解，所以原不定方程共有Ck-1n-1組解.

證法2令yi=xi-1，其中xi≥1，不定方程x1+x2+…+xk=n的正整數(shù)解與不定方程y1+y2+…+yk=n-k非負整數(shù)解之間建立了一一對應關系，所以不定方程x1+x2+…+xk=n的正整數(shù)解組（x1，x2，…，xk）的組數(shù)與不定方程y1+y2+…+yk=n-k非負整數(shù)解組（y1，y2，…，yk）的組數(shù)相等，由定理1知，方程y1+y2+…+yk=n-k有Cn-k（n-k）+k-1=Cn-kn-1=Ck-1n-1個非負整數(shù)解，所以方程x1+x2+…+xk=n有Ck-1n-1個正整數(shù)解.2利用不定方程整數(shù)解的結(jié)論解有限制條件的不定方程或不定方程組的整數(shù)解的個數(shù)問題

例1求方程2x1+x2+x3+…+x10=3的非負整數(shù)解的個數(shù).

解析由題意，x1=0，1，故分情況討論如下：

若x1=0，則x2+x3+…+x10=3，該方程非負整數(shù)解的個數(shù)為：C39+3-1=165；

若x1=1，則x2+x3+…+x10=1，該方程非負整數(shù)解的個數(shù)為：C19+1-1=9.

綜上，非負整數(shù)解的個數(shù)為：165+9=174個.

例2求方程x+y+z=2010滿足x≤y≤z的正整數(shù)解x，y，z的個數(shù).

解析首先由定理2知，方程x+y+z=2010的正整數(shù)解的個數(shù)為C22009=2009×1004.

把x+y+z=2010滿足x≤y≤z的正整數(shù)解分為三類：

1x，y，z均相等的正整數(shù)解的個數(shù)顯然為1；

2x，y，z中有且僅有兩個相等的正整數(shù)解的個數(shù)，易知為1003個；

3x，y，z兩兩均不相等的正整數(shù)解個數(shù)為k.

易知1+3×1003+6k=2009×1004，解得k=335671，從而方程x+y+z=2010滿足x≤y≤z的正整數(shù)解的個數(shù)為1+1003+335671=336675

例3在世界杯足球賽前，F(xiàn)國教練為了考察A1，A2，…，A7這七名隊員，準備讓他們在三場訓練比賽（每場90分鐘）中都上場.假設在比賽的任何時刻，這些隊員中有且僅有一人在場上，且A1，A2，A3，A4每人上場的總時間（以分鐘為單位）均能被7整除，A5，A6，A7每人上場的總時間（以分鐘為單位）均能被13整除.如果每場換人次數(shù)不限，那么，按每名隊員上場的總時間計算，共有多少種不同的情況.

解析設第i名隊員上場的時間為xi分鐘（i=1，2，3，…，7），問題即求不定方

程x1+x2+…+x7=270在條件7xi（1≤i≤4）且13xj（5≤j≤7）下的正整數(shù)解的組數(shù).由條件，設x1+x2+x3+x4=7m，x5+x6+x7=13n（m≥4，n≥3）.于是m、n即是不定方程7m+13n=270的一組正整數(shù)解.由m=270-13n7≥4，易得3≤n≤18，（n∈N）.進而得到方程的三組正整數(shù)解：

m=33，

n=3，m=20，

n=10，m=7，

n=17，設xi=7yi（1≤i≤4），xj=13yj（5≤j≤7）.

所以本題轉(zhuǎn)化為求方程組y1+y2+y3+y4=33，

y5+y6+y7=3，y1+y2+y3+y4=20，

y5+y6+y7=10，

y1+y2+y3+y4=7，

y5+y6+y7=17，的正整數(shù)解的組數(shù).由分步乘法計數(shù)原理和分類加法計數(shù)原理及定理2知共有正整數(shù)解C332C22+C319C29+C36C216=42244組.3利用不定方程整數(shù)解的結(jié)論解排列組合中的計數(shù)問題

利用不定方程整數(shù)解的結(jié)論解決排列組合中的計數(shù)問題，一般用于相同元素的有序分配問題，如指標數(shù)、個數(shù)、人數(shù)等相同的事物的數(shù)量分配問題.

3.1投球入盒問題

例4把2016個不加區(qū)別的小球分別放在10個不同的盒子里，使得第i個盒子里至少有i個球（i=1，2，…，10），問不同放法的總數(shù)是多少？

解析先在第i個盒子里放入i個球（i=1，2，…，10），即第1個盒子里放入1個球，第2個盒子里放入2個球，…，這時共放了1+2+3+…+10=55個球.還剩余2016-55=1961個球.故問題轉(zhuǎn)化為把1961個球任意放入10個盒子里（允許有的盒子里不放球），即為不定方程x1+x2+…+x10=1961的非負整數(shù)解的個數(shù)，由定理1知有C19611961+10-1=C91970種不同放法.

3.2名額分配問題

例5將24個志愿者名額分配給3個學校，則每校至少有一個名額且各校名額互不

相同的分配方法共有多少種？解析設分配給3個學校的名額數(shù)分別為x1，x2，x3，則每校至少有一個名額的分法數(shù)為不定方程x1+x2+x3=24的正整數(shù)解的個數(shù)，由定理2得不定方程x1+x2+x3=24的正整數(shù)解的個數(shù)為C223=253.又在“每校至少有一個名額的分法”中“至少有兩個學校的名額數(shù)相同”的分配方法有31種.

綜上知，滿足條件的分配方法共有253-31=222種.

3.3染色問題

例6用紅、橙、黃、綠、青、藍、紫七種顏色的一種，或兩種，或三種，或四種，分別涂在正四面體各個面上，一個面不能用兩色，也無一個面不著色的，問共有幾種著色法？

解析設紅色涂了x1個面，橙色涂了x2個面，…紫色涂了x7個面，則x1+x2+…+x7=4，正四面體著色方法與方程的非負整數(shù)解建立了一一對應的關系.由定理1知該不定方程有C47+4-1=210組非負整數(shù)解，所以正四面體共有210種著色方法.

3.4擲骰子問題

例7三粒骰子同時擲出，有多少種不同的結(jié)果？

解析設擲出1點的有x1粒，設擲出2點的有x2粒，…，設擲出6點的有x6粒，則有x1+x2+…+x6=3.擲骰子的結(jié)果與方程的非負整數(shù)解建立了一一對應的關系.由定理1知該不定方程有C36+3-1=C38=56組非負整數(shù)解，所以共有56種不同的結(jié)果.

3.5進站問題

例8某民航站共有1到4個入口，每個入口處每次只能進一個人，一小組4個人進站的方案數(shù)有多少種.

解析設第1，2，3，4個入口分別進x1，x2，x3，x4人，則xi≥0且x1+x2+x3+x4=4，由定理1知不定方程x1+x2+x3+x4=4的非負整數(shù)解的個數(shù)C44+4-1=C37即為4個人進站的分組方法數(shù)；由于每個入口處每次只能進一個人，按第1，2，3，4個入口順序同時通過入口排成一列，就每一分組方法將四個人全排列有A44種方法，所以共有不同進站方法C37·A44=840種.

3.6開關燈問題

例9街道上有10盞路燈，要求晚上關掉其中4盞，且為了方便行人，相鄰的路燈不允許關掉.問共有多少種關燈的方法？

解析先考慮關著的燈，再考慮開著的燈，如圖：○○○○，有4盞燈關著，它們之間形成了5個空，這5個空共要插進6盞燈作為開著的燈，設從左到右第i個空共有xi（i=1，2，3，4，5）盞燈開著，則有x1+x2+x3+x4+x5=6，等價于（x1+1）+x2+x3+x4+（x5+1）=8（x1+1，x2，x3，x4，x5+1≥1，且xi∈N），由定理2知，共有C47=35種方法，所以共有35種開關燈的方法.

3.7在線性規(guī)劃中整點個數(shù)問題

例10在直角坐標系xOy中，已知△ABC三邊所在直線方程分別為x=0，y=0，x+y=4，則在△ABC內(nèi)部（包括邊界）的整點個數(shù)是多少？

解析此類題常見解法是畫圖描出整點，然后數(shù)一下.實際上滿足題意的整點（x，y）必有x+y≤4，且x≥0，y≥0.若令z=4-（x+y）則z≥0且z為整數(shù).所以x+y+z=4，該方程非負整數(shù)解的組數(shù)即為整點個數(shù).所以整點個數(shù)是C44+3-1=C26=15.

3.8n項展開式的項數(shù)問題

例11試問（a+b+c）10的展開式共有多少項？

解析（a+b+c）10展開式每一項均可表示為ax1·bx2·Cx3，其中xi≥0（i=1，2，3）且x1+x2+x3=10.因此，求展開式中共有多少項，即求不定方程x1+x2+x3=10共有多少組非負整數(shù)解.由定理1知，此不定方程解的個數(shù)為C1010+3-1=C212=66，所以展開式共有66項.

同理可得（a1+a2+…+an）m展開式共有Cmn+m-1項.

3.9廣告問題

例12電視臺在n天內(nèi)共播出r次商業(yè)廣告，問若每天至少播p次廣告（np≤r），就每天播出廣告的次數(shù)而言，共有幾種播出方法？

解析設第i天播出廣告xi次，由題設知：x1+x2+…+xn=r，xi≥p（i=1，2，…，n），令yi=xi-p，則y1+y2+…+yn=r-np≥0，故問題轉(zhuǎn)化為求上述不定方程的非負整數(shù)解的個數(shù)，由定理1知廣告播放的方法數(shù)為Cr-np（r-np）+n-1.

3.10有條件的環(huán)形排列問題

例138個女孩和25個男孩圍成一圈，任意兩個女孩之間至少站兩個男孩，那么，共有多少種不同的排列方法.（只要把圈旋轉(zhuǎn)一下就重合的排法認為是相同的）.

解析以8個女孩為組長，將25個男孩分入該8組，每組內(nèi)男孩數(shù)記為x1，x2，…，x8，

則x1+x2+…+x8=25，（xi≥2，i=1，2，…8），設xi-1=yi（i=1，2，…，8），即得y1+y2+…+y8=17，（yi≥1，i=1，2，…，8），于是由定理2可求出符合條件的方程組的解的個數(shù)為C8-117-1=C716，即25個男孩分入8組，每組至少2人的分組方法有C716種.

8個組排成每組以女孩為頭的圓排列有（8-1）！=7?。ㄒ粋€8個元素的圓排列包括8個不同的線性排列，設8個元素的圓排列數(shù)為N，則8N=A88，所以N=A77）種排列方法，再將25個男孩站入的方法數(shù)為25！.

所以總的排列數(shù)為C716·7！·25！=16！·25！9！.

3.11比賽過程的種數(shù)問題

例14甲乙兩隊各出7名隊員按事先排好的順序出場參加圍棋擂臺賽.雙方先由1號隊員比賽，負者被淘汰，勝者再與負方2號隊員比賽，……直到有一方隊員全被淘汰為止，另一方獲得勝利，形成一種比賽過程.求所有可能出現(xiàn)的比賽過程的種數(shù).

解析先考慮甲隊獲勝的比賽過程，設甲隊隊員第i號隊員勝了xi場，（i=1，2，…，7），則x1+x2+…+x7=7，于是甲隊獲勝的比賽過程與方程x1+x2+…+x7=7的非負整數(shù)解組（x1，x2，…，x7）構(gòu)成一一對應，由定理1知方程x1+x2+…+x7=7有C67+6=C613組非負整數(shù)解，所以甲隊獲勝的比賽過程有C613種，同理乙隊獲勝的比賽過程也有C613種，故不同的比賽過程共有2C613=3432種.

3.12集合、映射個數(shù)問題

例15已知兩個實數(shù)集合A={a1，a2，…，a100}與B={b1，b2，…，b50}.若從A到B的映射f使得B中每個元素都有原像，且f（a1）≤f（a2）≤…≤f（a100），求這樣的映射的個數(shù).

解析不妨設b1

例16設集合M={1，2，3，…，14}，Ma={a1，a2，a3}，Ma為M的子集，且滿足a1+6≤a2+3≤a3，求Ma的個數(shù).

解析由a1≥1，a2-a1≥3，a3-a2≥3，14-a3≥0，令a1=x1，a2-a1=x2，a3-a2=x3，14-a3=x4，則x1+x2+x3+x4=14，問題即求不定方程在x1≥1，x2≥3，x3≥3，x4≥0下的整數(shù)解的組數(shù)，又方程轉(zhuǎn)化為x1+（x2-2）+（x3-2）+（x4+1）=11.令x1=y1，x2-2=y2，x3-2=y3，x4+1=y4，而y1+y2+y3+y4=11的正整數(shù)解的組數(shù)是C310.所以符合條件的Ma的個數(shù)有C310=120個.

以上問題雖然背景各異，但經(jīng)充分挖掘后發(fā)現(xiàn)本質(zhì)是相同的，其結(jié)果均與不定方程的整數(shù)解有一一對應的關系.解題的關鍵是建立不定方程模型.問題一般有三類，第一類是中間的可以一個也沒有，用定理1求解（如例4、例6、例7、例8、例10、例11、例14）；第二類是中間的個數(shù)至少有一個，用定理2求解（如例5、例9、例15）；第三類是中間的個數(shù)多于1個，這類有約束條件的相同元素的有序分配問題，相對來講破解較難，需要通過轉(zhuǎn)化問題才能用不定方程來處理.轉(zhuǎn)化的關鍵是使問題變成第一個類型（如例12），當然也可以轉(zhuǎn)化第二個類型（如例13、例16）.4不定方程非負整數(shù)解與重復組合數(shù)的關系

從k個不同的元素中，取n個允許重復的元素而不考慮其次序，被稱為從k個不同元素中取n個允許重復的組合，簡稱為n-重復組合，允許重復的組合數(shù)常常記作Hnk.

設（a1，a2，…，an）是取自{1，2，…，k}中的任一n-可重復組合，并設a1≤a2≤…≤an，令bi=ai+i-1（1≤i≤n），從而b1=a1，b2=a2+1，b3=a3+2，…，bn=an+n-1，顯然下面兩組數(shù)是一對一的：

a1≤a2≤…≤an，1≤a1

設A={（a1，a2，…，an）|ai∈{1，2，…，k}，a1≤a2≤…≤an}，

B={（b1，b2，…，bn）|bi∈{1，2，…，k+n-1}，b1

其一、上述證明，與定理1的證法2大同小異，請仔細體味其中小異妙在何處.

其二、設n-可重復組合a1，a2，…，an中含有x1個1，x2個2，…，xk個k，則x1+x2+…+xk=n（k，n∈N+），顯然（a1，a2，…，an）與不定方程x1+x2+…+xk=n的解（x1，x2，…，xk）一一對應.

其三、允許重復的組合的典型模型是把n只相同顏色的球放到k個編號不同的盒子中，而且每個盒子放球數(shù)不加限制，xi代表第i（i=1，2，3，…，k）個盒子中所放的球的個數(shù)，那么就有x1+x2+…+xk=n（k，n∈N+），不同的放法就對應該方程的不同的解.

對例6我們用重復的組合數(shù)來理解，易知，正四面體的相關位置，沒有先后順序，即先涂或后涂哪個面，沒有什么不同，所以是組合問題；這四個面可以分別用一種，或兩種，或三種，或四種顏色，故是一個重復組合問題，即可歸結(jié)為4只相同顏色的球放到7個編號不同的盒子中，每個盒子放球數(shù)不加限制，故有著色法H47=C47+4-1=210.

對例7我們用重復的組合數(shù)來理解，因為擲三粒骰子等價于從六個數(shù)1，2，3，4，5，6中允許重復的選取三個數(shù)，故不同結(jié)果的數(shù)目是H36=C36+3-1=C38=56.

從重復的組合數(shù)來理解不定方程的非負整數(shù)解，對于培養(yǎng)思維的深刻性、邏輯性大有裨益.